1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5  6 int v[7] , ans , k; 7 int dp[500000]; 8 //0-1背包 9 void zeroPack(int w , int v)10 {11     for(int i = ans ; i>=w ; i--)12         dp[i] = max(dp[i] , dp[i - w]+v);13 }14 //完全背包15 void compPack(int w , int v)16 {17     for(int i = w ; i<=ans ; i++)18         dp[i] = max(dp[i] , dp[i - w]+v);19 }20 //多重背包21 void multiPack(int n , int w , int v)22 {23     if(n*v > ans) compPack(w , v);24     else{25         int t = 1;26         while(n >= t){27             zeroPack(t*w , t*v);28             n-=t;29             t <<= 1;30         }31         if(n > 0) zeroPack(n*w , n*v);32     }33 }34 35 int main()36 {37     int cas = 0;38     while(1){39         ans = 0;40         k = 0;41         for(int i = 0 ; i<6 ; i++){42             scanf("%d" , v+i);43             ans += v[i]*(i+1);44         }45         if(ans == 0) break;46 47         if(ans & 1){48             printf("Collection #%d:\n" , ++cas);49             puts("Can‘t be divided.");50             puts("");51             continue;52         }53         ans >>= 1;54         memset(dp , 0 , sizeof(dp));55         for(int i = 0 ; i<6 ; i++){56             multiPack(v[i] , i+1 , i+1);57         }58 59         if(dp[ans] == ans){60             printf("Collection #%d:\nCan be divided.\n\n" , ++cas);61         }62         else printf("Collection #%d:\nCan‘t be divided.\n\n" , ++cas);63     }64     return 0;65 }