DP Problem R：Big Event in HDU（HDU 1171）

Problem R

Time Limit : 10000/5000ms (Java/Other)   Memory Limit :65536/32768K (Java/Other)

Total Submission(s) : 1   Accepted Submission(s) : 0

Problem Description

Nowadays, we all know thatComputer College is the biggest department in HDU. But, maybe you don't knowthat Computer College had ever been split into Computer College and SoftwareCollege in 2002.<br>The splitting is absolutely a big event in HDU! Atthe same time, it is a trouble thing too. All facilities must go halves. First,all facilities are assessed, and two facilities are thought to be same if theyhave the same value. It is assumed that there is N (0&lt;N&lt;1000)kinds of facilities (different value, different kinds).<br>

Input

Input contains multiple testcases. Each test case starts with a number N (0 < N <= 50 -- the totalnumber of different facilities). The next N lines contain an integer V(0<V<=50 --value of facility) and an integer M (0<M<=100--corresponding number of the facilities) each. You can assume that all V aredifferent.<br>A test case starting with a negative integer terminatesinput and this test case is not to be processed.<br>

Output

For each case, print one linecontaining two integers A and B which denote the value of Computer College andSoftware 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.<br>

Sample Input

2

10 1

20 1

3

10 1

20 2

30 1

-1

Sample Output

20 10

40 40

算法分析：

多重背包问题，不同的是要在中间开始，具体思路看代码,这题巧妙在价值直接可以看出体积（原因全部分完）

代码实现：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)&&n>0)
    {
        int w[52],num[52],f[250005],sum=0,mid,i,j,k;
        for(i=1;i<=n;i++)
            {
            scanf("%d%d",&w[i],&num[i]);
            sum+=w[i]*num[i];//计算出总价值
            }
            memset(f,0,sizeof(f));//初始化
            mid=sum/2;
        for(i=1;i<=n;i++)//物品价值
         for(j=1;j<=num[i];j++)//每个物品数量,j=0开始相当于有0件，但这里没有
            for(k=mid;k>=w[i];k-=w[i])//因为要求把都分完，这里可以把价值看作体积，但要在中间开始
            f[k]=max(f[k],f[k-w[i]]+w[i]);
            printf("%d %d\n",sum-f[mid],f[mid]);
    }

    return 0;
}