HDOJ 1059 Dividing (多重背包)
http://acm.hdu.edu.cn/showproblem.php?pid=1059
题意：有一些被划分为1-6价值的石头，并一直每个价值有多少块，求可否将石头分成两份且价值相等。
思路：求出总价值，除2。转化为大小为（总价值/2）的背包可否恰好装满的问题。
#include<stdio.h>#include<limits.h>#define maxn 444444//(1+2+3+4+5+6)*20000=420000int bag[maxn]={0};int main(){int w[111],n[7],cnt=1;//2^15(>20000)*6=90while(scanf("%d%d%d%d%d%d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6])&&(n[1]||n[2]||n[3]||n[4]||n[5]||n[6])){int i,j,k=1,sum=0;printf("Collection #%d:\n",cnt++);for(i=1;i<=6;i++){int tmp=1;sum+=n[i]*i;while(n[i]>tmp){w[k++]=tmp*i;n[i]-=tmp;tmp<<=1;}w[k++]=n[i]*i;}if(sum&1){printf("Can't be divided.\n\n");continue;}sum/=2;for(i=1;i<=sum;i++)bag[i]=INT_MIN;for(i=1;i<k;i++){for(j=sum;j>=w[i];j--){if(bag[j]<bag[j-w[i]]+w[i])bag[j]=bag[j-w[i]]+w[i];}}if(bag[sum]>=0)printf("Can be divided.\n\n");elseprintf("Can't be divided.\n\n");}return 0;}