POJ 1014 Dividing

思路：多重背包，以总价值sum为背包容量，当dp[sum/2]=sum/2时满足平分条件

[cpp]
#include<stdio.h>
#include<string.h>
#define N 120001
#define max(a,b) (a)>(b)?(a):(b)
int dp[N];
void Cpack(int v,int sum)//完全背包
{
    int j;
   for(j=v;j<=sum;j++)
       dp[j]=max(dp[j],dp[j-v]+v);
}
void pack01(int w,int v,int sum)//01背包
{
   int j;
   for(j=sum;j>=w;j--)
       dp[j]=max(dp[j],dp[j-w]+v);
}
int main()
{
   int a[7],sum,i,c=1,k;
   while(1)
   {
      a[0]=sum=0;
      for(i=1;i<=6;i++)
      {
         scanf("%d",&a[i]);
         a[0]+=a[i];
         sum+=i*a[i];
      }
      if(sum==0) break;
      if(c!=1) printf("\n");
      printf("Collection #%d:\n",c++);
      if(sum%2==1) printf("Can't be divided.\n");//若sum为奇数，一定不可平分
      else
      {
          sum/=2;for(i=0;i<=sum;i++) dp[i]=0;
          for(i=1;i<=6;i++)
          {
             if(a[i]*i>=sum)
                Cpack(i,sum);
             else
             {
               k=1;
               while(k<a[i])
               {
                 pack01(k*i,k*i,sum);
                 a[i]-=k;
                 k*=2;
               }
               pack01(a[i]*i,a[i]*i,sum);
             }
          }
          if(dp[sum]==sum)
              printf("Can be divided.\n");
          else printf("Can't be divided.\n");
      }
   }
   return 0;
}

补充：软件开发 , C++ ,