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

题解

题目大概意思是有个2个部门需要分配硬件
分配后A和B部门的价值尽可能相等 并且A不小于B
我们要考虑的是怎么达到这个条件呢
首先总价值是恒等不变的 最好的情况就是 一人一半的价值
所以这里我们可以把总价值的一半看成背包的最大容量
给B的总容量 是 总价值的一半 问题就变成了求B的最大价值
因为B的最大价值不会大于总容量的一半 所以最后一定符合A大于等于B


第一种实际上就是把多个物品拆分开来看成不同的物品
那么本质上还是01背包

#include <iostream>
#include <cstring>
using namespace std;
int dp[2000000],val[2000000],num[2000000];
int main() {
    ios::sync_with_stdio(false);
    int N;
    int a,b;
    while (cin >> N)
    {
        if(N < 0)break;
        memset(dp,0,sizeof(dp));
        memset(val,0,sizeof(val));
        memset(num,0,sizeof(num));
        int sum = 0;
        for (int i = 0; i < N; ++i) {
            cin >> val[i] >> num[i];
            sum += val[i]*num[i];
        }
        int half = sum / 2;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < num[i]; ++j) {
                for (int k = half; k >= val[i] ; --k) {
                    dp[k] = max(dp[k],dp[k - val[i]] + val[i]);
                }
            }
        }
        cout << sum-dp[half] << " " << dp[half] << endl;
    }
    return 0;
}


多重背包 因为每种物品不止一个
我们只要在01背包做修改就行了

#include <iostream>
#include <cstring>
using namespace std;
int dp[2000000],val[2000000],num[2000000];
int main() {
    ios::sync_with_stdio(false);
    int N;
    int a,b;
    while (cin >> N)
    {
        if(N < 0)break;
        memset(dp,0,sizeof(dp));
        memset(val,0,sizeof(val));
        memset(num,0,sizeof(num));
        int sum = 0;
        for (int i = 0; i < N; ++i) {
            cin >> val[i] >> num[i];
            sum += val[i]*num[i];
        }
        int half = sum / 2;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j <= half; ++j) {
                for (int k = 1; k <= num[i] && k * val[i] <= j; ++k) {
                    dp[j] = max(dp[j],dp[j - val[i] * k] + val[i] * k);
                }
            }
        }
        cout << sum-dp[half] << " " << dp[half] << endl;
    }
    return 0;
}

Last modification:April 10th, 2020 at 11:01 pm
如果觉得我的文章对你有用,请随意赞赏