学步园

      hdu 1059 Dividing

   有价值为1,2,3,4,5,6的物品，每种价值的物品分别n1,n2,......n6件，问是否能将这些物品平分给两个人

#include <iostream>
#include <cstring>
using namespace std;
#define max(a, b) ((a) > (b) ? (a) : (b))
int f[7], w[23000], dp[50004];
int main()
{
    int i, j, k, count;
    count = 0;
    while (cin>>f[1]>>f[2]>>f[3]>>f[4]>>f[5]>>f[6] &&(f[1]+f[2]+f[3]+f[4]+f[5]+f[6]))
    {
        count++;
        int sum = k = 0;
        memset(dp, 0, sizeof(dp));
        for (i=1; i<=6; i++)
         {
             sum += f[i] * i;
             for (j=1; j<=f[i]; j<<=1)//将物品进行二进制转化
             {
                 w[k++] = j * i;
                 f[i] -= j;
             }
             if (f[i]>0)
                w[k++] = f[i] * i;
         }
         int mid = sum / 2;
         for (i=0; i<k; i++)
            for (j=mid; j>=w[i]; j--)
              dp[j] = max(dp[j], dp[j-w[i]]+w[i]);
         cout<<"Collection #"<<count<<":"<<endl;
         if (dp[mid]!=sum-mid)//不能用if(dp[mid]!=mid),因为sum/2时可能除不尽，存在误差
            cout<<"Can't be divided.\n"<<endl;
         else
            cout<<"Can be divided.\n"<<endl;
    }
    return 0;
}