HDOJ 1171 Big Event in HDU (多重背包)
http://acm.hdu.edu.cn/showproblem.php?pid=1171
题意：已知有N种价值的物品，每种价值为v，有m件，现将物品分为两部分，使每部分价值尽量相等（如果不等则使第一部分大于第二部分）。
思路：背包体积为总价值的一半，然后用多重背包求最大值。
#include<stdio.h>#include<string.h>int bag[333333];int main(){int n,w[555];while(scanf("%d",&n)&&(n>=0)){int i,j,sum=0,size,k=1;;for(i=1;i<=n;i++){int tmp,v,m;scanf("%d %d",&v,&m);sum+=v*m;tmp=1;while(m>tmp){w[k++]=tmp*v;m-=tmp;tmp<<=1;}w[k++]=m*v;}size=sum/2;memset(bag,0,sizeof(bag));for(i=1;i<k;i++)for(j=size;j>=w[i];j--)if(bag[j]<bag[j-w[i]]+w[i])bag[j]=bag[j-w[i]]+w[i];printf("%d %d\n",sum-bag[size],bag[size]);}return 0;}