多重背包问题

这是个很老很老很早很早的知识点， 也是最为经典的DP（背包）模型之一。

题意： 给出物品个数 n，背包容积 V，以及每个物品的体积 v、价值 w、数量 s，求最大价值和。

今天没事做就写了写多重背包，三道模板，对应不同算法。

前置芝士：01背包、完全背包的学习，DP基础入门

多重背包1（$N \leq 100, V \leq 100$）

$0 < v_i, w_i, s_i \leq 100$

简单的背包，直接枚举取几个物品即可。

物品的体积、价值、数量分别用 V[i]、W[i]、C[i] 表示。

设 f[j] 表示使用了 j 的容积时，能取到的最大价值。以物品为阶段，我们考虑枚举取的物品个数， 显然有转移方程：
$$ f_j = \max_{1 \leq k \leq C_i}\{f_{j - k \times V_i} + k \times W_i\}[k \times V_i \leq j] $$
其中 k 表示枚举的 选取物品的个数。

时间复杂度约为 $\mathrm{O(N^2V)}$

退化：当物品个数全为1时就退化成01背包；当物品个数都远远大于“全取该物品”能取到的个数时，相当于完全背包。

关于本题：数据非常之小，以至于你可以将所有物品都拆出来，然后转化成01背包去做，但是显然这样对于稍微大一点的数据，比如物品可以非常之多的情况，就不适用了。

$\mathrm{Code:}$（码风略微鬼畜）

#include <iostream>
#define FOR(i, a, b) for (int i = (a), bb = (b); i <= bb; ++i) 
#define DOWN(i, a, b) for (int i = (a), bb = (b); i >= bb; --i)
const int N = 101, M = 101;
int n, m, f[M], V[N], W[N], C[N], ans = 0;
inline int read() {
    int s = 0, _ = 1; char c = getchar();
    for (; !isdigit(c) && c != '-'; c = getchar());
    (c == '-' ? _ = -1, c = getchar() : 0);
    for (; isdigit(c); c = getchar()) s = (s << 3) + (s << 1) + c - 48;
    return s * _; 
}
template <typename T>
inline void write(T x) {
    if (x < 0) x = ~x + 1, putchar('-');
    if (x > 9) write(x / 10);
    return putchar(x % 10 + 48), void();
}
signed main() {
    n = read(), m = read();
    FOR(i, 1, n) V[i] = read(), W[i] = read(), C[i] = read();
    FOR(i, 1, n) DOWN(j, m, V[i]) FOR(k, 1, C[i])
        if (j - k * V[i] >= 0) ans = std ::max(ans, f[j] = std ::max(f[j], f[j - k * V[i]] + k * W[i]));
    write(ans);
    return 0;
}

多重背包2 （$N \leq 1000, V \leq 2000$）

$0 < v_i, w_i, s_i \leq 2000$

这个数据范围，单纯的多重背包已经不再适用，我们考虑小 Trick，优化 01背包。

我们需要的是能够选择任意数量的物品，而 01 背包的局限在于只能选择单个物品。

那么通过上一阶段数据对于物品拆分的灵感，我们着手优化拆分。

能够表示 0 ~ n 中任意整数的拆分方案？二进制拆分。

众所周知，对于任意整数 x，都有拆分：
$$ x = b_1\times2^0 + b_2\times2^1 + b_3\times2^2… $$
b[i] 是该整数的二进制形式的从右往左第 i 位， 数值只有 0 或 1。 对于其他进制，我们都要考虑系数的问题，而二进制并不需要。

我们一路按照 2 的整次幂拆出物品，直到剩下的数量达不到 2 的整次幂， 则单独成一个物品。

假如说一个物品个数为 11，那么它就可以拆成 $2^0,2^1,2^2,4$ 这四个物品，你会发现对于 0 ~ 11 中的任意一数，都可以通过这三个物品的 “选” 与 “不选” 拼凑而成。

而 01 背包会帮你”智能“地选择拼成哪个数最好。

所以把物品拆开直接 01 背包就好了， 时间复杂度$\mathrm{O(V \sum log\ C_i)}$。

