多重背包（洛谷）

背包（洛谷）"/>

多重背包（洛谷）

多重背包链接（洛谷）

一.分析题目：

有n种物品，每种物品有多件，而且每种物品的体积和价值不变。

二.用集合的方式表示：

我们用一个f[i,j]表示，从i件物品中选，且所选物品的总体积不超过j的所有选法的集合，然后我们再选出这些方案中最有价值的一个方案我们用max表示。

三.计算集合：

f[i,j]枚举i种物品中选几个，假如我们选k*v[i]（k*v[i]<=i）件物品，而且选的这k*v[i]件物品的总价值为k*w[i],那么就可以推出这个式子： f[i,j]=max(f[i-1][j-k*v[i]]+k*w[i],f[i,j])

代码如下：

#include<iostream>
using namespace std;
const int N=110;
int n,m;
int f[N][N];
int v[N],s[N],w[N];
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=1;j<=m;j++){for(int k=0;k<=s[i]&&k*v[i]<=j;k++){f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}}cout<<f[n][m];return 0;
}