把东西分为两部分尽量相等,不相等则差值最小,
#include<stdio.h> #include<string.h> int f[250005]; int max(int a,int b) { if(a>b)return a; return b; } int main() { int w[5050],n,i,j,v,a,k,sum,half; while(scanf("%d",&n),n>0) { memset(f,0,sizeof(f)); sum=k=0; for(i=0;i<n;i++) { scanf("%d%d",&v,&a); for(j=1;j<=a;j++) { w[k++]=v;sum=sum+v; } } n=k;half=sum/2; for(i=0;i<n;i++) for(j=half;j>=w[i];j--) f[j]=max(f[j-w[i]]+w[i],f[j]); printf("%d %d\n",max(f[half],sum-f[half]),sum-max(f[half],sum-f[half])); } return 0; }