题意：有分别价值为1,2,3,4,5,6的6种物品，输入6个数字，表示相应价值的物品的数量，问一下能不能将物品分成两份，是两份的总价值相等，其中一个物品不能切开，只能分给其中的某一方，当输入六个0是（即没有物品了），这程序结束，总物品的总个数不超过20000。
做法：
多重背包+二进制优化。
注意：
1，注意初始化dp为-1，dp[0]=0;
2，注意理清各个变量代表的含义。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#define INT_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{int u;int v;int w;bool friend operator < (node a, node b){return a.w < b.w;}
}edge[1001];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
int n[7];
int w[7];
int c[7];
int dp[1000001];
int leap=0;
int s;
void pack01(int cost ,int weight)
{int v;for(v=s/2;v>=weight;v--){dp[v]=max(dp[v],dp[v-weight]+cost);if(dp[v]==s/2){leap=1;return ;}}
}
void mul(int cost,int num)
{if(cost*num>s/2){num=(s/2)/cost;}int k=1;while(k<num){pack01(cost*k,cost*k);if(leap)return ;num=num-k;k=k*2;}pack01(cost*num,cost*num);
}
int main()
{int i;for(i=1;i<=6;i++)w[i]=i,c[i]=1;int t;t=0;while(1){s=0;for(i=1;i<=6;i++){scanf("%d",&n[i]);s+=n[i]*w[i];}if(s==0)break;t++;leap=0;printf("Collection #%d:\n",t);if(s%2==0){memset(dp,-1,sizeof(dp));dp[0]=0;for(i=1;i<=6;i++){mul(w[i],n[i]);if(leap)break;}}if(leap)printf("Can be divided.\n\n");elseprintf("Can't be divided.\n\n");}return 0;
}