HDOJ 2192 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
一个多重背包的问题，如果还不了解多重背包，建议看背包九讲http://love-oriented.com/pack/#sec5，当然要深刻理解0/1背包和完全背包之后看多重背包就很简单。
代码：
#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]); printf("%d\n",dp[v]); }}