企业官网建设流程全解析

很多人学动态规划，背包问题算是最经典的入门关卡。但说实话，01背包和完全背包很多人背一背状态转移就过了，真正让人头皮发麻的是多重背包——每种物品有数量限制，不是只有一件，也不是无限拿。网上讲多重背包的文章不少，但多是直接丢个优化结论，看完代码还是不知道为什么。这次我把多重背包的几种主流写法从头到尾拆一遍，顺带把完全背包的思路也整理清楚，希望能帮你把这几类背包真正打通。

先说清楚一个容易混淆的点：完全背包不是多重背包的“无限数量版”那么简单，两者在状态转移方向、优化思路上都有本质区别。但反过来，多重背包在某些条件下可以借用完全背包的写法。这些内容我都会在下面展开。

1. 问题的定位：多重背包、完全背包和01背包的关系

1.1 从01背包到多重背包：一件物品的“限量供应”

先回顾01背包的状态转移，这是整个背包家族的地基：

$$dp[j] = \max(dp[j], ; dp[j - w[i]] + v[i])$$

含义很简单：容量为$j$的背包，要么不拿第$i$件物品，要么拿一件并腾出$w[i]$的空间。因为每件物品只有一件，所以容量必须倒序遍历，避免同一件物品被重复使用。

完全背包的区别在于“每件物品可以拿无限件”，于是状态转移变成了正序遍历：

$$dp[j] = \max(dp[j], ; dp[j - w[i]] + v[i])$$

转移公式看起来一模一样，唯一的差别是容量循环方向。但正是这个方向差异，导致完全背包的朴树复杂度只有$O(NV)$，比多重背包的朴素写法快一个数量级。至于为什么，后面我会单独展开。

多重背包的问题设定是：第$i$种物品有$c[i]$件，每件重量$w[i]$、价值$v[i]$。它既不是01背包那种“每样一件”，也不是完全背包那种“无限供应”，而是中间状态：有上限，但上限大于1。

朴素想法很直接：把第$i$种物品拆成$c[i]$个独立的01背包物品，然后跑一遍01背包。比如某件物品有5件，就当成5个独立物品，每个只能选一次。这样问题就退化成了01背包。缺点是复杂度太高，复杂度为$O(NVC)$，$C$是单种物品的数量上限。一旦$N$、$V$、$C$三个维度都到几千，基本就等着超时了。

1.2 为什么朴素写法在数据一大时就过不了

我最初学多重背包时，第一版代码长这样：

