1 #include <iostream> 2 using namespace std; 3 int arr[7]; 4 int sum, cnt = 1; 5  6 bool dp[7][120001]; 7  8 int main() 9 {10     cin.sync_with_stdio(false);11     while (cin >> arr[1])12     {13         sum = 0;14         sum += arr[1];15         for (int i = 2; i <= 6; i++)16         {17             cin >> arr[i];18             sum += arr[i] * i;19         }20         if (!sum)21             break;22         cout << "Collection #" << cnt++ << ":" << endl;23         if (sum & 1) {24             cout << "Can‘t be divided." << endl << endl;25             continue;26         }27         memset(dp, false, sizeof(dp));28         dp[0][0] = true;29         for (int i = 1; i <= 6; i++) {30             for (int j = sum; j >= 0; j--) {31                 if (dp[i - 1][j] == false) continue;32                 for (int k = 0; k <= arr[i]; k++) {33                     if (j + k*i >= sum) break;34                     if (dp[i][j + k*i]) break;35                     dp[i][j + k*i] = true;36                 }37             }38         }39         if (dp[6][sum / 2]) {40             cout << "Can be divided." << endl;41         }42         else {43             cout << "Can‘t be divided." << endl;44         }45         cout << endl;46     }47     return 0;48 }

 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5  6 int dp[100000]; 7  8 int main() 9 {10     int a[11],sum,v,i,j,k,cnt,cas = 1;11     while(~scanf("%d",&a[1]))12     {13         sum = a[1];14         for(i = 2;i<=6;i++)15         {16             scanf("%d",&a[i]);17             sum+=i*a[i];18         }19         if(!sum)20         break;21         printf("Collection #%d:\n",cas++);22         if(sum%2)//总和为奇数，必定不能平分23         {24             printf("Can‘t be divided.\n\n");25             continue;26         }27         v = sum/2;28         memset(dp,0,sizeof(dp));29         dp[0] = 1;30         for(i = 1;i<=6;i++)31         {32             if(!a[i])33             continue;34             for(j = 1;j<=a[i];j*=2)//二进制优化35             {36                 cnt = j*i;37                 for(k = v;k>=cnt;k--)38                 {39                     if(dp[k-cnt])//必须前面的能够放入背包，现在的才能放入背包40                     dp[k] = 1;41                 }42                 a[i]-=j;43             }44             cnt = a[i]*i;//剩下的45             if(cnt)46             {47                 for(k = v;k>=cnt;k--)48                 {49                     if(dp[k-cnt])50                     dp[k] = 1;51                 }52             }53         }54         if(dp[v])55         printf("Can be divided.\n\n");56         else57         printf("Can‘t be divided.\n\n");58     }59 60     return 0;61 }

 1 #include <iostream> 2 using namespace std; 3 int arr[7]; 4 int sum , cnt = 1; 5 bool flag; 6  7 void dfs( int pos , int cnt ) 8 { 9     if( cnt*2 == sum )10     {11         flag = true;12         return;13     }14     if( flag || cnt*2>sum )15     {16         return;17     }                18     for( int i = pos ; i>=1 ; i-- )19     {20         if( arr[i] )21         {22             if( cnt+i<=sum/2 )23             {24                 arr[i]--;25                 dfs( i , cnt+i );26                 if( flag )27                     break;28             }29         }    30     }31 }32 33 int main()34 {35     cin.sync_with_stdio(false);36     while( cin >> arr[1] )37     {38         flag =false;39         sum = 0;40         sum += arr[1];41         for( int i = 2 ; i<=6 ; i++ )42         {43             cin >> arr[i];44             sum += arr[i]*i;45         }46         if( !sum )47             break;48         cout << "Collection #"<< cnt++ <<":"<<endl;49         if( sum&1 )50         {51             cout << "Can‘t be divided." << endl << endl;52             continue;53         }54         dfs( 6 , 0 );55         if( flag )56             cout << "Can be divided." << endl << endl;57         else58             cout << "Can‘t be divided." << endl << endl;59     }60     return 0;61 }