类贪心：本题的 Acwing 评论区中提出了一些贪心选择优化的DP，虽说存在反例，但是就效率而言不错，链接。

PS： 当然，结合了之前提到的完全背包退化，该做法会有更大的提升，甚至能水过一些 OJ 第三阶段的模板。

$\mathrm{Code:}$

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), bb = (b); i <= bb; ++i)
#define DOWN(i, a, b) for (int i = (a), bb = (b); i >= bb; --i)
const int N = 1e6 + 10, M = 4e6 + 10;
int n, m, w[N], v[N];
struct Production { int s, w, v; } a[N];
inline int read() {
    int s = 0, _ = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') c = getchar(), _ = -1;
    while (isdigit(c)) 
        s = (s << 1) + (s << 3) + c - 48, c = getchar();
    return s * _;
}
template <class T>
inline void write(T x) {
    if (x < 0) x = ~x + 1, putchar('-');
    if (x > 9) write(x / 10);
    return putchar(x % 10 + 48), void();
}
int f[M], len = 0;
void Spilt() {
    FOR(i, 1, n) {
        int t = 1;
        while (t <= a[i].s)
            w[++len] = t * a[i].w, v[len] = t * a[i].v, a[i].s -= t, t <<= 1;
        if (a[i].s) w[++len] = a[i].s * a[i].w, v[len] = a[i].s * a[i].v;
    }
}           // 二进制拆分
signed main() {
    n = read(), m = read();
    FOR(i, 1, n) 
        a[i].w = read(), a[i].v = read(), a[i].s = read();
    Spilt();
    FOR(i, 1, len) DOWN(j, m, w[i])
        f[j] = std ::max(f[j], f[j - w[i]] + v[i]);
            // 裸 01 背包
    write(f[m]);
    return 0;
}

多重背包3 （$N \leq 1000, V \leq 20000$）

$0 < v_i, w_i, s_i \leq 20000$

这个数据加强了体积与物品数量，拆分做法不再适用。想要通过这样的数据量，接下来我们就要通过 DP优化 获得提升。

本题为单调队列优化，前置芝士：单调队列。

观察 我们每次转移的 决策。即我们是从哪些地方获取的最优值更新当前最优值。

$f_j$ 是从 $\{f_k| k \in j - h\times V_i\}$ 转移的，如图：

我们发现黄色、橙色的值各自继承，没有干扰，那么就可以按照 $j \% V_i$ 的余数进行分类，分别计算答案，因为我们发现一个同余的类是可以优化的。

所以我们把方程变一变，用 u + p * V[i] 表示某一个 j。那么
$$ \begin{aligned} f_{u + p \times V_i} &= \max_{p - C_i \leq k \leq p - 1}\{f_{u + k \times V_i} + (p - k) \times V_i\} \end{aligned} $$

红色的点答案是由某一个黄色的点转移而来，这个黄色的点显然具有一些最优值，那么我们是不是只需要能实时维护这样的最优值，就可以避免枚举了呢？答案是肯定的。

我们将 DP 方程中只和 i 有关、只和 j 有关的项裂开，得到：
$$ \begin{aligned} f_{u + p \times V_i} &= \max_{p - C_i \leq k \leq p - 1}\{f_{u + k \times V_i} + (p - k) \times V_i\} \\ & = \max_{p - C_i \leq k \leq p - 1}\{f_{u + k \times V_i} - k \times V_i\} + p \times V_i \end{aligned} $$
在枚举 i 和 u 的情况下可以视其为常数，我们要维护的就是 max 中的值。

大家都知道，单调队列可以及时排除劣项，以维护集合单调有序。而我们通过这点维护 决策集合（即上图黄色决策点的集合）单调性。

建立一个单调队列 q，开始时为空。再枚举 p，每次操作：

• 先排除不可用决策，即如果决策点小于最低线 $p - C_i$，即需排除当前决策。
• 用最优决策更新当前点，即用 q[h] 求 $f_{u + p \times V_i}$，可以通过单调队列保证决策为最优。
• 用新决策点 $f_{u + p \times V_i}$ 及时排除队尾不优决策，具体方式为比较 $f_{u + k \times V_i} - k \times V_i$这一值的大小，排除该值比当前值小的决策。

