多重背包
朴素·二进制·单调队列
本课摘要
多重背包课程回答“有限件物品怎样从朴素枚举优化到二进制或单调队列”。内容以朴素·二进制·单调队列为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。
- 判断多重背包的适用条件与状态边界
- 围绕“朴素·二进制·单调队列”推导转移与计算顺序
- 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节
正在整理目录…
介于「一件」与「无限件」之间
最直接的想法：既然第 种有 件，那就当成 件各不相同的 01 物品摊开，全丢进 01 背包。 正确，但慢，若每种都有上万件，物品总数 会爆炸， 直接超时。
也别想着「一件一件试着放」：对同一种枚举「取 0 件、1 件、…、 件」，本质还是把 件逐个塞进去，复杂度一样是 。 问题的关键是：能不能用远少于 个「物品」，就表达出「取 0… 件」的全部可能？这一节的主角，二进制拆分，正是干这个的。
朴素解：把每种拆成 m 件 01 物品
先把最朴素的解法写清楚，它是后面所有优化的地基。状态照搬 01 背包： 表示容量不超过 时的最大价值。 对第 种物品，把它当作 件相同的 01 物品，一件一件地做逆推：
内层必须逆推，道理和 01 背包完全一样：每「件」至多取一次，逆推让 停在「这件还没放进来」的旧值上。 循环层次是「物品种 件数 容量」，复杂度 。
本质 · 多重背包 = 带件数上限的 01 背包
多重背包并没有新机制：它就是 01 背包，只不过同一种物品被允许取不超过 次。 朴素解把「 次」老老实实摊成 件，正确但冗余。后面要做的，全是如何更省地表达这 次。
二进制拆分：用 log 个「打包件」代替 m 件
朴素解的浪费在于：取 5 件，它非要一件一件加五次。可如果我手上有「1 件装」「2 件装」「4 件装」这样的打包件， 想凑 5 件，只需拿「1 件装 + 4 件装」，两次就够。这正是二进制拆分的思想：把 件拆成 这些 2 的幂，再加上一个余数包
每个「打包件」含 件原物，就等效成一件重量 、价值 的新物品，扔进 01 背包（逆推，每包至多用一次）。
为什么这几个包能凑出 0… 的任意件数？先只看 这几个 2 的幂，这正是二进制： 任何 到 之间的整数，都能唯一地写成它们的子集和（比如 、）。 于是这部分覆盖了 件。再补上余数 这一包：把它加进来，相当于让可凑范围整体平移 ， 正好把上界从 顶到 ，中间不留缝。既不重复、也不遗漏，恰好 。
拆完后，打包件总数从 降到 ，复杂度随之从 压到 。这是多重背包的主力解法。
本质 · 拆完就是 01 背包
二进制拆分把多重背包彻底还原成 01 背包：每个打包件就是一件普通 01 物品，逆推、取或不取，规则分毫不差。 所以它天然是 混合背包的一块拼图，01、完全、多重三种物品能同题混装，正因为它们最终都落在同一套一维转移上。
跟着算一遍：把 3 件拆成两包
用一种物品 、容量 6 走一遍。先拆件数 ：取 1（剩 2），再取 2（剩 0），得两个包，×1 包（）与 ×2 包（）。
看它把每个打包件逐格放进去
- 来源参与当前转移的依赖状态
- 当前正在计算或观察的状态
- 确定 / 最优已进入当前最优解或确定结果
- 已处理已经扫描、当前不再活跃的状态
- 非法越界、冲突或不可达状态
再进一步：单调队列 O(V·n)（选讲）
二进制拆分已经够快，应付绝大多数题目。但还有一层理论最优： 的单调队列优化，连那个 都抹掉。
思路是：把容量 按对 取模的余数分组，同余的那些 （即 ）恰好构成一条「取第 种若干件」的链。 在每条链上，「取不超过 件」就变成了一个定长滑动窗口求最大值的问题，用单调队列可 均摊维护，于是第 种物品整体只花 。
设 是加入当前物品前的旧数组。固定余数 ，令容量 ，再用 表示「从旧状态出发的位置」，便有
对每个 ，变化的只是长度为 的窗口 ；候选分数 只依赖 。队首保存窗口内分数最大的 ，每个下标最多进队、出队一次，于是整条链是线性的。
跟着算一遍：按余数链维护滑动窗口
处理物品 ，容量上限 8。只看偶数余数链 ；旧数组在容量 上的值依次是 。
队列里到底存什么
队列存的是链下标 ：队首过期条件是 ，队尾则按 从大到小淘汰。每次把当前 也入队，表示「当前物品取 0 件」，因此不会漏掉沿用旧状态的选择。
下面是与 P1776 输入格式一致的完整写法。代码比二进制拆分繁琐，竞赛里通常仍首选二进制；当容量与物品种数允许、但件数上限很大时，再考虑这套 优化。
#include <deque>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, W;
cin >> n >> W;
vector<long long> f(W + 1, 0);
for (int i = 1; i <= n; i++)
{
int v, w, m; // 价值、重量、件数上限
cin >> v >> w >> m;
vector<long long> g = f; // g：还没加入第 i 种物品的旧状态
for (int r = 0; r < w && r <= W; r++) // 容量按 j mod w 分成 w 条链
{
deque<int> q; // 存链上的下标 x，不是容量 j
auto score = [&](int x) {
return g[r + x * w] - 1LL * x * v;
};
for (int k = 0, j = r; j <= W; k++, j += w)
{
while (!q.empty() && q.front() < k - m)
q.pop_front(); // 超过 m 件，窗口左端失效
while (!q.empty() && score(q.back()) <= score(k))
q.pop_back(); // 保持候选分数单调递减
q.push_back(k); // x=k 表示这一种取 0 件
int x = q.front();
f[j] = g[r + x * w] + 1LL * (k - x) * v;
}
}
}
cout << f[W] << endl;
return 0;
}常见陷阱 · 别把三法记混
三法的分界很清晰：朴素 是把 件摊开；二进制 是把 打包（主力）；单调队列 是按同余滑窗（选讲）。三者拿的都是同一个 ，只是把「取不超过 件」表达得越来越省。切莫把二进制的「打包件」当成真的多买了物品，打包只是转移的组织方式，取用件数始终不超过 。
例题
#include <iostream>
using namespace std;
int a[7]; // 六种砝码的个数
int val[7] = {0, 1, 2, 3, 5, 10, 20}; // 对应面值
bool f[1005]; // f[j]：重量 j 能否被称出
int main()
{
for (int i = 1; i <= 6; i++)
cin >> a[i];
int S = 0; // 可达重量的上界
for (int i = 1; i <= 6; i++)
S += a[i] * val[i];
f[0] = true; // 重量 0 恒可达（不放砝码）
for (int i = 1; i <= 6; i++) // 逐种砝码
for (int k = 1; k <= a[i]; k++) // ★朴素：这一种一件一件地放
for (int j = S; j >= val[i]; j--) // 每件都是一次 01 逆推
if (f[j - val[i]])
f[j] = true;
int cnt = 0;
for (int j = 1; j <= S; j++) // 统计非零可达重量的种数
if (f[j]) cnt++;
cout << "Total=" << cnt << endl;
return 0;
}#include <iostream>
#include <algorithm>
using namespace std;
int f[40005]; // f[j]：容量不超过 j 的最大价值
int w2[100005], v2[100005]; // 二进制拆分后的「打包件」
int cnt; // 打包件总数
int main()
{
int n, W;
cin >> n >> W;
for (int i = 1; i <= n; i++)
{
int v, w, m; // 价值、重量、件数上限
cin >> v >> w >> m;
int k = 1; // ★二进制拆分：1,2,4,… 各捆一包
while (k < m)
{
cnt++;
w2[cnt] = k * w; // 一包含 k 件，等效重量 k*w
v2[cnt] = k * v; // 等效价值 k*v
m -= k;
k <<= 1; // k 翻倍
}
if (m > 0) // 余数单独成一包
{
cnt++;
w2[cnt] = m * w;
v2[cnt] = m * v;
}
}
for (int i = 1; i <= cnt; i++) // 每个打包件当一件做 01 背包
for (int j = W; j >= w2[i]; j--) // ★逆推：一包至多用一次
f[j] = max(f[j], f[j - w2[i]] + v2[i]);
cout << f[W] << endl;
return 0;
}