企业官网建设流程全解析

1. 从一道题说起：为什么暴力解法一定会超时

第一次在题库里刷到这道题的时候，我盯着题目看了大概三分钟，脑子里第一反应就是——这不就是个背包吗，直接套模板不就完了。结果提交上去，红色的超时提示直接把我打回原形。后来仔细一算数据范围，才发现自己太天真了。

这道题的核心场景是这样的：有若干种物品，每种物品有有限个，每种物品有自己的重量和价值，背包有一个固定的容量上限，要求在容量允许的范围内选出总价值最大的组合。如果你之前只接触过01背包和完全背包，可能会觉得多重背包无非就是在这两者之间取个中间态——每种物品既不是只能拿一个，也不是能拿无限个，而是有一个明确的数量上限。

但恰恰是这个“有限个”的限制，让问题的复杂度上了一个台阶。01背包里每种物品只有“拿”和“不拿”两个选择，状态转移非常干净；完全背包虽然物品无限，但正序遍历容量就能自然处理重复选取；而多重背包，每种物品有 $c_i$ 个，最朴素的思路就是把 $c_i$ 个相同物品摊开当成 $c_i$ 个独立的01背包物品来处理。这个思路本身没错，但问题在于——当 $c_i$ 很大的时候，物品总数会爆炸。

我举个具体的例子你就明白了。假设有 $n = 100$ 种物品，每种物品最多有 $c_i = 1000$ 个，背包容量 $V = 10000$。如果暴力拆分，物品总数就变成了 $100 \times 1000 = 100000$ 个，然后对每个物品做一次容量遍历，时间复杂度就是 $O(100000 \times 10000) = 10^9$。这个量级在大多数评测环境下基本就是一两秒起步，稍微卡紧一点就直接超时。而如果 $n$ 和 $c_i$ 再大一些，比如 $n = 1000$，$c_i = 10000$，那暴力拆分的复杂度直接飙到 $10^{11}$ 级别，根本跑不动。

所以这道题真正考察的不是“你会不会背包”，而是“你能不能用更聪明的方式处理数量”。二进制优化就是解决这个问题的经典手段，它能把每种物品的拆分数量从 $c_i$ 降到 $O(\log c_i)$，整体复杂度从 $O(V \sum c_i)$ 降到 $O(V \sum \log c_i)$，这个提升在数据量大的时候是质变级别的。

这篇文章我会从这道题出发，把多重背包的二进制优化从头到尾讲透。不管你是刚学完01背包想进阶的新手，还是刷题时被多重背包卡住的老手，我都会把思路推导、代码实现、边界处理、常见坑点这些东西掰开揉碎讲清楚。你看完之后，应该能直接把这套方法套到类似的题目上去。

2. 多重背包的本质与二进制优化的核心逻辑

2.1 多重背包到底在解决什么问题

先把问题定义说清楚。多重背包的标准描述是：有 $n$ 种物品，第 $i$ 种物品的重量为 $w_i$，价值为 $v_i$，数量为 $c_i$。背包的容量为 $V$。每种物品最多选 $c_i$ 个，求在总重量不超过 $V$ 的前提下，能获得的最大总价值。

和01背包对比一下就很清楚了：01背包是 $c_i = 1$ 的特例，完全背包是 $c_i = \infty$ 的特例。多重背包处在中间，每种物品有一个有限的上限。

最直接的转化思路就是把第 $i$ 种物品的 $c_i$ 个副本全部展开，变成 $\sum c_i$ 个独立的物品，每个物品只能选一次，然后跑01背包。这个转化在逻辑上完全正确，因为“第 $i$ 种物品选 $k$ 个”等价于“在前 $k$ 个副本中每个都选，后面的副本都不选”。但正如前面分析的，当 $c_i$ 很大时，这个展开会让物品数量急剧膨胀。

那有没有办法在不展开所有副本的前提下，仍然能表示“选任意 $0$ 到 $c_i$ 个”的所有情况呢？这就是二进制优化要解决的问题。

2.2 二进制拆分为什么能覆盖所有选取数量

二进制优化的核心思想其实非常朴素：任何一个正整数都可以表示成若干个2的幂次之和。比如 $13 = 1 + 4 + 8$，$7 = 1 + 2 + 4$，$10 = 1 + 2 + 3 + 4$（注意最后一个不是2的幂，后面会解释）。

具体做法是：对于数量为 $c_i$ 的第 $i$ 种物品，我们把它拆分成若干个“捆绑包”，每个捆绑包里有 $2^0, 2^1, 2^2, \ldots$ 个该物品，直到剩余数量不足以构成下一个2的幂次为止，最后把剩余的部分单独作为一个捆绑包。

