//动态规划的话，我的思路就是
//一：先确定dp数组
//维度i,j：一般是多少种选法，还有体积限制
//含义：最大值，最小值，数量
//二：初始化、
//三：遍历dp，更新dp[i][j]
//这里就是集合划分，将当前dp[i][j]所有情况进行分析
//和floyd一样，你要学会使用自己的dp数组
[https://www.acwing.com/solution/content/4515/](http:www.acwing.com/solution/content/4515/)
//感觉这个挺好的
//dp[i][j] 考虑i个物品，空间为j，最大的价值
//初始化，更新第一行
//对于dp[i][j],要么选择i，要么不选择i
//如果j装不下i物品，那么就是不选择，最大值为dp[i-1][j];
//如果j可以装下i物品，考虑选择和不选择两者最大的那个
#include<iostream>
#include<algorithm>
using namespace std;
int w[1010],v[1010];
int dp[1010][1010];
int maxvalue=0,num,maxv;
void search(){
for(int i=0;i<=maxv;i++){
if(v[1]<=i) dp[1][i]=w[1];
}
for(int i=2;i<=num;i++){
for(int j=0;j<=maxv;j++){
if(j>=v[i]){
dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
}
else dp[i][j]=dp[i-1][j];
}
}
}
int main(){
cin>>num>>maxv;
for(int i=1;i<=num;i++) cin>>v[i]>>w[i];
search();
// for(int i=1;i<=num;i++){
// for(int j=1;j<=maxv;j++){
// cout<<dp[i][j]<<' ';
// }
// cout<<endl;
// }
cout<<dp[num][maxv];
}
我的理解就是，物品变得无限量
这里集合划分我们就需要考虑选一件，选两件这样下去
这里有一个优化，就是发现选一件的情况已经包含了后面的情况
只需要考虑这一种情况即可
这里有一点需要注意，我们在之前的情况列举中是对比
max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i])
然后我们发现了一个规律，和dp[i][j-v[i]]的规律
dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i])
这里是用本行之前的情况，代替上面很多情况
我们列举一下更新次序的内部关系：
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系：
f[i][j]=max(f[i,j-v]+w , f[i-1][j])
> 有了上面的关系，那么其实k循环可以不要了，核心代码优化成这样：
for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{
f[i][j] = f[i-1][j];
if(j-v[i]>=0)
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
对于多重背包来说
其实就是给了数量限制，这里其实思考方式和完全背包一样
只不过数量给了上限
还有一种思路是将一个物品k个，转化为k个物品，只不过这k个物品的价值和体积都是一样的，这样转化为基本的01背包问题
这里最优解是进行二进制方面的知识，过于复杂了，不看了
这里我有一个错误的地方在于，和之前的完全背包搞混淆了
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i])
这里后面是i-1，我和完全搞混淆了
