母函数简单题
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 const int MAX=130000; 6 int c1[MAX],c2[MAX]; 7 8 struct { 9 int val,num; 10 }thing[55]; 11 int n; 12 13 int main(){ 14 while(scanf("%d",&n)!=EOF){ 15 if(n<0) break; 16 int sum=0,tmp; 17 for(int i=1;i<=n;i++){ 18 scanf("%d%d",&thing[i].val,&thing[i].num); 19 sum+=(thing[i].val*thing[i].num); 20 } 21 tmp=sum/2; 22 for(int i=0;i<=tmp;i++) 23 c1[i]=c2[i]=0; 24 for(int i=0,k=0; i<=tmp&&k<=thing[1].num; i+=thing[1].val,k++) 25 c1[i]=1; 26 for(int i=2;i<=n;i++){ 27 for(int j=0;j<=tmp; j++){ 28 if(c1[j]>=1){ 29 for(int k=0,p=0; k+j<=tmp&&p<=thing[i].num; k+=thing[i].val,p++){ 30 c2[j+k]+=c1[j]; 31 } 32 } 33 } 34 for(int j=0;j<=tmp;j++){ 35 c1[j]=c2[j]; c2[j]=0; 36 } 37 } 38 for(int i=tmp;i>=0;i--){ 39 if(c1[i]){ 40 printf("%d %d ",sum-i,i); 41 break; 42 } 43 } 44 } 45 return 0; 46 }