for (int i = 1; i <= n; ++i) { int w, v, c; cin >> w >> v >> c; // 倒序枚举容量 for (int j = V; j >= 0; --j) { // 枚举第 i 种物品选 k 件 for (int k = 0; k <= c && k * w <= j; ++k) { dp[j] = max(dp[j], dp[j - k * w] + k * v); } } }

这个写法思路没错，但你看三重循环：外层是物品种类，中层是容量，内层是件数。粗略算一下，$N=100$，$V=1000$，$C=100$，这就是$10^7$量级，勉强能跑。但如果数据范围变成$N=100$，$V=10000$，$C=10000$，复杂度瞬间到$10^{10}$，任何OJ都扛不住。

所以多重背包的核心难题不是“怎么定义状态”，而是“怎么把$C$这个维度消掉”。这也是下面所有优化的共同目标。

2. 二进制优化：把“数量”压成“二进制块”

2.1 二进制拆分的原理：用组合代替枚举

二进制优化的出发点是一个很朴素的问题：给你$c$件相同的物品，真的需要枚举$0$到$c$的每一个数量吗？

不需要。因为我们不需要知道“选$k$件”的所有细节，只需要知道“能否凑出某个数量”以及“凑出这个数量能带来多少价值”。而任意一个$0$到$c$之间的整数，都可以用若干个$2$的幂次组合表示。

具体拆分规则是：把$c$拆成$1, 2, 4, 8, \dots, 2^m$，以及末尾剩下的$r$（$r < 2^{m+1}$）。

举个例子，$c = 13$：

$$13 = 1 + 2 + 4 + 6$$

这里$1, 2, 4$是连续的二幂次，最后剩下$6$。你可以验证一下：从$0$到$13$的任意数量，都能由$1, 2, 4, 6$这个集合中的若干个数相加得到。比如$7 = 1 + 6$，$11 = 1 + 4 + 6$，$13 = 1 + 2 + 4 + 6$。这就是二进制优化的数学基础。

为什么不用$1, 2, 4, 8$呢？因为$1 + 2 + 4 + 8 = 15 > 13$，凑出的组合会超过实际数量，导致选了“不存在的物品”。所以最后一个块必须是余数。

拆分完以后，每个块看成一个独立的01背包物品，块的大小是$k \times w$，价值是$k \times v$。原来枚举$c$次的复杂度，现在只需要枚举$\log_2 c$个块。

2.2 拆分的代码实现和边界细节

下面这段是我在实际中一直用的拆分写法：

for (int i = 1; i <= n; ++i) { int w, v, c; cin >> w >> v >> c; int k = 1; while (k <= c) { // 把大小为 k 的块作为一个新物品 goods.push_back({k * w, k * v}); c -= k; k <<= 1; // k *= 2 } if (c > 0) { goods.push_back({c * w, c * v}); } } for (auto [ww, vv] : goods) { for (int j = V; j >= ww; --j) { dp[j] = max(dp[j], dp[j - ww] + vv); } }

这里有三个特别容易踩坑的地方，我逐一说明。

第一个坑是循环里的c一直在被削减。很多人忘了c -= k，导致k虽然翻倍了，但原始数量没有被正确扣除，拆分出来的块大小总和超过原数量。每次循环把k加进goods后，必须同步从c里减掉k，这是拆分的核心逻辑。

第二个坑是最后剩下的那个零头不能丢。比如$c=10$，拆完$1, 2, 4$后剩下的$3$还有个块，如果漏掉它，总数量只有$1 + 2 + 4 = 7$，凑不出$8, 9, 10$这些数量。这个错误很隐蔽，因为大多数测试数据里$c$恰好是二幂次减一的时候不会暴露，一旦$c$是普通数字，结果就错得莫名其妙。

第三个坑是拆出来的件数$k$乘上重量$w$后可能超过容量$V$，在01背包的容量循环里直接被跳过，这是正确的，不会影响结果，但会造成一点性能浪费。如果想要更严谨，可以在拆分时加上判断：如果k * w > V，说明这个块不可能放进背包，可以不加入goods。

二进制优化后的复杂度是$O(NV \log C)$。虽然看起来还带着$\log C$，但实际运行中比朴素写法快了几个数量级。$N=100$, $V=10000$, $C=10000$的数据，朴素写法到$10^9$以上，二进制优化直接降到$10^7$左右，这就是能过和不能过的差距。

3. 单调队列优化：把多重背包压到O(NV)的原理与实现

3.1 从转移方程式推导单调队列的用法

二进制优化很好，但它是多重背包的终点吗？不是。实际上多重背包存在$O(NV)$的最优解法，这就是单调队列优化（也叫滑动窗口优化）。

我知道很多人听到“单调队列”就觉得头大，但其实它的推导过程是有迹可循的。把多重背包的状态转移写成通式：

$$dp[j] = \max_{0 \le k \le c,; k \cdot w \le j} (dp[j - k \cdot w] + k \cdot v)$$

现在做一步关键变形。固定余数$r = j \bmod w$，把容量$j$写成：

$$j = r + t \cdot w$$

其中$t = j / w$（向下取整）。代入转移方程式：

$$dp[r + t \cdot w] = \max_{0 \le k \le \min(c, t)} (dp[r + (t - k) \cdot w] + k \cdot v)$$

令$t - k = u$，则$u$的取值范围是$[t - c, t]$，于是：

$$dp[r + t \cdot w] = t \cdot v + \max_{t - c \le u \le t} (dp[r + u \cdot w] - u \cdot v)$$

观察这个式子，括号里的部分只跟$u$有关，跟$t$无关。所以对于同一个余数$r$，当$t$从$0$递增到最大值时，括号里的候选值形成一个序列，我们只需要在长度为$c$的滑动窗口内找最大值。这正好是单调队列的经典应用场景。

过程可以形象地理解成：把所有容量按余数分成$w$类，每一类内部沿着“每加一个$w$就看一格”的方向滑动窗口，每次队首就是当前窗口的最大值。

3.2 滚动数组下的旧值保护与完整实现

这里有一个非常容易忽略的细节，也是我当时第一次写单调队列优化时卡了很久的原因：dp数组在滚动更新，而计算当前物品时用到的数据必须是上一轮的结果，不能是已经被当前物品更新过的数据。

如果直接用dp数组既当输入又当输出，会发生什么？处理第一个余数类时，dp[r1 + t*w]被更新了；处理第二个余数类时，如果它的某个容量引用了第一个余数类的旧值，拿到的是新值，这就破坏了DP的“阶段性”。所以稳妥的做法是先把dp拷贝到old数组，计算时从old取数，更新到dp：

for (int i = 1; i <= n; ++i) { int w, v, c; cin >> w >> v >> c; if (c * w >= V) { // 当总重量超过背包容量，等同于完全背包 for (int j = w; j <= V; ++j) { dp[j] = max(dp[j], dp[j - w] + v); } continue; } // 保存上一轮的值 memcpy(old, dp, sizeof(old)); for (int r = 0; r < w; ++r) { // 队列存的是 u 的值，即 r + u * w 中的 u int head = 0, tail = 0; // 注意：每个余数类里面，t 从 0 开始递增 for (int t = r; t <= V; t += w, cnt++) { // cnt 当前是第几个块，也就是 t/w 向下取整 } } }

上面的代码还缺一个关键部分，就是cnt和队列的具体维护。我补一个更完整的版本，用数组模拟队列，队列里存的是下标u：

for (int i = 1; i <= n; ++i) { int w, v, c; cin >> w >> v >> c; if (c * w >= V) { for (int j = w; j <= V; ++j) { dp[j] = max(dp[j], dp[j - w] + v); } continue; } memcpy(old, dp, sizeof(old)); for (int r = 0; r < w; ++r) { int head = 0, tail = 0; // q 存的是 u，也就是商 int q[N]; int cnt = 0; for (int t = r; t <= V; t += w, ++cnt) { // 把当前 u = cnt 加入队列 int curVal = old[t] - cnt * v; while (head < tail && q[tail - 1] >= cnt - c) { // 这一行其实是多余的判断，窗口淘汰在下面处理 } // 队尾出队：如果队尾的候选值不大于当前值，则队尾永远不可能成为最优 while (head < tail && old[r + q[tail - 1] * w] - q[tail - 1] * v <= curVal) { --tail; } q[tail++] = cnt; // 队头淘汰：u < cnt - c 的超出了窗口范围 while (head < tail && q[head] < cnt - c) { ++head; } // 用队头更新 dp[t] dp[t] = old[r + q[head] * w] + (cnt - q[head]) * v; } } }

这里队列里存的是$u$，每个$u$对应的实际容量是$r + u \cdot w$。每次处理新的$t$（即新的$cnt$），先把$cnt$作为候选加入队列，再淘汰过期下标，最后从队头取值。

注意两个while循环的顺序问题。我写的时候习惯“先入队再淘汰”，但严格来说，先淘汰再入队也可以。区别在于：如果新加入的候选本身就是当前窗口内最新的值，入队前需要保证队列的单调性；而窗口淘汰是为了不让过期值留在队头。顺序上“先入队再淘汰”有一个好处：即使新值入队后马上被淘汰，也不影响结果，因为淘汰逻辑依赖的是cnt - c，不会误删当前值。不过初学者最好固定一种写法，不要每次临时变。

3.3 一个可运行的对照测试

为了验证单调队列优化的正确性，我拿一个具体例子手算过：

假设$N=2$，$V=10$：

• 物品1：$w=3$, $v=5$, $c=2$
• 物品2：$w=4$, $v=7$, $c=3$

用朴素写法和单调队列优化分别跑：

最优组合是物品1选2件（占6容量，价值10），物品2选1件（占4容量，价值7），总容量正好10，总价值17。

我在本地用这个用例测过三种写法，结果一致。如果你也写了这三种写法，建议先用这种小例子验证，再上大数据测性能，能省很多调试时间。

4. 完全背包的正序枚举写法与“转化”思路辨析

4.1 完全背包的正序循环到底在做什么

完全背包的状态转移方程和01背包长得一样，但容量遍历方向完全相反。01背包必须倒序，因为正序会导致同一件物品被重复选择；完全背包恰恰利用了这个“缺陷”。

看一个极端例子：背包容量$V=5$，一件物品重量$w=2$，价值$v=3$，无限件。

正序遍历：

• $j=2$：$dp[2] = \max(dp[2], dp[0]+3) = 3$
• $j=3$：$dp[3] = \max(dp[3], dp[1]+3) = 3$
• $j=4$：$dp[4] = \max(dp[4], dp[2]+3) = 6$

当$j=4$时，dp[2]已经在当前轮被更新成了3，所以dp[4]更新为6，相当于选了两件。这就是“正序允许重复选择”的直观体现。

这段推导值得在纸上画一遍。很多资料直接告诉你“完全背包正序，01背包倒序”，没讲本质。当你真正理解了这个方向差异的根源，以后遇到“每种物品有次数上界，且上界很大”的问题时，一眼就能判断能不能套完全背包的思路。

4.2 完全背包与其他背包的互相转化与误区

完全背包本身不需要二进制优化，这一点经常被初学者搞混。因为完全背包的朴素写法复杂度已经是$O(NV)$，如果把一个物品拆成多个块再跑01背包，复杂度反而变成了$O(NV \log(V/w))$，更差了。二进制优化是针对“有限件数”设计的，无限件数直接正序跑就行。

但反过来，多重背包在某些情况下可以“冒充”完全背包。判断条件很直接：如果物品的总重量$c \cdot w \ge V$，意味着即使把所有件数都塞进容量为$V$的背包，也塞不完。这时“数量上限”约束实际上不生效，它退化成了完全背包。我在第3节代码里用的就是这个判断：

if (c * w >= V) { // 当作完全背包处理 }

这个优化在单调队列写法里尤其有用，能省掉整个分余数类的过程。

还有一类问题是从完全背包延伸的变种，比如：

• 最小花费：求装满背包恰好需要的最少物品数
• 方案数：求装满背包有多少种不同的组合方式
• 价值随数量变化：第$k$次选某件物品时价值不同

这些变种的思路根子还是在“正序枚举”和“容量循环方向”上。做题时先把问题归类到背包模型，再决定方向，比硬套模板靠谱得多。

5. 数据范围成套测试与实战踩坑记录

5.1 不同数据范围下应该选哪种写法

我整理了一份选择表，方便你在实际做题时快速决策：

这里注意：即使理论上单调队列最优，实际做题时我也会先考虑二进制优化。原因很简单——二进制优化代码短、调试容易、出错概率低。只有数据范围明确要求必须$O(NV)$，或者单调队列能明显降低常数时才用。

5.2 实测中容易翻车的细节清单

这些坑是我在多次练习和帮别人review代码时真实遇到的，每一条都能让程序在某个测试点上挂掉：

初始化问题：如果题目要求“恰好装满”，dp[0] = 0，其他容量初始化为负数极大值（比如-0x3f3f3f3f）。如果不要求恰好装满，全部初始化为0。这两种初始化的结果完全不同，选错了边界数据肯定错。

容量循环方向：多重背包的二进制优化本质上是在跑01背包，容量必须倒序。我曾经把二进制优化后的goods当成完全背包做，正序循环，结果每一种拆出来的块都被选了无数次，答案彻底错乱。每次写完都自查一遍：这段代码代表的背包模型是什么？循环方向对不对？

单调队列的窗口大小：窗口大小是$c$，不是$c-1$，也不是$c+1$。因为最多选$c$件，所以窗口里最多有$c+1$个候选值（从0件到c件），但“最多选c件”和“窗口大小为c”在代码里对应的是q[head] < cnt - c这个淘汰条件。我建议把这个推导再走一遍：如果$u < cnt - c$，说明$(t - u) > c$，即选的件数超过了上限。理解了这一点，写淘汰条件就不会差一。

单调队列中拷贝旧数组的必要性：我在3.2节反复强调的，滚动数组下不备份old，同一个余数类的更新会污染其他余数类。个别优化写法不需要备份，但那需要非常谨慎地控制访问顺序，对新手不友好，不如老老实实memcpy一份。memcpy的性能开销可以接受，毕竟一次拷贝是$O(V)$，在整个算法里占比很小。

5.3 从多重背包到背包体系的整体思考

学完多重背包的三种写法，再回头看01背包和完全背包，能发现一个清晰的递进关系：01背包是“每件一个”的特例，完全背包是“无限供应”的特例，多重背包则位于两者之间。从朴素枚举到二进制优化，再到单调队列，优化的本质都是减少枚举的冗余度。

这种“先写朴素版本验证正确性，再逐步优化复杂度”的思路，不止适用于背包问题，也适用于其他DP问题，比如区间DP、状压DP、树形DP。我现在拿到一道DP题，习惯先确认状态定义和转移方向，再手推几组小样例，确认无误后才写优化版本。优化不是炫技，而是在朴素版本正确的基础上做减法。这个习惯帮我避免了很多“优化半天，结果基础逻辑就是错的”的尴尬。

最后再分享一个排错技巧：如果单调队列版本的答案和朴素版对不上，别急着怀疑单调队列的窗口逻辑，先把dp数组每一步的值打出来，和朴素版逐项对比。通常很快就能定位是某个余数类处理错了，还是窗口淘汰边界写错了。对比几次之后，你会发现这类问题的规律性很强，熟练了反而不容易出错。