#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int N,n[105],c[105],v[105],dp[105][105],p=0,V;
memset(dp,0,sizeof(dp));
cin>>N>>V;
for(int i=1;i<=N;i++)
{
cin>>v[i]>>c[i]>>n[i];
}
for(int i=1;i<=N;i++)
{
for(int j=V;j>=0;j--)
{
for(int k=0;k<=n[i];k++)
{
if(j>=k*v[i])
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*c[i]);
}
}
}
}
p=dp[N][V];
cout<<p;
}
AcWing 4. 多重背包问题 I（新手向） 原题链接 简单
作者：
夜晚星狼
,
2019-07-03 16:53:57
,
所有人可见
,
阅读 4492
夜晚星狼
,
2019-07-03 16:53:57
,
所有人可见
,
阅读 4492
对于上述评论区提到的问题，k是从0开始更新的。因此当k=0时，实际上就是dp[i-1][j]。
状态转移方程为：dp[i][j] = max(dp[i - 1][j], dp[i -1][j -v] +w,dp[i-1][j-2v]+2w,…)
感谢大佬解决了我的疑惑！！
这个是真的强。k=1和V/v[i]就分别退化为01和完全背包
请问为什么是dp[i][j]=max(dp[i][j],dp[i-1][j-kv[i]]+kc[i]);而不是dp[i][j]=max(dp[i-1][j],dp[i-1][j-kv[i]]+kc[i]);呢？
我也有下列同样问题。而且，我觉得应该是max(dp[i-1]…。
因为多重背包就是01背包的变形，所以转移状态也应该与01的相同，即max(dp[i-1…
请大家指正，讲明why，why,why.谢谢。
请问为什么是dp[i][j]=max(dp[i][j],dp[i-1][j-kv[i]]+kc[i]);而不是dp[i][j]=max(dp[i-1][j],dp[i-1][j-kv[i]]+kc[i]);呢？
都是dp[i - 1] 只不过左边的算过了 右边必须满足条件才能算 故此
请问为什么是dp[i][j]=max(dp[i][j],dp[i-1][j-kv[i]]+kc[i]);而不是dp[i][j]=max(dp[i-1][j],dp[i-1][j-kv[i]]+kc[i]);呢？
请问为什么是dp[i][j]=max(dp[i][j],dp[i-1][j-kv[i]]+kc[i]);而不是dp[i][j]=max(dp[i-1][j],dp[i-1][j-kv[i]]+kc[i]);呢？
请问为什么是dp[i][j]=max(dp[i][j],dp[i-1][j-kv[i]]+kc[i]);而不是dp[i][j]=max(dp[i-1][j],dp[i-1][j-kv[i]]+kc[i]);呢？
是“种”不是“个”，不能减一。