多重背包的二进制分解法

· · 题解

\text{蒟蒻在DP之路上求索着}

羞羞脸打广告来获得更好的阅读体验

这是一道裸的多重背包,也就是给出若干种物品,每种物品的价格是v_i,每种物品的代价是w_i,每种物品有c_i件的背包问题.

思路

当我们在看到这种题的时候,首先想到可以直接把每种物品视为c_i件不同的物品,然后做01背包.这原则上是正确的.但是,题目显然不会这么放你AC.数据范围往往会让你的01背包TLE.

这样来看,当我们把需要做的事完全拆分碎,就造成了大量时间的花费.那么我们可以联想到我们曾重点讨论的倍增的思想.

在这道题中,我们不必把很多件物品拆分成一个一个的单件物品,而可以通过二进制的方法,使得不管你打算取其中的多少件,都可以表示的出来.也就是通过将同种物品分组,使得选择其中不同的组合能够等价于选择各种数量的单件.具体操作是这样的:

我们将c_i二进制分解,但是要求每一位二进制位都必须是1.这显然是无法适应所有数据的.毕竟不是所有数据都满足c_i=2^k-1.即便如此我们也要尽量做到这一点.因此我们要找到最大的k,使得t=\sum_{i=0}^{k}2^i满足t\le c_i.也就是找到最大的,小于c_i的二的各个次幂和.到目前为止我们可以通过不重复且有选择地使用2^0到2^k来表示出1到t所有的数.但是剩下的咋办呢?我们将剩下的c_i-t单独分为一组.因为1到t都可以表示,那么有了这个c_i-t组就可以表示出所有数了.例如我们会把21分为1,2,4,8,6,这样就可以从中不重复地选择来表示出1到c_i的所有数了.

这时候,问题已然变成了一个01背包问题.时空间复杂度均得到了优化.

题解代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n, v, p[10005], w[10005], f[40005];

int main() {//f数组为常规01背包数组,
    cin >> n >> v;//w是重量数组
    int tot = 0;//p是价值数组,tot是物品数量
    for (int i = 1; i <= n; i++) {//二进制拆分
        int a, b, c;
        cin >> a >> b >> c;
        for (int j = 1; j <= c; j <<= 1) {
            p[++tot] = j * a;//循环2的0到k次方
            w[tot] = j * b;//每件物品相当于若干
            c -= j;//单件的捆绑
        }
        if (c > 0) {//此时c只剩下没分解的部分了
            p[++tot] = c * a;
            w[tot] = c * b;
        }
    }
    for (int i = 1; i <= tot; i++)//平凡的01背包
        for (int j = v; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + p[i]);
    cout << f[v] << endl;
    return 0;
}