也是多重背包可行性问题。
时间复杂度为 O（VN）。 V=背包容量。N=物品数量。
题意是说给你N个物品，每一个物品有不同的价值与数量。分给两个院。
问你怎么分配才让能让价值尽量相等。
跟我上一篇解题报告是一种类型。
以价值为费用，总价值的一半为背包容量。
只是物品有点多，直接开数组可能会超内存。我就用了滚动数组。
须要注意的是 you should guarantee that A is not less than B. 也就是说前面的比后面的大。
还有就是A test case starting with a negative integer terminates input and this test case is not to be processed.
以一个负数结束，我以为是-1.结果TLE一次。 改了之后就是 46 ms 。
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
int n,m;
int dp[2][256001];
int value[51],cot[51];
int main()
{
while(scanf("%d",&n),n>=0)
{
m=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&value[i],&cot[i]);
m+=value[i]*cot[i];
}
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
int tmp=m;
m=m/2+1;
int u,d;
for(int i=1;i<=n;i++)
{
u=(i-1)%2;
d=i%2;
for(int j=0;j<=m;j++)
{
if(dp[u][j]>=0)
dp[d][j]=cot[i];
else
dp[d][j]=-1;
}
for(int j=0;j<=m-value[i];j++)
{
if(dp[d][j]>0)
dp[d][j+value[i]]=max(dp[d][j+value[i]],dp[d][j]-1);
}
}
int a,b;
for(int i=m-1;i>=0;i--)
if(dp[n%2][i]>=0){a=i;break;}
b=tmp-a;
printf("%d %d
",b,a);
}
}