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.

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 int dp[];

 int a[];

 int value=;

 void completepack(int cost,int weight)        //代价cost换取价值weight 完全背包

 {

     for(int i=cost;i<=value;i++)

         dp[i]=max(dp[i],dp[i-cost]+weight);

 }

 void zeroonepack(int cost,int weight)

 {

     for(int i=value;i>=cost;i--)

         dp[i]=max(dp[i],dp[i-cost]+weight);

 }

 void multiplepack(int cost,int weight,int amount)

 {

     int t=;

     if(amount*cost>=value)

         completepack(cost,weight);

     else

     {

         while(t<amount)

         {

             zeroonepack(cost*t,cost*t);

             amount-=t;

             t<<=;

         }

         if(amount)

             zeroonepack(cost*amount,cost*amount);

     }

 }

 int main()

 {

     int i,j,t=;

     freopen("in.txt","r",stdin);

     while(scanf("%d%d%d%d%d%d",&a[],&a[],&a[],&a[],&a[],&a[]))

     {

         int sum=;

         for(i=;i<=;i++)

             sum+=a[i]*i;

         value=sum/;

         if(sum==)

             break;

         printf("Collection #%d:\n",++t);

         if(sum%)

         {

             printf("Can't be divided.\n\n");

             continue;

         }

         memset(dp,,sizeof(dp));

         for(i=;i<=;i++)

         {

             if(a[i])

                 multiplepack(i,i,a[i]);

         }

         if(dp[value]==value)

             printf("Can be divided.\n\n");

         else

             printf("Can't be divided.\n\n");

     }

     return ;

 }