题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1171
此题让我们求出最好的分配方式使得两边的差最小。
此题有两种做法，第一种是用母函数，第二种是用01背包。
1.母函数：
进行母函数的算法后，我们从中间开始找，第一个找到的不为0的便就是我们要找的。
2.背包：
背包的处理就只需要找到我们V/2的容积下最大获得的价值即可。
#include <stdio.h>//母函数
#include <string.h>
struct Point
{int v,num;
}dp[60];
int c1[260000],c2[260000];
int main()
{int n,i,j,k;while(scanf("%d",&n)&&n>0){int sum=0;for(i=1;i<=n;i++){scanf("%d%d",&dp[i].v,&dp[i].num);sum+=dp[i].v*dp[i].num;}int mid=sum/2;memset(c1,0,sizeof(c1));memset(c2,0,sizeof(c2));for(i=0;i<=mid&&((i/dp[1].v)<=dp[1].num);i+=dp[1].v)c1[i]=1;for(i=2;i<=n;i++){for(j=0;j<=mid;j++){for(k=0;k+j<=mid&&(k/dp[i].v)<=dp[i].num;k+=dp[i].v)c2[j+k]+=c1[j];}for(j=0;j<=mid;j++){c1[j]=c2[j]; c2[j]=0;}}for(i=mid;i>=0;i--){if(c1[i]) break;}printf("%d %d\n",sum-i,i);}return 0;
}#include <stdio.h>//背包
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN=250010;
int dp[MAXN];
int nValue;
void ZeroOnePack(int cost,int weight)
{for(int i=nValue;i>=cost;i--)dp[i]=max(dp[i],dp[i-cost]+weight);
}
void CompletePack(int cost,int weight)
{for(int i=cost;i<=nValue;i++)dp[i]=max(dp[i],dp[i-cost]+weight);
}
void MultiplePack(int cost,int weight,int amount)
{if(cost*amount>=nValue)CompletePack(cost,weight);else{int k=1;while(k<amount){ZeroOnePack(k*cost,k*weight);amount-=k;k<<=1;}ZeroOnePack(amount*cost,amount*weight);}
}
int a[55],b[55];
int main()
{int n;while(scanf("%d",&n)==1){if(n<0)break;nValue=0;for(int i=0;i<n;i++){scanf("%d%d",&a[i],&b[i]);nValue+=a[i]*b[i];}memset(dp,0,sizeof(dp));for(int i=0;i<n;i++){if(b[i]==1)ZeroOnePack(a[i],a[i]);else MultiplePack(a[i],a[i],b[i]);}int t=nValue/2;while(dp[t]!=t)t--;printf("%d %d\n",nValue-t,t);}return 0;
}