拿 $c_i = 13$ 来举例。我们依次取 $1, 2, 4$，这三个捆绑包加起来是 $1 + 2 + 4 = 7$ 个，还剩 $13 - 7 = 6$ 个。因为 $6 < 8$（下一个2的幂次），所以把剩下的 $6$ 个作为一个独立的捆绑包。最终拆分结果是：$1, 2, 4, 6$ 这四个捆绑包。

为什么这样拆能覆盖 $0$ 到 $13$ 的所有数量？你可以这样想：$1, 2, 4$ 这三个捆绑包通过选或不选，能组合出 $0$ 到 $7$ 之间的任意整数（这就是二进制的基本性质）。而最后一个捆绑包是 $6$，当我们把它加进来的时候，能覆盖的范围就变成了 $[0, 7] \cup [6, 13] = [0, 13]$。因为 $6 \leq 7 + 1$，两个区间有重叠，所以中间没有断档。这个条件是关键：最后一个捆绑包的大小不能超过前面所有捆绑包之和加一，否则就会出现无法表示的数量。

再验证一下 $c_i = 10$ 的情况。依次取 $1, 2, 4$，加起来是 $7$，还剩 $3$。因为 $3 < 8$，所以最后一个捆绑包是 $3$。拆分结果是 $1, 2, 4, 3$。这四个数能组合出 $0$ 到 $10$ 的所有整数吗？$1, 2, 4$ 能覆盖 $[0, 7]$，加上 $3$ 之后能覆盖 $[3, 10]$，两个区间合并是 $[0, 10]$，确实没有遗漏。

你可以自己拿几个数验证一下，比如 $c_i = 1$ 时只拆出 $1$；$c_i = 2$ 时拆出 $1, 1$（因为取 $1$ 之后剩 $1$，$1 < 2$，所以第二个捆绑包是 $1$）；$c_i = 3$ 时拆出 $1, 2$；$c_i = 4$ 时拆出 $1, 2, 1$。每一种拆分都能完整覆盖 $0$ 到 $c_i$ 的所有取值。

2.3 拆分后的复杂度分析

拆分的数量从 $c_i$ 降到了多少？对于数量 $c_i$，拆出的捆绑包个数大约是 $\lfloor \log_2 c_i \rfloor + 1$。比如 $c_i = 1000$ 时，拆出 $1, 2, 4, 8, 16, 32, 64, 128, 256, 489$，一共 $10$ 个捆绑包，而原来需要 $1000$ 个。$c_i = 10000$ 时，拆出大约 $14$ 个捆绑包。这个压缩比在 $c_i$ 越大的时候越明显。

整体时间复杂度从 $O(V \sum c_i)$ 降到了 $O(V \sum \log c_i)$。还是拿前面的例子：$n = 100$，$c_i = 1000$，$V = 10000$，优化前是 $10^9$，优化后大约是 $10000 \times 100 \times 10 = 10^7$，差了整整一百倍。这个差距在评测环境里就是“超时”和“轻松通过”的区别。

注意：二进制优化之后的每个捆绑包在01背包的意义下是“不可分割”的，也就是说你要么选整个捆绑包，要么不选。但因为捆绑包的组合能覆盖所有可能的选取数量，所以最终结果和暴力展开是完全等价的。

3. 代码实现：从拆分到状态转移的完整流程

3.1 二进制拆分的代码模板

先看拆分部分的代码。这部分是整个算法的预处理阶段，目标是把每种物品的多个副本转化成若干个01背包物品。

// 二进制拆分 int cnt = 0; // 拆分后的物品总数 for (int i = 0; i < n; i++) { int k = 1; // 当前捆绑包的大小 int remain = c[i]; // 剩余数量 while (k <= remain) { cnt++; w_new[cnt] = k * w[i]; // 捆绑包的重量 v_new[cnt] = k * v[i]; // 捆绑包的价值 remain -= k; k <<= 1; // k *= 2 } if (remain > 0) { cnt++; w_new[cnt] = remain * w[i]; v_new[cnt] = remain * v[i]; } }

这段代码的逻辑很直白：用 $k = 1, 2, 4, 8, \ldots$ 去不断从剩余数量中扣除，每次扣除后把对应的捆绑包记录下来。当 $k$ 超过剩余数量时，退出循环，如果还有剩余就单独打包。

