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]--){//用常規(guī)的多重背包做，必超時
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