题目链接
转化为01背包,将背包上限定为sum/2
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[],dp[];
int main()
{
//freopen("in.txt","r",stdin);
int n,sum,i,j,k,v,m;
while(scanf("%d",&n)&&n>)
{
k=;
sum=;
memset(dp,,sizeof(dp));
for(i=;i<=n;i++)
{
scanf("%d%d",&v,&m);
while(m--)//转化成01背包
{
a[++k]=v;
sum+=v;
}
}
for(i=;i<=k;i++)
for(j=sum/;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
printf("%d %d\n",sum-dp[sum/],dp[sum/]);
}
return ;
}