基本思路
多重背包只是在完全背包上加了一些限制
每个物品的选择次数有了限制,所以只需要在循环次数的时候加个判断条件k<=s[i]
代码实现
#include <iostream>
using namespace std;
const int N=1010;
int f[N][N],v[N],w[N],s[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k*v[i]<=j&&k<=s[i];k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
cout<<f[n][m];
}
为什么是
f[i-1]
而不是f[i-k]
呢啊我理解了,f[i]表示的是前i种物品,而不是前i个物品。还是太弱了qaq