1 /*
 2 Author:    Leo.W
 3 Descriptipn:    多重背包问题。选定总价值的一半作为背包容量V，选定物件开始加入。            
 4 How to Do:    如描述。
 5   */
 6 #include <stdio.h>
 7 #include <string.h>
 8 int value[51],num[51];
 9 int dp[250002];
10 int main(){
11     int i,j,t,sum,half;
12     while (scanf("%d",&t)&&t>=0){
13         memset(dp,0,sizeof(dp));    dp[0]=1;
14         sum=0;
15         for(i=0;i<t;i++){
16             scanf("%d%d",&value[i],&num[i]);
17             sum+=value[i]*num[i];
18         }
19         half=sum/2;//取总价值一半为背包的容量
20         for(i=0;i<t;i++){
21             while(num[i]--){//用常规的多重背包做，必超时
22                 for(j=half-value[i];j>=0;j--){
23                     if(dp[j])    dp[j+value[i]]=1;
24                 }
25             }    
26         }
27         while(!dp[half]) half--;//寻找最接近一半价值的
28         printf("%d %d\n",sum-half,half);
29     }
30 } 
31