题意：有6种石头，价值分别是1,2,3,4,5,6   每种有若干，作为输入数据。问能否把这些石头按照价值均分？

分析：多重背包问题。

代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 const int MAXN = 60000 + 5; 6 int dp[MAXN], n[6]; 7 int main(){ 8     int i, j, k; 9     int cas = 0;10     while(scanf("%d%d%d%d%d%d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6])!=EOF){11         int sum=n[1]+n[2]*2+n[3]*3+n[4]*4+n[5]*5+n[6]*6;12         if(!sum) break;13         printf("Collection #%d:\n", ++cas);14         if(sum%2) {15             printf("Can't be divided.\n\n");16             continue;17         }18         for(i=0; i
         
          >1;20         for(i=1; i<=6; i++){21             for(k=1; n[i]; k<<=1){22                 if(n[i]
          
           =k*i; j--)24                     if(dp[j]
          
         
        
       
      

发现如果用max()函数会比较慢，改用if判断来更新dp值的时候会快0.6秒左右~

不过如果输入数据a[i]mod30后会0ms就ac 我表示很不解：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 const int MAXN = 60000 + 5; 6 int dp[MAXN], n[6]; 7 int main(){ 8     int i, j, k; 9     int cas = 0;10     while(true){11         int sum = 0;12         for(i=1; i<=6; i++){13             scanf("%d", &n[i]);14             n[i]%=30;15             sum+=n[i]*i;16         }17         if(!sum) break;18         printf("Collection #%d:\n", ++cas);19         if(sum%2) {20             printf("Can't be divided.\n\n");21             continue;22         }23         for(i=0; i
         
          >1;25         for(i=1; i<=6; i++){26             for(k=1; n[i]; k<<=1){27                 if(n[i]
          
           =k*i; j--)29                     if(dp[j]
          
         
        
       
      

至于剪枝我还没有去想过，这里的代码可以参考下