$\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;
}

——Gensokyo