有一个细节需要注意：循环条件是k <= remain而不是k < remain。当k == remain时，说明剩余数量刚好等于当前捆绑包大小，直接打包即可，不需要再走后面的if (remain > 0)分支。这个边界条件如果写错了，可能会导致多出一个大小为 $0$ 的捆绑包，虽然不影响正确性，但会浪费一次状态转移。

3.2 01背包状态转移的复用

拆分完成之后，剩下的就是标准的01背包了。因为每个捆绑包只能选一次，所以容量要倒序遍历。

// 01背包状态转移 for (int i = 1; i <= cnt; i++) { for (int j = V; j >= w_new[i]; j--) { dp[j] = max(dp[j], dp[j - w_new[i]] + v_new[i]); } }

这里的dp[j]表示容量为 $j$ 时能获得的最大价值。倒序遍历的原因是保证每个捆绑包只被使用一次——如果正序遍历，同一个捆绑包可能会被重复选取，那就变成了完全背包的行为。

最终答案是dp[V]，即在容量不超过 $V$ 的情况下能获得的最大价值。

3.3 完整代码与关键注释

把上面的两部分拼起来，就是完整的解题代码：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; // 拆分后的最大物品数 const int MAXV = 100005; // 最大容量 int w[MAXN], v[MAXN], c[MAXN]; // 原始物品的重量、价值、数量 int w_new[MAXN], v_new[MAXN]; // 拆分后的物品 int dp[MAXV]; int main() { int n, V; cin >> n >> V; for (int i = 0; i < n; i++) { cin >> w[i] >> v[i] >> c[i]; } // 二进制拆分 int cnt = 0; for (int i = 0; i < n; i++) { int k = 1; int remain = c[i]; while (k <= remain) { cnt++; w_new[cnt] = k * w[i]; v_new[cnt] = k * v[i]; remain -= k; k <<= 1; } if (remain > 0) { cnt++; w_new[cnt] = remain * w[i]; v_new[cnt] = remain * v[i]; } } // 01背包 memset(dp, 0, sizeof(dp)); for (int i = 1; i <= cnt; i++) { for (int j = V; j >= w_new[i]; j--) { dp[j] = max(dp[j], dp[j - w_new[i]] + v_new[i]); } } cout << dp[V] << endl; return 0; }

数组大小要根据题目的数据范围来定。拆分后的物品总数上界是 $n \times (\lfloor \log_2 \max(c_i) \rfloor + 1)$，容量上界就是题目给的 $V$。如果题目没有明确给出范围，建议开大一点，避免越界。

提示：如果题目要求的是“恰好装满”而不是“不超过容量”，初始化时需要把dp[0]设为 $0$，其余设为负无穷。这个细节在01背包里很常见，但在多重背包的题目里容易被忽略。

4. 实操中容易踩的坑与排查方法

4.1 拆分逻辑写错导致覆盖不全

这是最常见的问题。我见过不少人把拆分写成这样：

// 错误写法 int k = 1; while (k < remain) { // ... remain -= k; k <<= 1; } // 剩下的 remain 直接丢弃

这个写法的错误在于：当循环结束时，remain可能还有剩余，但代码没有处理。比如 $c_i = 13$，循环过程是 $k=1$ 扣掉剩 $12$，$k=2$ 扣掉剩 $10$，$k=4$ 扣掉剩 $6$，$k=8$ 时因为 $8 > 6$ 退出循环，此时remain = 6没有被处理。结果就是只能表示 $0$ 到 $7$ 的数量，$8$ 到 $13$ 全部丢失。

正确的做法是在循环结束后加一个判断，把剩余的remain单独打包。这个细节看起来简单，但在紧张的比赛环境下很容易漏掉。

4.2 容量遍历方向搞反

二进制优化之后跑的是01背包，容量必须倒序遍历。如果写成正序，每个捆绑包会被重复选取，结果就变成了完全背包，答案会偏大。

我自己的排查方法是：拿一个简单的测试用例手动验证。比如只有一种物品，重量为 $1$，价值为 $1$，数量为 $2$，背包容量为 $3$。正确结果是 $2$（选两个）。如果容量正序遍历，结果会变成 $3$（因为捆绑包被重复选了），一眼就能看出问题。

4.3 数组越界与初始化问题

拆分后的物品数量可能比原始物品数量大很多，如果数组只开了原始物品的大小，就会越界。建议在写代码之前先估算一下上界：$n \times 20$ 通常是一个安全的值（因为 $2^{20} \approx 10^6$，足够覆盖大多数题目的数量范围）。

另外，dp数组的初始化也要注意。如果题目要求“不超过容量”，全部初始化为 $0$ 即可；如果要求“恰好装满”，除了dp[0] = 0之外，其余要初始化为负无穷。这个区别在最终答案上可能差很多。

