完全背包的二进制优化

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 const int maxn=20005;
 7 int va[maxn];
 8 int dp[maxn*6];
 9 int a[7];
10 
11 int main()
12 {
13     int kase=1;
14     //freopen("aa.txt","r",stdin);
15     while(scanf("%d %d %d %d %d %d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6]))
16     {
17         int sum=0;
18         for(int i=1;i<=6;i++)
19         sum+=i*a[i];
20 
21         if(sum==0)
22         break;
23 
24         printf("Collection #%d:\n",kase++);
25         if(sum%2==1)
26         {
27             printf("Can‘t be divided.\n\n");
28             continue;
29         }
30 
31         int all=sum/2;
32         int cnt=0;
33         for(int i=1;i<=6;i++)
34         {

35             if(a[i])
36             {
37                 for(int k=1;k<=a[i];k*=2)
38                 {
39                     va[cnt++]=k*i;
40                     a[i]-=k;
41                 }
42                 if(a[i]>0)
43                 {
44                     va[cnt++]=a[i]*i;
45                 }
46             }
47         }
48         memset(dp,0,sizeof(dp));
49         for(int i=0;i<cnt;i++)
50         {
51             for(int j=all;j>=va[i];j--)
52             {
53                 if(j-va[i]>=0)
54                 dp[j]=max(dp[j],dp[j-va[i]]+va[i]);
55             }
56         }
57         if(all==dp[all])
58         printf("Can be divided.\n\n");
59         else
60         printf("Can‘t be divided.\n\n");
61     }
62     return 0;
63 }