多重背包转化为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;
}