EOJ(动态规划）——1052. 0-1背包问题
单测试点时限: 2.0 秒
内存限制: 256 MB
已知 n 个物体 1,2,3,…,n 与一个背包。物体 i 的重量为 Wi>0，价值为 Pi>0 (i=1,2,…,n)，背包容量为 M>0。
求在不超过背包容量的情况下，使得装进去的物体的价值最高。
输入
第一行为一个正整数 T，表示有几组测试数据。
每组测试数据的第一行为两个整数 n 和 M，0<n≤20,0<M<100000。
再下去的 n 行每行有两个整数 Wi,Pi，0<Wi,Pi<10000。
输出
对于每组测试数据，输出一行，只含一个整数，表示装进去物体的价值最高值。
样例
input
1
5 10
2 6
2 3
6 5
5 4
4 6
output
15
题目大意：
01背包。
题目解析：
第二次遇到01背包问题，这次算是完全弄明白了。
01背包核心代码：
for(int i=1;i<=n;i++){
for(int j=1;j<=M;j++){
if(j<weight[i])
dp[i][j]=dp[i-1][j];
else{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+price[i]);
}
}
}
关键点：
- dp[i][j]表示前i件物品，放入总空间为j的背包中，所能装下商品的最大价值。
- for循环下标要从1开始而不是0开始，因为当i等于0时（即前0件商品）最大价值肯定为0，j等于0时（即总空间为0）最大价值肯定为0。
if(j<weight[i]) dp[i][j]=dp[i-1][j];//表示第i件商品的重量已经超出了总空间，所以肯定装不下，等于前i-1件商品在此空间下的总价值。dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+price[i]);中的dp[i-1][j-weight[i]]+price[i]);表示把第i件物品放进去看看总价值为多少，其结果自然是物品i的价值加上前i-1件物品在总空间j-weight[i]中的最大总价值。跟不第i件物品做对比，看看谁大。
具体代码：
#include<iostream>
using namespace std;
#define MAXN 25
int weight[MAXN],price[MAXN];
int dp[MAXN][100005];//dp[i][j]表示前i件物品放入空间为j的最大价值
int main()
{
int T;
cin>>T;
while(T--){
int n,M;
cin>>n>>M;
for(int i=1;i<=n;i++)
cin>>weight[i]>>price[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=M;j++){
if(j<weight[i])
dp[i][j]=dp[i-1][j];
else{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+price[i]);
}
}
}
cout<<dp[n][M]<<endl;
}
return 0;
}
