HDOJ 2192 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

一个多重背包的问题，如果还不了解多重背包，  ，当然要深刻理解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