hdu1171 01背包 | 多重背包

题目链接：点击打开链接

题意：

杭电分设备；

有 n 种设备；

每种都不同，每种都有 w[i] 个；

问怎样分才能使分成的两堆之差最少；

理解：

多重背包；

套模板；

递推式：dp[i] = max(dp[i], dp[i - mul * v[i]] + mul * v[i])；

其中的值根据代码定义；

也可以 01背包做；

但是顺手就用了多重背包；

有个坑，输入结束标志是一个负数，而不是-1；

代码如下：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int MIN_INF = 1e-7;
const int MAX_INF = (1e9) + 7;

#define X first
#define Y second

int dp[555555];
int v[1111];
int w[1111];

int main() {
    int n;
    while (cin >> n && n >= 0) {
        memset(dp, 0, sizeof(dp));
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            cin >> v[i] >> w[i];
            sum += v[i] * w[i];
        }

        for (int i = 0; i < n; ++i) {
            int num = w[i];
            for (int k = 1; num > 0; k <<= 1) { // 注意是左移等于
                int mul = min(k, num);
                for (int j = sum / 2; j >= mul * v[i]; --j) {
                    dp[j] = max(dp[j], dp[j - mul * v[i]] + mul * v[i]);
                }
                num -= k;
            }
        }

        cout << sum - dp[sum / 2] << " ";
        cout << dp[sum / 2] << endl;
    }

    return 0;
}