A test case starting with a negative integer terminates input and this test case is not to be processed.
Output For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.
Sample Input
2
10 1
20 1
3
10 1
20 2
30 1
-1
Sample Output
20 10
40 40/*
母函数解法：将能筹成的标记成1，找最接近sum/2的就可以
*/
#include
#include
#include
using std::max; const int MAX=52; bool c1[MAX*MAX*100];//c2[MAX*MAX*100]; int main(){ int N; int val[MAX],Count[MAX]; while(scanf("%d",&N),N>0){ int sum=0; memset(val,0,sizeof(val)); memset(Count,0,sizeof(Count)); memset(c1,0,sizeof(c1)); for(int i=1;i<=N;i++){ scanf("%d%d",&val[i],&Count[i]); sum+=val[i]*Count[i]; } c1[0]=1; int Limit=sum>>1; for(int i=1;i<=N;i++){ for(int j=0;j<=Limit;j++){ for(int k=0;j+k<=Limit&&k<=val[i]*Count[i];k+=val[i]) c1[k+j]=(c1[k+j]==1?c1[k+j]:c1[j]);//注意此处不能直接等于，防止出现 50 30 20 ，v[20]=0;的情况，是可以筹成50的 } /* for(int j=0;j<=Limit;j++){ c1=c2[j]; c2[j]=0; }*/ } int k=Limit; while(1){ if(c1[k]){ printf("%d %d\n",sum-k,k); break; } k--; } } return 0; }
/*
多重背包解法：
将体积和价值都看做 价值，上限也是 sum/2，找最大值，用sum-d[sum/2]便是较大的那一个
*/
#include
#include
#include
using std::max; const int MAX=51; int sum,Count,N; int dp[MAX*MAX*100]; int v[MAX],w[MAX],c[MAX]; int V[MAX],W[MAX]; void Div(){//多重背包分解 Count=0; for(int i=0;i
0){ W[Count++]=w[i]*c[i]; } } } int main(){ while(scanf("%d",&N),N>0){ sum=0; memset(w,0,sizeof(w)); memset(c,0,sizeof(c)); memset(W,0,sizeof(W)); memset(dp,0,sizeof(dp)); for(int i=0;i
>1; Div(); for(int i=0;i
=W[i];j--){ dp[j]=max(dp[j],dp[j-W[i]]+W[i]); } } printf("%d %d\n",sum-dp[upLimit],dp[upLimit]); } return 0; }