题意：给出价值为1,2,3,4,5,6的6种物品数量，问是否能将物品分成两份，使两份的总价值相等。
思路:求出总价值除二，做多重背包，需要二进制优化。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; int n[7];
int v,sum;
bool flag;
int dp[100000]; /*完全背包*/
void CompletePack(int cost,int weight)
{
for(int i=cost;i<=v;i++)
{
dp[i]=max(dp[i],dp[i-cost]+weight);
if(dp[i]==v) //剪枝
{
flag=true;
return;
}
} return;
}
/*01背包*/
void ZeroOnePack(int cost,int weight)
{
for(int i=v;i>=cost;i--)
{
dp[i]=max(dp[i],dp[i-cost]+weight);
if(dp[i]==v) //剪枝
{
flag=true;
return;
}
}
return;
} /*多重背包*/
void MultiplePack(int cost,int weight,int amount)
{
if(cost*amount>=v)
{
CompletePack(cost,weight);
return;
} if(flag) //剪枝
return; /*二进制优化*/
int k=1;
while(k<amount)
{
ZeroOnePack(k*cost,k*weight); if(flag)
return; amount-=k;
k*=2;
}
ZeroOnePack(amount*cost,amount*weight); return;
} int main(int i)
{
int test=1;
while(scanf("%d%d%d%d%d%d", &n[1], &n[2], &n[3], &n[4], &n[5], &n[6])!=EOF)
{
sum=0; //物品总价值 for(i=1;i<=6;i++)
sum+=i*n[i]; if(sum==0)
break; if(sum%2)
{
cout<<"Collection #"<<test++<<':'<<endl;
cout<<"Can't be divided."<<endl<<endl;
continue;
} v=sum/2;
memset(dp,-1,sizeof(dp));
dp[0]=0;
flag=false; for(i=1;i<=6;i++)
{
MultiplePack(i,i,n[i]); if(flag) //剪枝
break;
} if(flag)
{
cout<<"Collection #"<<test++<<':'<<endl;
cout<<"Can be divided."<<endl<<endl;
continue;
}
else
{
cout<<"Collection #"<<test++<<':'<<endl;
cout<<"Can't be divided."<<endl<<endl;
continue;
}
printf("\n");
}
return 0;
}