Dividing （hdu 1059 多重背包）

Dividing

Sample Input

1 0 1 2 0 0　　　价值为1，2，3，4，5，6的物品数目分别为 1 0 1 2 0 0，求能否将这些物品按价值分为两堆，转化为多重背包。
1 0 0 0 1 1
0 0 0 0 0 0

Sample Output

Collection #1: Can't be divided.

Collection #2: Can be divided.

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 int dp[120005];
 7 int a[7];
 8 int value=0;
 9 void completepack(int cost,int weight)        //代价cost换取价值weight 完全背包
10 {
11     for(int i=cost;i<=value;i++)
12         dp[i]=max(dp[i],dp[i-cost]+weight);
13 }
14 void zeroonepack(int cost,int weight)        
15 {
16     for(int i=value;i>=cost;i--)
17         dp[i]=max(dp[i],dp[i-cost]+weight);
18 }
19 void multiplepack(int cost,int weight,int amount)        
20 {
21     int t=1;
22     if(amount*cost>=value)        
23         completepack(cost,weight);        
24     else
25     {
26         while(t<amount)
27         {
28             zeroonepack(cost*t,cost*t);            
29             amount-=t;
30             t<<=1;
31         }
32         if(amount)
33             zeroonepack(cost*amount,cost*amount);
34     }
35 }
36 int main()
37 {
38     int i,j,t=0;
39     freopen("in.txt","r",stdin);
40     while(scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6]))
41     {
42         int sum=0;
43         for(i=1;i<=6;i++)
44             sum+=a[i]*i;
45         value=sum/2;
46         if(sum==0)
47             break;
48         printf("Collection #%d:
",++t);
49         if(sum%2)
50         {
51             printf("Can't be divided.

");
52             continue;
53         }
54         memset(dp,0,sizeof(dp));
55         for(i=1;i<=6;i++)
56         {
57             if(a[i])
58                 multiplepack(i,i,a[i]);
59         }
60         if(dp[value]==value)
61             printf("Can be divided.

");
62         else
63             printf("Can't be divided.

");
64     }
65     return 0;
66 }