多重背包

一句话算法

多重背包的核心是“每种物品最多选有限个”；常用做法是把数量拆成若干个二进制包，再转成 01 背包。

问题模型

给定 $n$ 种物品和容量为 $C$ 的背包。第 $i$ 种物品有：

• 重量 $w_i$；
• 价值 $v_i$；
• 数量上限 $m_i$。

要求选择若干物品，使总重量不超过 $C$，总价值最大。每种物品最多只能选 $m_i$ 个。

它位于 01 背包和完全背包之间：

核心直觉

朴素转移会枚举第 $i$ 种物品选几个：

如果直接枚举 $k$，复杂度可能很高。

二进制拆分的想法是：不用一个一个拿，而是把 $m_i$ 个相同物品拆成若干个“大包”。

例如 $m_i=13$：

13 = 1 + 2 + 4 + 6

于是原来“最多选 13 个”变成选择这些包中的若干个：

1 个包，2 个包，4 个包，6 个包

这些包组合起来可以表示 $0..13$ 中的任意数量。

为什么二进制拆分正确

对一个数量上限 $m$，按下面方式拆：

1, 2, 4, 8, ..., rest

每次取当前能取的最大二进制块，最后剩下的 rest 小于下一块大小。

例如：

13 -> 1, 2, 4, 6

前面的 $1,2,4$ 可以组成 $0..7$ 的任意数；最后的 $6$ 加上它们，可以组成 $6..13$ 的任意数。两段合起来覆盖 $0..13$。

拆完后，每个包只能选一次，因此可以直接做 01 背包。

算法步骤

1. 初始化 dp[c]=0。
2. 枚举每种物品 (w,v,m)。
3. 将数量 m 拆成 1,2,4,...,rest。
4. 对每个拆出的包：
   • 包重量为 cnt * w；
   • 包价值为 cnt * v；
   • 按 01 背包方式容量倒序更新。
5. 输出 dp[C]。

算法证明

关键不变量： 处理完某种物品后，dp[c] 表示在已经处理的物品范围内，容量不超过 c 的最大价值。

1. 拆分不改变可选数量集合

   二进制拆分出的若干包，可以组合出从 $0$ 到 $m_i$ 的任意整数数量。因此，原来第 $i$ 种物品所有合法选择数量，在拆分后仍然都能表示。

2. 拆分不会产生非法数量

   所有包的数量之和正好是 $m_i$。每个包最多选一次，因此组合出的总数量不会超过 $m_i$。

3. 转化为 01 背包

   每个拆出的包都是一个独立的 01 物品。容量倒序更新保证每个包最多被使用一次。

4. 最优性保持

   原问题中任意合法方案，都能映射为拆分包中的某个 01 选择方案；拆分后的任意 01 选择方案，也能映射回原问题中合法的选取数量。因此两者最优值相同。

所以二进制拆分后做 01 背包是正确的。

复杂度分析

第 $i$ 种物品会被拆成 $O(\log m_i)$ 个包。

• 时间复杂度：$O(C\sum_{i=1}^{n}\log m_i)$。
• 空间复杂度：$O(C)$。

如果 $m_iw_i\ge C$，第 $i$ 种物品在容量范围内等价于完全背包，也可以直接用完全背包正序优化。但模板为了统一，使用二进制拆分。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

        #include <bits/stdc++.h>
using namespace std;

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

    int n, capacity;
    cin >> n >> capacity;

    vector<int> dp(capacity + 1, 0);

    for (int i = 1; i <= n; ++i) {
        int weight, value, amount;
        cin >> weight >> value >> amount;

        for (int block = 1; amount > 0; block <<= 1) {
            int cnt = min(block, amount);
            amount -= cnt;

            int pack_weight = cnt * weight;
            int pack_value = cnt * value;

            for (int c = capacity; c >= pack_weight; --c) {
                dp[c] = max(dp[c], dp[c - pack_weight] + pack_value);
            }
        }
    }

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

测试用例

输入：

3 10
2 3 3
3 4 2
5 10 1

输出：

17

解释：选 2 个第一种物品、2 个第二种物品，总重量 $2\times2+2\times3=10$，总价值 $2\times3+2\times4=14$；更优方案是选 1 个第一种、1 个第二种、1 个第三种，总重量 $2+3+5=10$，总价值 $3+4+10=17$。

应用分类详解

多重背包的本质是：每种资源可以使用有限次。只要题目同时出现“容量限制”和“每种选择有数量上限”，就应该考虑多重背包。

一、有限数量物品最大价值

典型模式： 每种物品有库存，不能无限选。

识别信号： 出现“第 $i$ 种有 $m_i$ 个”“最多购买若干件”“库存有限”。

核心建模： 重量是容量消耗，价值是收益，数量上限用二进制拆分处理。

二、有限次数凑数

典型模式： 每种面值、材料或操作最多使用若干次。

识别信号： 出现“每种硬币有数量限制”“每种材料库存有限”“每个技能最多用几次”。

核心建模： dp[c] 可以表示是否可达、最大价值、最少代价或方案数。

三、需要进一步优化的大数量模型

典型模式： 容量和数量都很大，二进制拆分仍可能偏慢。

识别信号： $\sum \log m_i$ 仍然很大，或题目明确要求单调队列优化。

核心建模： 按容量对 $w_i$ 取模分组，把转移变成滑动窗口最大值。

经典例题

1. acwing-4

多重背包模板题。适合练习二进制拆分。

2. luogu-P2347

砝码称重。目标不是最大价值，而是统计哪些重量可达，本质仍是有限数量选择。

3. 有限硬币凑金额

每种硬币面值固定、数量有限。可以用多重背包判断某个金额是否可达，或求最少硬币数。

参考

• 前置：01 背包
• 前置：完全背包
• 进阶：本目录 单调队列优化.md