题意：有6种石头，价值分别是1,2,3,4,5,6 每种有若干，作为输入数据。问能否把这些石头按照价值均分？
分析：多重背包问题。
代码：
View Code
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 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<MAXN; i++) dp[i]=0; 19 int v=sum>>1; 20 for(i=1; i<=6; i++){ 21 for(k=1; n[i]; k<<=1){ 22 if(n[i]<k) k=n[i]; 23 for(j=v; j>=k*i; j--) 24 if(dp[j]<dp[j-k*i]+k*i) dp[j]=dp[j-k*i]+k*i; 25 n[i]-=k; 26 } 27 } 28 if(dp[v]==v) printf("Can be divided.\n\n"); 29 else printf("Can't be divided.\n\n"); 30 } 31 }
发现如果用max()函数会比较慢，改用if判断来更新dp值的时候会快0.6秒左右~
不过如果输入数据a[i]mod30后会0ms就ac 我表示很不解：
View Code
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 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<MAXN; i++) dp[i]=0; 24 int v=sum>>1; 25 for(i=1; i<=6; i++){ 26 for(k=1; n[i]; k<<=1){ 27 if(n[i]<k) k=n[i]; 28 for(j=v; j>=k*i; j--) 29 if(dp[j]<dp[j-k*i]+k*i) dp[j]=dp[j-k*i]+k*i; 30 n[i]-=k; 31 } 32 } 33 if(dp[v]==v) printf("Can be divided.\n\n"); 34 else printf("Can't be divided.\n\n"); 35 } 36 }
至于剪枝我还没有去想过，这里的代码可以参考下http://liangguoqiu.diandian.com/post/2010-04-29/40038525181
