完全背包的二进制优化

1 #include
2 #include <string.h>
3 #include
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)
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 }