分析
与01背包不同的是,多重背包的每一个物品有$S$件,而01背包每个物品有$1$件。
我们是不是可以进行一个拆分,把这$S$件物品拆成01背包的模型来计算。
我们再看物品的数量,假设最多的$100$件物品,每个物品可以取$100$次,我们使用三重循环的话,时间复杂度是$100 * 100 * 100$,也就是$10^6$。而C++程序一秒大概可以执行$10^7 \sim10^8左右$的次数。
也就是说我们简单使用三重循环的暴力方法是可以过的。
#include <iostream>
using namespace std;
const int N = 110;
int dp[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
int v,w,s;//v 物品所占的体积 w 物品的重量 s 物品的数量
cin>>v>>w>>s;
for(int j = m; j >= v; j--)
for(int k = 1; k <= s && (k * v <= j); k++)
dp[j] = max(dp[j], dp[j - k * v] + k * w);
}
cout<<dp[m]<<endl;
return 0;
}