1 #include<iostream> 2  using namespace std; 3  const int maxn = 10; 4  int n[ maxn ]; 5  int sumv,V; 6  int dp[ 60011 ]; 7  int max(int a,int b) 8  { 9      return a>b?a:b ;10  }11  void bag01( int cost,int weight ){12      for( int i=V;i>=cost;i-- ){13          dp[ i ]=max(dp[ i ],dp[ i-cost ]+weight);14      }15      return ;16  }17  void bagall( int cost ,int weight ){18     for( int i=cost;i<=V;i++ ){19         dp[ i ]=max( dp[ i ],dp[ i-cost ]+weight);20     }21      return ;22  }23  24 void mul_bag( int cost,int weight,int num ){25      if( cost*num>=V ){26          bagall( cost,weight );27          return ;28     }29      int k=1;30      while( k<=num ){31          bag01( k*cost,k*weight );32          num-=k;33          k*=2;34     }35      bag01( num*cost,num*weight );36      return ;37  }38  int main()39  {40      int i,k=1;41      while(cin>>n[0]>>n[1]>>n[2]>>n[3]>>n[4]>>n[5],n[0]+n[1]+n[2]+n[3]+n[4]+n[5])42      {43          memset(dp,0,sizeof(dp));44         sumv=n[0]+n[1]*2+n[2]*3+n[3]*4+n[4]*5+n[5]*6;45          if(sumv%2==1)46          {47              printf("Collection #%d:\nCan‘t be divided.\n\n",k++);48              continue;49          }50          V=sumv/2;51         for(i=0;i<6;i++)52         {53              if(n[i]) mul_bag(i+1,i+1,n[i]);54         }55         if(V==dp[V]) printf("Collection #%d:\nCan be divided.\n\n",k++);56          else printf("Collection #%d:\nCan‘t be divided.\n\n",k++);57      }58      return 0;59  }

 1 #include<iostream>   2 #include<cstdio>   3 using namespace std;   4 int halfvalue;   5 int a[7],sum,SUM,flag;   6    7 void dfs(int v,int pre)  8 {                         9     if(flag==1)    10         return;  11     if(v==halfvalue)  12     {  13         flag=1;  14         return;  15     }  16     for(int i=pre;i>=1;i--)  17     {  18        if(a[i]!=0)  19        {  20            if(v+i<=halfvalue)  21            {  22                a[i]--;//用过了就要减 23                dfs(v+i,i);  24                if(flag==1)  25                    break;  26            }  27        }  28     }  29     return;  30 }  31 int main()  32 {  33     int c=1;  34     while(1)  35     {  36         sum=0,SUM=0;  37         for(int i=1;i<=6;i++)  38         {  39             scanf("%d",&a[i]);  40             sum+=a[i];  41             SUM+=i*a[i];  42         }  43         if(sum==0)  44             break;  45         if(SUM%2==1)  46         {  47             printf("Collection #%d:\nCan‘t be divided.\n\n",c++);  48             continue;  49         }  50         flag=0;  51         halfvalue=http://www.mamicode.com/SUM/2;  52         dfs(0,6);  53         if(flag==1)  54             printf("Collection #%d:\nCan be divided.\n\n",c++);  55         else  56             printf("Collection #%d:\nCan‘t be divided.\n\n",c++);  57     }  58     system("pause");  59     return 0;  60 }