zoj 1149 && hdu 1059 && poj 1014 Dividing

多重背包转化为01背包。

学习了二进制在背包问题中的应用。。。爽！！！！！

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int a[8];
int bag[120005];
int v[120005],cc,sum;

void DP()
{
    int i,j;
    memset(bag,0,sizeof(bag));
    for(i=0;i<cc;i++)
    {
        for(j=sum;j>=v[i];j--)
        {
            bag[j]=max(bag[j],bag[j-v[i]]+v[i]);
        }
    }
}

int main()
{
    int cas=1,cnt,tmp;
    while(scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6])!=EOF)
    {
        if(a[1]+a[2]+a[3]+a[4]+a[5]+a[6]==0)
            break;
        printf("Collection #%d:\n",cas++);
        cnt=0,sum=0;
        for(int i=1;i<=6;i++)
            sum+=a[i]*i;
        if(sum%2)
        {
            printf("Can‘t be divided.\n\n");
            continue;
        }
        sum=sum/2,cc=0;
        for(int i=1;i<=6;i++)
        {
            if(a[i]==0) continue;
            tmp=1;
            while(a[i]>tmp)
            {
                v[cc++]=tmp*i;
                a[i]-=tmp;
                tmp=tmp*2;
            }
            if(a[i])
                v[cc++]=a[i]*i;
        }
        DP();
        if(bag[sum]!=sum)
            printf("Can‘t be divided.\n\n");
        else
            printf("Can be divided.\n\n");
    }
    return 0;
}

zoj 1149 && hdu 1059 && poj 1014 Dividing

原文：http://blog.csdn.net/u012841845/article/details/18504851