1 //Accepted    10108 KB    125 ms 2 //多重背包 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 1005; 8 const int imax_v = 50*1005*100/2+5; 9 int n,v;10 int sum;11 int cost[imax_n];12 int weight[imax_n];13 int amount[imax_n];14 int f[imax_v];15 int max(int a,int b)16 {17     return a>b?a:b;18 }19 void zeroOnePack(int cost,int weight)20 {21     for (int j=v;j>=cost;j--)22     f[j]=max(f[j],f[j-cost]+weight);23 }24 void completePack(int cost,int weight)25 {26     for (int j=cost;j<=v;j++)27     f[j]=max(f[j],f[j-cost]+weight);28 }29 void multiplePack(int cost,int weight,int amount)30 {31     if (amount*cost>=v)32     {33         completePack(cost,weight);34         return ;35     }36     int k=1;37     while (k<amount)38     {39         zeroOnePack(cost*k,weight*k);40         amount-=k;41         k<<=1;42     }43     zeroOnePack(amount*cost,amount*weight);44 }45 void Dp()46 {47     memset(f,0,sizeof(f));48     for (int i=0;i<n;i++)49     {50         multiplePack(cost[i],weight[i],amount[i]);51     }52     int ans=0;53     for (int i=0;i<=v;i++)54     ans=max(ans,f[i]);55     ans=max(ans,sum-ans);56     printf("%d %d\n",ans,sum-ans);57 }58 int main()59 {60     while (scanf("%d",&n) && n>=0)61     {62         sum=0;63         for (int i=0;i<n;i++)64         {65             scanf("%d%d",&weight[i],&amount[i]);66             cost[i]=weight[i];67             sum+=cost[i]*amount[i];68         }69         v=sum/2;70         Dp();71     }72     return 0;73 }