#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAX 250010 //注意得开大点int c1[MAX], c2[MAX];int num[55], val[55];int main(){ int n; while( scanf("%d", &n)!=EOF && n>0) { int total = 0; memset(val, 0, sizeof(val) ); memset(num, 0, sizeof(num) ); for(int i=0; i<n; i++) {scanf("%d %d", &val[i], &num[i]); total += val[i]*num[i];} memset(c1, 0, sizeof(c1) ); memset(c2, 0, sizeof(c2) ); for(int i=0; i<=num[0]*val[0]; i+=val[0]) //第一项全部至0 c1[i]=1; int len = num[0]*val[0]; for(int i=1; i<n; i++) { for(int j=0; j<=len; j++) for(int k=0; k<=num[i]*val[i]; k+=val[i]) c2[k+j] += c1[j]; //一定得是累加 len += val[i]*num[i]; for(int j=0; j<=len; j++) //结束一轮运算赋值 { c1[j] = c2[j]; c2[j] = 0; } } /* 如果我们往递减的方向遍历就不会重叠误差而导致影响的那个”点”(真实值)，也就不用单独考虑total/2是否刚好整除了。 比如有一组样例就可以说明这一点： 2 4 1 1 1 */ /*for(int i=total/2;i<=total;i++) { if(c1[i]) { printf("%d %d
",i,total-i); break; } } 错的*/ for(int i= total/2; i>=0; --i) if(c1[i] != 0) { printf("%d %d
", total-i, i); break; } } return 0;}