算法设计例题：多重背包

给定N种物品和一个容量为C的背包，第i种物品最多有 M_i 件可用，每件的重量是W_i，价值是V_i。问：将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入的第一行为测试样例的个数T，接下来有T个测试样例。

每个测试样例的第一行是物品种数N（1 ≤ N ≤ 100）和背包容量C（C ≤ 10000）。

接下来N行，每行三个正整数，W_i ，V_i 和 M_i （ W_i ≤ 10000,    V_i ≤ 10000,    M_i ≤ 10000 ），分别表示第i种物品的重量 W_i ，价值 V_i ，及个数 M_i 。

对应每个测试样例输出一行，只有一个整数，表示装入背包的物品总价值的最大值。

1
2 8
4 100 2
2 100 4

400

#include
#define ll long long
#define INF 0x3f3f3f3f
const int maxn = 1e4+10;
using namespace std;
int w[maxn],v[maxn],dp[maxn];
int main()
{
int t;cin>>t;
while(t--){
int n,c;
cin>>n>>c;
int num=0;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
int x,y,z,res=1;
cin>>x>>y>>z;
while(res w[++num]=res*x;
v[num]=res*y;
z-=res;
res*=2;
}
if(z>0){
w[++num]=x*z;
v[num]=y*z;
}
}
for(int i=1;i<=num;i++)
for(int j=c;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
cout< }
}