多重背包

一、问题描述

有 $n$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品的体积为 $w[i]$ ，价值为 $v[i]$ ，最多可以选择 $s[i]$ 件。

在所选物品总体积不超过 $V$ 的前提下，求能够得到的最大总价值。

本节沿用《完全背包》的符号，允许背包没有装满，也允许一件物品都不选。

三种背包问题的区别在于每种物品可以选择的数量：

问题	第 $i$ 种物品可以选择的件数
01 背包	$0$ 或 $1$
完全背包	$0,1,2,\ldots$ ，直到容量不足
多重背包	$0,1,2,\ldots,s[i]$ ，同时满足容量限制

本节代码约定 $1\le n\le5000$ 、 $0\le V\le5000$ 、 $1\le w[i]\le5000$ 、 $0\le v[i]\le10^6$ 、 $1\le s[i]\le10^9$ 。

二、二进制优化：把物品拆成若干组

1. 转化为 01 背包

将 $s$ 件相同物品逐件作为 01 背包物品，数量可能过多。二进制优化将它们按 $1,2,4,8,\ldots$ 件分组，最后不足下一组的部分单独作为一组。

每组视为一件新的 01 背包物品，只能整组选或不选。 拆出的组需要能表示选择 $0$ 到 $s$ 件的所有情况。

如果某组包含 $c$ 件第 $i$ 种物品，这件新物品的属性为：

$$\text{体积}=c\cdot w[i],\qquad \text{价值}=c\cdot v[i].$$

2. 拆分示例

假设一种物品的体积为 $2$ ，价值为 $3$ ，最多可以选 $100$ 件。

拆分的要求是：各组最多选一次，拼出的件数恰好覆盖 $0$ 到 $100$ 的所有整数，既不能遗漏，也不能超过 $100$ 。

依次拆出 $1,2,4,8,16,32$ 件，总共拆出了 $63$ 件，还剩 $37$ 件。不足下一组的 $64$ 件，因此将剩余 $37$ 件作为最后一组：

100=1+2+4+8+16+32+37.

得到七件新的 01 背包物品：

新物品	包含原物品的件数	总体积	总价值
A	1	2	3
B	2	4	6
C	4	8	12
D	8	16	24
E	16	32	48
F	32	64	96
G	37	74	111

例如选择 $64$ 件，可以选取 $1+2+8+16+37$ 这几组。原来需要处理 $100$ 件物品，现在只需处理 $7$ 组。

3. 为什么能够表示所有件数？

前六组 $1,2,4,8,16,32$ 可以按二进制组合出 $0$ 到 $63$ 的所有整数。因此：

不选最后的 $37$ 件这一组，可以拼出 $[0,63]$ 中的所有整数。
选择这组，再搭配前六组，可以拼出 $37+[0,63]=[37,100]$ 中的所有整数。

两段区间合起来恰好是 $[0,100]$ ，所以所有件数都能拼出。全部组的件数之和为 $100$ ，也不会超出上限。

一般数量的拆分同理：前面的二次幂组覆盖一段连续区间，最后的余数组不会造成空缺，因此保留了原问题的所有合法件数。

注意，不能只按 $100$ 的二进制表示拆成 $4+32+64$ ，这样虽然总和正确，却无法拼出 $1$ 、 $2$ 等数量。

三、拆分后进行 01 背包转移

设 dp[j] 表示处理过的组中，总体积不超过 $j$ 时能够得到的最大总价值。

因为允许一件物品都不选，初始时 dp[] 全部为 $0$ 。

对于包含 $c$ 件原物品的一组，令 weight = c * w、value = 1LL * c * v，进行 01 背包转移：

for (int j = V; j >= weight; --j) {
    dp[j] = max(dp[j], dp[j - weight] + value);
}

容量必须倒序枚举。 原物品虽然可以选多件，但每一组只能选一次。如果改成正序，同一组就可能被重复选择，导致超出原物品的数量上限。

可以一边拆分一边更新 dp[]，不需要把所有新物品存下来。

四、参考代码

输入第一行为 $n,V$ ，接下来 $n$ 行，每行输入一种物品的体积、价值和数量上限，即 $w,v,s$ 。输出最大总价值。

背包最多装下 $\lfloor V/w\rfloor$ 件同种物品，因此拆分前先令 s = min(s, V / w)，减少无用的组。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 5005;
int n, V;
long long dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        int w, v, s;
        cin >> w >> v >> s;

        // 超过容量允许的件数没有必要考虑
        s = min(s, V / w);

        // 依次拆出 1、2、4……件，最后一组取剩余件数
        for (int k = 1; s > 0; k *= 2) {
            int c = min(k, s);
            int weight = c * w;
            long long value = 1LL * c * v;

            // 当前这一组最多选择一次，按照 01 背包倒序更新
            for (int j = V; j >= weight; --j) {
                dp[j] = max(dp[j], dp[j - weight] + value);
            }

            s -= c;
        }
    }

    cout << dp[V] << '\n';
    return 0;
}

价值乘法和 DP 状态使用 long long，因为最大总价值可能达到 $5\times10^9$ 。

五、复杂度

设有效数量为：

$$t_i=\min\left(s[i],\left\lfloor\frac{V}{w[i]}\right\rfloor\right).$$

第 $i$ 种物品拆成 $O(\log(t_i+1))$ 组，每一组进行一次 $O(V)$ 的 01 背包转移。因此，时间复杂度为：

O\left(n+V\sum_{i=1}^{n}\log(t_i+1)\right).

其中 $O(n)$ 为读入开销。有效数量不超过 $V$ ，因此时间上界也可写为 $O(n+nV\log(V+1))$ 。

边读入边拆分、边进行转移，只使用一个 DP 数组，空间复杂度为 $O(V)$ 。

六、单调队列优化

多重背包还可以使用单调队列进一步优化到 $O(nV)$ 。单调队列优化多重背包的方法见 DP 优化章节。