题意：价值分别为1，2，3，4，5，6的物品个数分别为a[1],a[2],a[3],a[4],a[5],a[6],问能不能分成两堆价值相等的。
解法：转化成多重背包
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std; int dp[];
int a[]; int nValue; //0-1背包，代价为cost,获得的价值为weight
void ZeroOnePack(int cost,int weight)
{
for(int i=nValue;i>=cost;i--)
dp[i]=max(dp[i],dp[i-cost]+weight);
} //完全背包，代价为cost,获得的价值为weight
void CompletePack(int cost,int weight)
{
for(int i=cost;i<=nValue;i++)
dp[i]=max(dp[i],dp[i-cost]+weight);
} //多重背包
void MultiplePack(int cost,int weight,int amount)
{
if(cost*amount>=nValue) CompletePack(cost,weight);
else
{
int k=;
while(k<amount)
{
ZeroOnePack(k*cost,k*weight);
amount-=k;
k<<=;
}
ZeroOnePack(amount*cost,amount*weight);//这个不要忘记了，经常掉了
}
} int main()
{
int iCase=;
while()
{
iCase++;
int tol=;
for(int i=;i<=;i++)
{
scanf("%d",&a[i]);
tol+=i*a[i];
}
if(tol==)break;
printf("Collection #%d:\n",iCase);
if(tol%!=)
{
printf("Can't be divided.\n\n");
continue;
}
else
{
nValue=tol/; }
memset(dp,,sizeof(dp));
for(int i=;i<=;i++)
MultiplePack(i,i,a[i]);
if(dp[nValue]==nValue)printf("Can be divided.\n\n");
else printf("Can't be divided.\n\n");
}
return ;
}