HUD 1171 Big Event in HDU(01背包)

Big Event in HDU

Problem Description

Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the 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 they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).

 

Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 -- the total number 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 are different.
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

 

Wrong Answer

刚开始的RE和WA，一看原因是没有处理总数和DP数组太小，之后还是WA，竟然是没看题，以为是-1结束，完全不知道是负数结束。。。

 

Answer

输入是价值和数量，如果数量不是1，那么在放入数组的时候，需要用一个循环，把相应数量的价值都放进数组。

目的是要把这些东西分成价值最相近的两堆，那就先求出总价值，除以2，因为当两个都是半数的时候最接近，但是由于物品的价值不同，不一定能恰好分成两堆价值相同，就用半价值作为背包容量，求出最多能放入多少，总量减去这个最多的价值，就是另一堆的价值，输出要先大后小。

 

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#define PI acos(-1.0)
#define ms(a) memset(a,0,sizeof(a))
#define msp memset(mp,0,sizeof(mp))
#define msv memset(vis,0,sizeof(vis))
#define msd memset(dp,0,sizeof(dp))
using namespace std;
//#define LOCAL
int dp[300000];
int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    //freopen("out.txt","w",stdout);
#endif // LOCAL
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&n>0)
    {
        int sum=0;
        vector<int>v;
        v.clear();
        for(int i=0;i<n;i++)
        {
            int t1,t2;
            cin>>t1>>t2;
            while(t2)
            {v.push_back(t1);t2--;sum+=t1;}
        }
        int m=sum/2;
        msd,n=v.size();
        for(int i=0;i<n;i++)
        {
            for(int j=m;j>=v[i];j--)
            {
                dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
            }
        }
        printf("%d %d
",sum-dp[m],dp[m]);
    }
    return 0;
}