尽管看起来有三重循环，但可以保证时间复杂度$\mathrm{O(VN)}$。

$\mathrm{Code:}$（为了不写滚动数组改得 十 分 鬼 畜，更加舒适的体验还请移步 Acwing某题解）

#include <iostream>
#define FOR(i, a, b) for (int i = (a), bb = (b); i <= bb; ++i)
#define DOWN(i, a, b) for (int i = (a), bb = (b); i >= bb; --i)
const int N = 1e3 + 10, M = 2e4 + 10;
int n, m, f[M], q[M], V[N], W[N], C[N];
inline int read() {
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c) && c != '-'; c = getchar());
    (c == '-' ? w = -1, c = getchar() : 0);
    for (; isdigit(c); c = getchar()) s = (s << 3) + (s << 1) + c - 48;
    return s * w;
}
template <typename T>
inline void write(T x) {
    if (x < 0) x = ~x + 1, putchar('-');
    if (x > 9) write(x / 10);
    return putchar(x % 10 + 48), void();
}
inline int Calc(int i, int u, int x) { return f[u + x * V[i]] - x * W[i]; }
signed main() {
    n = read(), m = read();
    FOR(i, 1, n) V[i] = read(), W[i] = read(), C[i] = read();
    FOR(i, 1, n) FOR(u, 0, V[i] - 1) {
        int h = 1, t = 0, maxn = (m - u) / V[i];
        DOWN(k, maxn - 1, std ::max(maxn - C[i], 0)) {
            while (h <= t && Calc(i, u, q[t]) < Calc(i, u, k)) --t;
            q[++t] = k;
        }
        DOWN(p, maxn, 0) {
            while (h <= t && q[h] > p - 1) ++h;
            if (h <= t) f[u + p * V[i]] = std ::max(f[u + p * V[i]], Calc(i, u, q[h]) + p * W[i]);
            if (p - C[i] - 1 >= 0) {
                while (h <= t && Calc(i, u, q[t]) < Calc(i, u, p - C[i] - 1)) --t;
                q[++t] = p - C[i] - 1;
            }
        }
    }
    int ans = 0;
    FOR(i, 1, m) ans = std ::max(ans, f[i]);
    write(ans);
    return 0;
}

<第一次更新>

我屈服了，滚动数组版：

$\mathrm{Code:}$

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#define FOR(i, a, b) for (int i = (a), bb = (b); i <= bb; ++i)
#define DOWN(i, a, b) for (int i = (a), bb = (b); i >= bb; --i)
const int M = 2e4 + 1;
int n, m, V, W, C, q[M], h, t, f[2][M];
inline int read() {
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c) && c != '-'; c = getchar());
    (c == '-' ? w = -1, c = getchar() : 0);
    for (; isdigit(c); c = getchar()) s = (s << 3) + (s << 1) + c - 48;
    return s * w;
}
inline void write(int x) {
    if (x < 0) x = ~x + 1, putchar('-');
    if (x > 9) write(x / 10);
    return putchar(x % 10 + 48), void();
}
inline int Calc(int i, int u, int k) { return (f[(i - 1) & 1][u + k * V] - k * W); }
main() {
    n = read(), m = read();
    FOR(i, 1, n) {
        V = read(), W = read(), C = read();
    //  C = std ::min(C, m / V);
        FOR(u, 0, V - 1) {
            h = 1, t = 0;
            int maxp = (m - u) / V;
            FOR(j, 0, maxp) {
                while (h <= t && q[h] < j - C) ++h;
                while (h <= t && Calc(i, u, q[t]) <= Calc(i, u, j)) --t;
                q[++t] = j;
                f[i & 1][u + j * V] = Calc(i, u, q[h]) + j * W;
            }
        }
    }
    write(f[n & 1][m]);
    return 0;
}

不知为啥，不吸氧就WA？？？我也没办法