一、题意

有6堆石头，第i堆石头中每个石头的价值都是i。然后输入每堆石头的数量num[i]。
要求你判断是否可以将所有石头分成总价值相等的两堆。

二、解析

首先算出所有石头的总价值V，若V为奇数，则无解。
若V为偶数，则我们的目标就是拿一个体积为V/2的背包，然后尽可能装满它。若装得满，说明原问题可以分成价值相等的两堆，否则不能。

由于每种价值的石头有数量限制，因此这是一个多重背包问题。
在本题对应的背包问题中，物体（也就是石头）的价值和体积都是V[i]。于是我们套用完全背包的模板即可。

一般情况下，完全背包问题使用二进制法就基本不会超时了，它的原理就是将一个数量为p[i]，价值为v[i]的物体拆分成 1、2、4、8...这若干份（每一份右2的幂次份原物体构成，构成的新物体价值为kw[i]，体积为kv[i]），然后注意最后不足2的幂次的数量也单独做成1份，这样物体的总数量就降为了 O(∑lgn)。然后就可以按照01背包问题的套路来处理这∑lgn个新物体了。

正确性是由二进制原理保证的：因为原来可能选择的1~p[i]个原物体一定可以被替换为新物体的组合。

三、代码

#include <iostream>
// #include <cmath>
#define max(x, y) (x)>(y)?(x):(y)
#define min(x, y) (x)<(y)?(x):(y)
using namespace std;
const int n = 6, maxv = 210000 + 5;
const int v[n] = {1, 2, 3, 4, 5, 6};
int kase = 1, p[n], dp[maxv];

void output(bool ok) {
    cout << "Collection #" << kase ++ << ":" << "\n";
    cout << (ok ?  "Can be divided.\n" : "Can't be divided.\n") << endl;
}

int main() {
    while(cin >> p[0] >> p[1] >> p[2] >> p[3] >> p[4] >> p[5]) {
        int V = 0;
        for(int i = 0; i < n; i ++) V += v[i] * p[i];
        if(V == 0) break;
        else if(V % 2) output(0);
        else {
            V /= 2;
            fill(dp, dp + V + 1, 0);
            for(int i = 0; i < n; i ++) {
                for(int k = 1, num = min(p[i], V / v[i]); num > 0; k <<= 1) {
                    if(k > num) k = num;
                    num -= k;
                    for(int j = V; j >= k * v[i]; j --) {
                        dp[j] = max(dp[j], dp[j - k * v[i]] + k * v[i]);
                    }
                }
            }
            output(dp[V] == V);
        }
    }
}

四、归纳

  • 多重背包问题：将n种物品放入体积为V的背包中，每种物体有数量限制p[i]。二进制法实现的模板如下（ 用时O(V*∑lg(p[i])) ）： 
int v[n], w[n], p[n], dp[maxv];  // p[i]表示原物体i的数量限制
fill(dp, dp + V + 1, 0);
for(int i = 0; i < n; i ++) {
    for(int k = 1, num = min(p[i], V / v[i]); num > 0; k <<= 1) {  // 每一个新物体由k个原物体组成
        if(k > num) k = num;  // 最后不足2的幂次的单独一份
        num -= k;
        for(int j = V; j >= k * v[i]; j --) {  // 对新物体使用01背包问题处理，这里使用的是01背包问题的滚动数组模板，当然也可以不用
            dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
        }
    }
}
  • 01背包问题可以通过滚动数组的形式来减少空间复杂度，只需要将j的遍历顺序反过来即可。但注意，如果需要打印路径的话，就不能使用滚动数组。 
fill(dp, dp + V + 1, 0);
for(int i = 0; i < n; i ++) {
    for(int j = V; j >= v[i]; j --) {
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}
  • 实际上还有一种使用单调队列的优化方式，但由于技巧性比较高，一般用不到