一個多重背包的問題，如果還不了解多重背包， ，當然要深刻理解0/1背包和完全背包之後看多重背包就很簡單。
代碼：
[cpp]
#include<iostream>
using namespace std;
int dp[105],v,n[105],vl[105],ct[105];
void ZeroOnePack(int cost,int value)
{
for(int i=v; i>=cost; i--)
dp[i]=max(dp[i],dp[i-cost]+value);
}
void CompletePack(int cost,int value)
{
for(int i=cost; i<=v; i++)
dp[i]=max(dp[i],dp[i-cost]+value);
}
void MultiPack(int cost,int value,int num)
{
int k;
if( num*cost>=v)
CompletePack(cost,value);
else{
k=1;
while( num>k){
ZeroOnePack(k*cost,k*value);
num-=k;
k*=2;
}
ZeroOnePack(num*cost,num*value);
}
}
int main()
{
int c,m,i;
scanf("%d",&c);
while( c--){
scanf("%d%d",&v,&m);
for( i=1; i<=m; i++)
scanf("%d%d%d",&vl[i],&ct[i],&n[i]);
memset(dp,0,sizeof(dp));
for( i=1; i<=m; i++)
MultiPack(vl[i],ct[i],n[i]);
int mx=0;
for( i=1; i<=v; i++){
if( dp[i]>mx)
mx=dp[i];
}
printf("%d\n",mx);
}
}
作者：aacm1992
