HDU1059 二进制拆分优化多重背包

 1 /*问你能不能将给出的资源平分成两半，那么我们就以一半为背包，运行多重背包模版
 2 但是注意了，由于个数过大，直接运行会超时，所以要用二进制拆分每种的个数*/
 3 #include<stdio.h>
 4 #include<string.h>
 5 #include<algorithm>
 6 using namespace std;
 7 int w[120005],vr[120005],dp[120005];
 8 int a[7],v[7];
 9 int numw;
10 void cf(int n,int ok)
11 {
12     int i,j,sum,e;
13     e=sum=1;
14     while(sum<=n)
15     {
16         vr[numw]=v[ok];
17         w[numw++]=e;
18         e*=2;
19         sum+=e;
20     }
21     if(n-(sum-e)>0)
22     {
23         w[numw]=n-(sum-e);
24         vr[numw]=v[ok];
25         numw++;
26     }
27 }
28 int main()
29 {
30     int i,j,n,m,k;
31     int n1,n2,n3,n4,n5,n6;
32     int cas=0;
33     while(scanf("%d%d%d%d%d%d",&n1,&n2,&n3,&n4,&n5,&n6)!=EOF)
34     {
35         if(n1==0 && n2==0 && n3==0 && n4==0 && n5==0 && n6==0) break;
36         int num=1;
37         if(n1!=0) { a[num]=n1; v[num++]=1;}
38         if(n2!=0) { a[num]=n2; v[num++]=2;}
39         if(n3!=0) { a[num]=n3; v[num++]=3;}
40         if(n4!=0) { a[num]=n4; v[num++]=4;}
41         if(n5!=0) { a[num]=n5; v[num++]=5;}
42         if(n6!=0) { a[num]=n6; v[num++]=6;}
43         int sum=0;
44         //printf("%d
",num);
45         for(i=1;i<num;i++)
46         {
47             sum=sum+a[i]*v[i];
48         }
49         if(sum==0) break;
50          if(sum%2)
51          {
52              printf("Collection #%d:
",++cas);
53              printf("Can't be divided.

");
54              continue;
55          }
56         numw=1;
57         for(i=0;i<=sum/2;i++)
58         dp[i]=0;
59         for(i=1;i<num;i++)
60         {
61            cf(a[i],i);
62         }
63         for(i=1;i<numw;i++)
64         for(j=sum/2;j>=w[i]*vr[i];j--)
65         dp[j]=max(dp[j],dp[j-w[i]*vr[i]]+w[i]*vr[i]);
66         printf("Collection #%d:
",++cas);
67         if(dp[sum/2]==sum-dp[sum/2]) printf("Can be divided.

");
68         else printf("Can't be divided.

");
69     }
70     return 0;
71 }