题目分析：很裸的完全背包！用sum做总价值之和，C=sum/2 做背包容量，另外用价值做背包的体积，就转化为多重背包，就是价值为w[i],体积v[i],数量为n[i]的N个背包放到容量为C=sum/2，的背包中，所的到 的最大价值，A所得的价值为sum-dp[C],B 为dp[C]
#include<iostream>
#include<cstdio>
using namespace std;
int v[1010],w[1010],n[1010],dp[1000000];
int main()
{
int N;
while(scanf("%d",&N)!=EOF)
{
if(N<0)
break;
int sum=0,C;
for(int i=1;i<=N;i++)
{
scanf("%d %d",&w[i],&n[i]);
v[i]=w[i];
sum+=w[i]*n[i];
}
C=sum/2;
memset(dp,0,sizeof(dp));
//dp[i][j]代表吧前i件物品放到容量为j的背包里所获得的最大价值
for(int i=1;i<=N;i++)//多重背包
{
if(n[i]*w[i]>=C)
for(int j=v[i];j<=C;j++)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
int k=1;
while(k<n[i])
{
for(int j=C;j>=k*v[i];j--)
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
n[i]-=k;
k*=2;
}
for(int j=C;j>=n[i]*v[i];j--)
dp[j]=max(dp[j],dp[j-n[i]*v[i]]+n[i]*w[i]);
}
int ans=sum-dp[C];
printf("%d %d\n",ans,dp[C]);
}
system("pause");
return 0;
}