分析：输入N种设备，已知设备的价值和数量。然后根据总价值将这批设备均分
给两个计算机系。输出包括这两个系分别获得设备的价值，要求计算机系的价值不小于软件系。
一个多重背包问题，将总价值的二分之一作为背包的容量，依次将设备选入背包。
背包可以是不装满的。
#include<stdio.h>
#include<string.h>
int dp[260000],V;
//01背包
void ZeroOnePack(int c,int w)
{
for(int i=V;i>=c;i--)
dp[i]=dp[i]>dp[i-c]+w?dp[i]:dp[i-c]+w;
}
//完全背包
void CompletePack(int c,int w)
{
for(int i=c;i<=V;i++)
dp[i]=dp[i]>dp[i-c]+w?dp[i]:dp[i-c]+w;
}
//多重背包
void MultiplePack(int c,int w,int amount)
{
if(c*amount>=V)
{
CompletePack(c,w);
return;
}
int k=1;
while (k<=amount)
{
ZeroOnePack(k*c,k*w);
amount-=k;
k*=2;
}
ZeroOnePack(amount*c,amount*w);
}
int main()
{
int N,v[51],n[51],sum;
while (scanf("%d",&N)!=EOF)
{
//获取数据
if(N<0) break;
sum=0;
for(int i=1;i<=N;i++)
{
scanf("%d%d",&v[i],&n[i]);
sum+=v[i]*n[i];
}
//初始化 背包可以不装满
V=sum/2;
memset(dp,0,sizeof(dp));
for(int i=1;i<=N;i++)
MultiplePack(v[i],v[i],n[i]);
//背包最后的总价值dp[v]<=sum/2 sum-dp[V]>=sum/2
printf("%d %d
",sum-dp[V],dp[V]);
}
return 0;
}