4.4 常见问题速查表

5. 从这道题延伸出去：二进制优化的适用场景与变体

5.1 什么时候该用二进制优化

二进制优化不是万能的，它的适用场景有一个明确的判断标准：每种物品的数量有限，且数量较大，暴力展开会导致复杂度过高。

如果每种物品的数量都很小（比如 $c_i \leq 10$），那直接暴力展开反而更简单，代码也不容易出错。如果每种物品的数量是无限的，那应该用完全背包的正序遍历，不需要拆分。只有当 $c_i$ 处于“有限但较大”的区间时，二进制优化才是最优选择。

具体来说，当 $\sum c_i$ 超过 $10^5$ 或者 $10^6$ 级别时，就应该考虑二进制优化了。如果 $\sum c_i$ 只有几百，暴力展开完全没问题。

5.2 单调队列优化：另一种思路

除了二进制优化，多重背包还有另一种优化方式叫单调队列优化，可以把复杂度进一步降到 $O(nV)$。它的核心思想是利用滑动窗口维护状态转移的最大值，避免重复计算。

不过单调队列优化的代码实现比二进制优化复杂不少，需要维护一个双端队列，处理起来容易出错。在大多数题目里，二进制优化的 $O(V \sum \log c_i)$ 已经足够通过，没必要为了那一点常数优化去写更复杂的代码。除非题目的数据范围特别大（比如 $n = 10^5$，$V = 10^5$），否则二进制优化是性价比最高的选择。

5.3 混合背包的处理方式

有些题目会把01背包、完全背包、多重背包混在一起考。比如有的物品只能选一次，有的可以选无限次，有的有数量上限。这种混合背包的处理方式是：分类处理，各用各的方法。

• 01背包物品：倒序遍历容量
• 完全背包物品：正序遍历容量
• 多重背包物品：二进制拆分后按01背包处理

三种情况分开写，逻辑清晰，不容易出错。我在实际刷题中遇到混合背包的时候，通常会先把所有物品分类，然后依次处理每一类，这样代码结构比较清楚。

5.4 二进制优化在其它问题中的应用

二进制优化的思想不仅限于背包问题。任何需要“表示一个有限范围内的所有整数”的场景，都可以用到类似的拆分技巧。比如：

• 多重集合的选取问题：给定若干种元素，每种有有限个，问能否选出总和为某个值的子集。
• 资源分配问题：有限的资源分配给多个任务，每个任务有上限，求最优分配方案。
• 游戏中的道具合成：有限数量的材料，每种材料有使用上限，求最大收益。

这些问题的底层逻辑和多重背包是一样的，都可以用二进制拆分来降低状态空间。

6. 一些实战中的经验与建议

刷题刷到一定程度之后，我发现一个规律：背包问题的难点从来不在状态转移方程本身，而在于如何根据数据范围选择合适的优化方式。01背包的方程就那一行，完全背包也就改个遍历方向，多重背包的二进制拆分也就十几行代码。但为什么很多人还是会在这些题上卡住？因为题目不会直接告诉你“这是多重背包，请用二进制优化”，你需要自己从题目描述和数据范围中判断出来。

我的习惯是：拿到一道题，先看数据范围。如果物品数量少、容量小，直接暴力；如果物品数量多但每种只有一个，那是01背包；如果每种有无限个，那是完全背包；如果每种有有限个且数量较大，那就上二进制优化。这个判断流程走下来，基本不会选错方法。

另外一个经验是：写完代码之后一定要手动造几个边界用例测试。比如数量为 $1$ 的情况、数量刚好是2的幂次的情况、容量为 $0$ 的情况、所有物品都装不下的情况。这些边界用例能帮你发现大部分逻辑错误，比盲目提交等评测结果高效得多。

最后说一个关于代码风格的建议。二进制拆分的代码虽然不长，但涉及的变量比较多（原始重量、原始价值、原始数量、拆分后重量、拆分后价值、拆分后总数），命名一定要清晰。我通常会用w_orig、v_orig、c_orig表示原始数据，用w_bin、v_bin表示拆分后的数据，这样读代码的时候不容易搞混。变量命名清晰了，调试的时候也能省不少时间。

这道题本身并不复杂，但它是一个很好的切入点，能帮你把多重背包的整个知识体系串起来。从暴力展开到二进制优化，从01背包到混合背包，从状态转移到边界处理，这些东西在后续刷题中会反复出现。把这套方法吃透了，再遇到类似的题目就是降维打击。