#include<stdio.h>
#include<string.h>
int v[55],num[55];
int a[300000],b[200000];
int main()
{
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        if(n<0)break;
        int sum=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&v[i],&num[i]);
            sum+=v[i]*num[i];

        }
         int d=(sum+1)/2;

        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(i=0;i<=num[1]*v[1];i+=v[1])
        {
            a[i]=1;
        }
        int h=num[1]*v[1];
        for(i=2;i<=n;i++)
        {

            for(j=0;j<=h;j++)
            {
                for(k=0;k<=num[i]*v[i];k+=v[i])
                {
                    b[k+j]+=a[j];
                }
            }
            
            h+=num[i]*v[i];
           for(j=0;j<=h;j++)
           {
               a[j]=b[j];
               b[j]=0;
           }
        }
        if(a[d]!=0)
        {
            printf("%d %d\n",d,sum-d);
        }
        else
        {
            for(i=d;i<=sum;i++)
            {
                if(a[i]!=0)break;
            }
            printf("%d %d\n",i,sum-i);
        }


    }
}

优质内容筛选与推荐>>
1、搜索所有的路径-矩阵运算-暴力-ACM
2、[POJ2356]Find a multiple 题解（鸽巢原理）
3、在触发器中，当“IsMouseOver”属性=true时，设置当前控件的高亮选中效果
4、拿下shell后提权技巧
5、markdown、git