hdu 1117 Big Event in HDU（多重背包）
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
Sample Output
20 1040 40
这是多重背包，背包的上线时total/2;
代码：
#include<iostream>using namespace std;int dp[250025];int v[100],num[100];int max( int a,int b ) { return a > b ? a : b; } int main(){ int i,j,n,sum,cnt,k; while(scanf("%d",&n),n>0) { cnt=0; for(i=0;i<n;i++){ scanf("%d%d",&v[i],&num[i]);cnt+=v[i]*num[i];} memset(dp,0,sizeof(dp)); sum=cnt/2; for(i=0;i<n;i++) for(j=0;j<num[i];j++) for(k=sum;k>=v[i];k-=v[i]) dp[k]=max(dp[k],dp[k-v[i]]+v[i]); if(cnt-dp[sum]>dp[sum]) printf("%d %d\n",cnt-dp[sum],dp[sum]); else printf("%d %d\n",dp[sum],cnt-dp[sum]); } return 0;}