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

 /*问你能不能将给出的资源平分成两半，那么我们就以一半为背包，运行多重背包模版

 但是注意了，由于个数过大，直接运行会超时，所以要用二进制拆分每种的个数*/

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 int w[],vr[],dp[];

 int a[],v[];

 int numw;

 void cf(int n,int ok)

 {

     int i,j,sum,e;

     e=sum=;

     while(sum<=n)

     {

         vr[numw]=v[ok];

         w[numw++]=e;

         e*=;

         sum+=e;

     }

     if(n-(sum-e)>)

     {

         w[numw]=n-(sum-e);

         vr[numw]=v[ok];

         numw++;

     }

 }

 int main()

 {

     int i,j,n,m,k;

     int n1,n2,n3,n4,n5,n6;

     int cas=;

     while(scanf("%d%d%d%d%d%d",&n1,&n2,&n3,&n4,&n5,&n6)!=EOF)

     {

         if(n1== && n2== && n3== && n4== && n5== && n6==) break;

         int num=;

         if(n1!=) { a[num]=n1; v[num++]=;}

         if(n2!=) { a[num]=n2; v[num++]=;}

         if(n3!=) { a[num]=n3; v[num++]=;}

         if(n4!=) { a[num]=n4; v[num++]=;}

         if(n5!=) { a[num]=n5; v[num++]=;}

         if(n6!=) { a[num]=n6; v[num++]=;}

         int sum=;

         //printf("%d\n",num);

         for(i=;i<num;i++)

         {

             sum=sum+a[i]*v[i];

         }

         if(sum==) break;

          if(sum%)

          {

              printf("Collection #%d:\n",++cas);

              printf("Can't be divided.\n\n");

              continue;

          }

         numw=;

         for(i=;i<=sum/;i++)

         dp[i]=;

         for(i=;i<num;i++)

         {

            cf(a[i],i);

         }

         for(i=;i<numw;i++)

         for(j=sum/;j>=w[i]*vr[i];j--)

         dp[j]=max(dp[j],dp[j-w[i]*vr[i]]+w[i]*vr[i]);

         printf("Collection #%d:\n",++cas);

         if(dp[sum/]==sum-dp[sum/]) printf("Can be divided.\n\n");

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

     }

     return ;

 }