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//背包方法：#include
#include
#include
using namespace std;
int dp[100000],sum,ans;
struct st
{
int v;
int m;
}data[100000];
void full(int x)
{
for(int i=data[x].v;i<=ans;i++)
dp[i]=max(dp[i],dp[i-data[x].v]+data[x].v);
}
void one(int x)
{
for(int j=1;j<=data[x].m;j++)
for(int i=ans;i>=data[x].v;i--)
dp[i]=max(dp[i],dp[i-data[x].v]+data[x].v);
}
int main()
{
int i,j,n;
while(scanf("%d",&n)&&(n>0))
{
memset(dp,0,sizeof(dp));
sum=0;
for(i=1;i<=n;i++)
{
scanf("%d%d",&data[i].v,&data[i].m);
sum+=data[i].v*data[i].m;
}
ans=sum/2;
for(i=1;i<=n;i++)
{
if(data[i].v*data[i].m>=ans)
full(i);
else
one(i);
}
printf("%d %d\n",sum-dp[ans],dp[ans]);
}
return 0;
}
//母函數方法：
/*注意將數組a,s清零，WA了好幾次，測試數據都過。。無語。
*/
#include
#include
int a[250010],s[250010];
int v[55],m[55];
int main()
{
int n,i,j,k,sum,ans;
while(scanf("%d",&n)&&n>0)
{
sum=0;
memset(s,0,sizeof(s));
memset(a,0,sizeof(a));
for(i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&m[i]);
sum+=v[i]*m[i];
}
for(i=0;i<=v[1]*m[1];i+=v[1])//注意變化。
{
s[i]=1;
}
for(i=2;i<=n;i++)
{
for(j=0;j<=sum;j++)
{
for(k=0;k+j<=sum&&k<=v[i]*m[i];k+=v[i])
{
a[k+j]+=s[j];
}
}
for(k=0;k<=sum;k++)
{
s[k]=a[k];
a[k]=0;
}
}
for(i=sum/2;i>=0;i--)
{
if(s[i])
{
printf("%d %d\n",sum-i,i);
break;
}
}
}
return 0;
}
