学步园

题目分析：很裸的完全背包！用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;
}