题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1059
题目链接：http://poj.org/problem?id=1014
题意：给我们6种物品，其价值分别是1、2、3、4、5、6，给出我们这些物品每一种的数量，问我们可不可以将其分成价值一模一样的两堆。
此题的做法就是运用典型的多重背包问题，最后只需要判断是否满足dp[sum/2] == sum/2就可以了。
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const int maxn = 20000*6+5;
int dp[maxn],v,n[10];
void ZeroOnePack(int cost,int value)
{for(int i=v; i>=cost; i--)dp[i]=max(dp[i],dp[i-cost]+value);
}
void CompletePack(int cost,int value)
{for(int i=cost; i<=v; i++)dp[i]=max(dp[i],dp[i-cost]+value);
}
void MultiPack(int cost,int value,int num)
{int k;if(num*cost>=v)CompletePack(cost,value);else{k=1;while(num>k){ ZeroOnePack(k*cost,k*value);num-=k;k*=2;}ZeroOnePack(num*cost,num*value);}
}
int main()
{int k = 1;while(scanf("%d",&n[1])!=EOF){int sum = n[1]*1;for(int i=2; i<=6; i++){scanf("%d",&n[i]);sum += n[i]*i;}if(sum==0) break;if(sum&1){printf("Collection #%d:\nCan't be divided.\n\n",k++);continue;}v = sum/2;memset(dp,0,sizeof(dp));for(int i=1; i<=6; i++)MultiPack(i,i,n[i]);if(dp[v] == v)printf("Collection #%d:\nCan be divided.\n\n",k++);else printf("Collection #%d:\nCan't be divided.\n\n",k++);}
}