HDOJ1171 这道题之前是用01背包做的，现在用多重背包的做法解决。这其实更符合题意（个人认为）

代码如下：

版本三(二进制优化的多重背包，93ms)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <algorithm>
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=1000000+5; 
int n;
int v[5005],m[5005];
int dp[maxn];
void zero_one(int cost,int val,int vtot)
{
    for(int j=vtot;j>=cost;j--)
        dp[j]=max(dp[j],dp[j-cost]+val);
}
void complete(int cost,int val,int vtot)
{
    for(int j=cost;j<=vtot;j++)
        dp[j]=max(dp[j],dp[j-cost]+val);
}
void multiple(int cost,int val,int num,int vtot)
{
    int k;
    if(cost*num>=vtot)
    {
        complete(cost,val,vtot);
        return ;
    }
    k=1;
    while(k<num)
    {
        zero_one(k*cost,k*val,vtot);
        num-=k;
        k<<=1;
    }
    zero_one(num*cost,num*val,vtot);
}
int main()
{
    while(scanf("%d",&n)!=EOF&&n>0)
    {    
        mst(v,0);mst(m,0);mst(dp,0);
        int sum=0;
        for(int i=0;i<n;i++)
        {
            int val,num;
            scanf("%d %d",&val,&num);
            sum+=val*num;
            v[i]=val;m[i]=num;
        }
        for(int i=0;i<n;i++)
            multiple(v[i],v[i],m[i],sum/2);
        int a=sum-dp[sum/2];
        int b=dp[sum/2];
        cout<<a<<" "<<b<<endl;
    }
}

二进制优化的模板→多重背包二进制优化模板分析