http://acm.hdu.edu.cn/showproblem.php?pid=1171
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #define max(x,y) x>y?x:y 4 int main() 5 { 6 int n; 7 int m; 8 int sum; 9 int i,j,jj; 10 int a[55]; 11 int w[5500]; 12 int f[250000]; 13 while(~scanf("%d",&n)&&n>0) 14 { 15 memset(f,0,sizeof(f)); 16 jj=0; 17 sum=0; 18 for(i=0;i<n;i++) 19 { 20 21 scanf("%d%d",&a[i],&m); 22 for(j=0;j<m;j++) 23 { 24 sum+=a[i]; 25 w[jj++]=a[i]; 26 } 27 28 } 29 for(i=0;i<jj;i++) 30 { 31 for(j=sum/2;j>=w[i];j--) 32 { 33 f[j]=max(f[j],f[j-w[i]]+w[i]); 34 } 35 } 36 printf("%d %d\n",sum-f[sum/2],f[sum/2]); 37 } 38 }