今天刷题打卡刷到了第2685题，用 C++ 过了 P2998 [USACO10NOV] Candy S。题目名带个 Candy，看着像是模拟题，实际是动态规划里的多重背包，而且核心考点是二进制拆分优化。我一开始也吃了点亏，写完朴素的 DP 直接交了一发 TLE，后面把每种糖的数量拆成 1、2、4、8 这样二进制的“包”，才把复杂度降下来。这篇把整个推导过程和 C++ 实现完整记录下来，给同样在刷 USACO、刷背包题的朋友一个参考。

1. 先把题意翻译成人话

1.1 “买糖果”本质是一道背包题

原题的大意我用比较直白的方式描述一下：Bessie 手里有预算 B 美元，糖果店里有 N 种糖果，第 i 种糖果每颗价格是 p_i，吃掉之后能带来的甜度是 s_i，而且店里这种糖果只有 c_i 颗库存。Bessie 要买一些糖果，花的钱加起来不能超过 B，问她在预算内能拿到的最大甜度总和是多少。

翻译成算法语言就非常清晰了：

• 预算 B 就是背包容量；
• 每一颗糖果就是一个物品，价格是体积、甜度是价值；
• 第 i 种糖果最多选 c_i 颗，也就是物品有数量上限；
• 目标是在容量限制下最大化总价值。

这不就是教科书里标标准准的“多重背包”吗？凡是看到“每件物品有数量限制，选若干件，总消耗不超过某个值，让收益最大”这种句式，第一反应就应该是背包模型。USACO 特别喜欢把这种模型套上农场、糖果、奶牛的故事外壳，剥掉外壳之后其实一点都不神秘。

1.2 数据范围决定了你不能无脑枚举

很多人第一步想的是：那就暴力搜索呗，所有糖果的组合都试一遍，取甜度最大的那个。但是搜索是指数级的，就算 N 只有 30，2^30 的组合也是十亿级别，更何况库存还是多颗，完全没法枚举。

考场上拿到题目第一件事不是写代码，而是把数据范围看清楚。我记得这道题的数据范围给得不算宽松，N 大概在 100 左右，预算 B 能到 100000 这个量级，每种糖果的库存 c_i 也可能有上千。这种规模下：

• 暴力枚举：指数级，直接出局；
• 朴素的 DP：三重循环，复杂度是 N × B × c_i，约 100 × 100000 × 1000 = 10^10，必然超时；
• 二进制优化后的 DP：复杂度变成 B × log(c_i) × N，大约 100000 × 10 × 100 = 10^8，C++ 优化一下输入输出是完全可以跑的。

所以这道题真正想考的是：你能不能把一个带数量限制的背包问题，转化成没有数量限制的 01 背包问题。“转化”这个词，就是这道题的核心价值。

2. 朴素做法为什么不香

2.1 最直接的三重循环 DP

如果什么都不想，直接套多重背包的定义，可以写出这样一个状态转移。设 dp[j] 表示花不超过 j 美元能获得的最大甜度，枚举每一种糖果 i，再枚举总花费 j，再枚举这种糖果买多少颗 k：

for (int i = 0; i < N; i++) { for (int j = budget; j >= 0; j--) { for (int k = 0; k <= c[i] && k * price[i] <= j; k++) { dp[j] = max(dp[j], dp[j - k * price[i]] + k * sweet[i]); } } }

这个代码逻辑上没有任何问题，它确实能算出正确答案。问题只在效率。内层循环对每一种糖果都会把 k 从 0 枚举到 c[i]，而这个 c[i] 可能上千。

2.2 复杂度是怎么爆掉的

我们来算一笔账。假设 N = 100，B = 100000，c_i = 1000。那么总操作次数大约是：

100 × 100000 × 1000 = 10^10

10 的 10 次方是什么概念？一台普通电脑一秒能跑的简单运算大约是 10^8 到 10^9 量级，10^10 这种规模就是 10 秒到几十秒的差距，放在 OJ 上妥妥的超时。而且 DP 里还有 max 运算、取地址、数组访问，实际常数还要更大。

你可以把它类比成整理书架：你要从 100 个抽屉里挑糖果，每次还得考虑预算，最蠢的办法是把每个抽屉里的每一颗糖都单独过一遍，重复劳动多到离谱。二进制优化做的事情就是：把每个抽屉里的糖打包成少数几个标准包，用组合的方式拼出任意数量，整件事一下子就轻了。

2.3 01、完全、多重，区别就在一个“数量”

这三种背包是亲兄弟，核心区别只有一条：

• 01 背包：每种物品最多拿 1 个；
• 完全背包：每种物品可以拿无限个；
• 多重背包：每种物品最多拿固定数量 c[i] 个。

从代码上看，01 背包用滚动数组的时候内层循环要倒序，完全背包要正序，而多重背包是第三种状态。很多初学者背代码背了半天，却不知道为什么要这么写，一到路变体题目就懵。其实这几种背包的关系是：完全背包是 c[i] = 无穷大的多重背包，01 背包是 c[i] = 1 的多重背包。如果你能把多重背包的“数量限制”消掉，它就变回 01 背包，那么代码也好、正确性证明也好，都会统一起来。P2998 这道题就是逼着你做这个消去操作。

3. 二进制优化：把“数量”拍平成“物品”

3.1 为什么拆成 1、2、4、8 就够了

二进制优化的核心思路是：不需要把 c[i] 颗糖果拆成 c[i] 个单独物品，那样又回到三重循环的老路。而是把 c[i] 拆成 1、2、4、8、… 这样一组二的幂次，再补上最后一个余数。

例如 c[i] = 13，可以拆成：

1、2、4、6

注意最后不是 8，因为 1+2+4+8 = 15 > 13，所以拆完 1、2、4 之后还剩 6，把 6 单独作为一组。于是 13 颗糖果变成了 4 个打包好的“物品包”：

• 1 颗糖一包；
• 2 颗糖一包；
• 4 颗糖一包；
• 6 颗糖一包。

接下来的问题是：这 4 个包能不能组合出 0 到 13 的任意数量？答案是能。这背后的道理就是二进制计数。1、2、4 可以组合出 0 到 7 的任意整数，在这个基础上加上 6，就能往后覆盖到 13。比如 8 = 6 + 2，9 = 6 + 2 + 1，10 = 6 + 4，13 = 6 + 4 + 2 + 1。一个不落。

为什么这个性质成立？我习惯用一个砝码的类比来解释：你不需要准备 13 个 1g 砝码才能称出 1 到 13g 的重量，只要准备 1g、2g、4g、6g 这四个砝码就够了。二进制优化的本质就是把“重复的单个物品”压缩成“可以组合的标准包”。

3.2 组合覆盖性的严谨证明

光有感觉还不够，信奥题讲究逻辑闭环。我们用一个比较形式化的说法证明“拆出来的包能组合出 0 到 c[i] 任意数量”。

假设循环拆出来的二的幂次组是 1、2、4、…、2^k，它们的总和是 2^(k+1) - 1，记为 S。最后剩下的余数是 r，满足 r < 2^(k+1)，并且 S + r = c[i]。

现在任取 x ∈ [0, c[i]]：

• 如果 x ≤ S，那么直接用 1、2、4、…、2^k 的二进制表示就能把 x 凑出来；
• 如果 x > S，那就先取 r 这组，剩下的 x - r 一定落在 0 到 S 之间，再用二进制组凑出来。

这个证明虽然简短，但它是二进制优化“为什么不丢解”的根基。写代码的时候可以不用每一步都在脑子里跑这个证明，但理解它能帮你避免边界写错。

3.3 拆完之后就变成了 01 背包

一旦我们把每种糖果都拆成若干个“组合包”，每个包的使用次数就只能是 0 或 1。你不可能把一个包拆开一半来用，因为包里是固定颗数的糖，你要么整包拿，要么整包不拿。这就是一个不折不扣的 01 背包问题。

01 背包用滚动数组的时候有个铁律：内层循环必须从大往小扫。原因是 dp[j] 的定义是“花不超过 j 能获得的最大甜度”，如果你正着扫，更新 dp[j] 的时候可能已经用到了本轮刚更新过的 dp[j - price]，那同一包糖就被重复使用了一次，性质悄悄从 01 背包变成了完全背包，答案就会偏大。

倒序扫的话，dp[j - price] 还停留在上一轮的状态，也就是说这个包还没被用过，正好符合“每个包最多用一次”的条件。这个细节我在刚开始学背包时至少踩过三次，后来养成习惯：只要看到只用一维数组做 01 背包，下意识就是 for (int j = budget; j >= price; j--)。

3.4 顺带一提：还有更进一步的单调队列优化

二进制优化把多重背包复杂度从 O(N × B × c) 降到 O(N × B × log c)，已经足够应付 P2998 这道题了。但如果你想继续往深处走，多重背包还有一种更极限的优化：单调队列优化，可以让复杂度变成 O(N × B)。原理是把同余类的状态分开，用滑动窗口维护最大值，每次转移只需要 O(1)。这个做法比较进阶，Lo题里一般用不到，但竞赛更高级别很常见。我建议先把二进制优化的思想吃透，再去碰单调队列，否则很容易被状态之间的余数关系绕晕。

4. C++ 完整实现：带注释的 AC 代码

4.1 读入与二进制拆分

我习惯把每种糖果的信息先读进来，边读边拆，直接生成一个“新物品列表”。这样后面 DP 的时候，只需要对物品列表做一遍 01 背包，代码结构非常干净。

#include <bits/stdc++.h> using namespace std; struct Item { long long price; // 这包糖果的总价格 long long sweet; // 这包糖果的总甜度 }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long budget; cin >> n >> budget; vector<Item> items; for (int i = 0; i < n; i++) { long long p, s, c; cin >> p >> s >> c; // 二进制拆分：把 c 颗糖拆成 1、2、4、... 和最后一个余数 long long k = 1; while (c >= k) { items.push_back({p * k, s * k}); c -= k; k <<= 1; } if (c > 0) { items.push_back({p * c, s * c}); } } // 此时 items 里每个元素都是一个只能选一次的“糖果包” // 问题退化为普通的 01 背包 vector<long long> dp(budget + 1, 0); for (const auto &it : items) { for (long long j = budget; j >= it.price; j--) { dp[j] = max(dp[j], dp[j - it.price] + it.sweet); } } cout << dp[budget] << '\n'; return 0; }

4.2 代码逐段说明

输入部分我开了ios::sync_with_stdio(false)和cin.tie(nullptr)。这是 C++ 选手的基本操作：解绑 C 标准库同步之后，cin的读入速度会快很多，避免在输入规模稍大的时候被 IO 卡住。

二进制拆分的while (c >= k)是整个代码的灵魂。以 c = 13 为例，循环过程是：

• 初始 c = 13，k = 1，c >= 1，拆出 1 包，c 变成 12，k 变成 2；
• c = 12，k = 2，拆出 2 包，c 变成 10，k 变成 4；
• c = 10，k = 4，拆出 4 包，c 变成 6，k 变成 8；
• c = 6，k = 8，条件 c >= k 不成立，退出循环；
• 最后 c = 6，拆出 6 包。

最终得到 1、2、4、6 四组，对 13 的覆盖我们已经验证过了。

4.3 为什么要用 long long

题目里价格和甜度的乘积很容易超过 int 的表示范围。假设一种糖单价 10000，库存 1000，那么一包拆下来就是 10^7，再乘上预算维度的累加，dp 数组里的值可能更大。用long long多花不了多少内存，却能避免很多莫名其妙的溢出错误。USACO 这类题对数据类型常常不设防，我见过太多选手因为 int 溢出，答案变成一个很离谱的负数的惨案。

4.4 滚动数组的空间优势

如果开二维数组dp[i][j]表示前 i 种糖果在预算 j 下的最大甜度，空间复杂度是 O(N × B)，100 × 100000 约为 10^7 个 long long，也就是 80MB 左右，在有些 OJ 上会很紧张。滚动数组把空间压到 O(B)，还能保留上一轮状态的信息，一举两得。唯一的代价就是要记住 01 背包倒序的规则。

5. 实战中踩过的坑与排查速查表

5.1 答案突然变大？检查循环是否倒序

这是最经典的一个坑。如果你把主循环写成：

for (long long j = it.price; j <= budget; j++) { dp[j] = max(dp[j], dp[j - it.price] + it.sweet); }

那就从 01 背包变成了完全背包。因为正序循环里，dp[j - it.price]可能是本轮已经放进去同一个包之后的状态，等于同一个包被反复使用了多次，甜度自然虚高。现象就是样例可能碰巧对了，一旦数据变大，答案就比正确答案大很多。遇到这种症状，第一反应砍自己的循环方向。

5.2 答案偏小？大概率是二进制拆分少拆了

拆分的时候while (c >= k)循环正常结束后，如果忘了处理剩余的量，也就是漏掉了if (c > 0)这一句，那 c 里剩下的那一坨糖果就永远不会被考虑。比如 c = 13 拆出 1、2、4 之后还剩 6，你忘了把它加进去，那么所有需要 7 到 13 这个范围的组合都会无法达到，答案偏小就是必然的。

5.3 运行时报错？检查数组下标越界

如果用朴素写法，第三层 k 循环里dp[j - k * price[i]]这个下标很容易因为 k 枚举过头而变成负数。解决办法是每次访问前判断k * price[i] <= j。如果是二进制优化后的 01 背包，判断条件简单很多，就是j >= it.price。这个边界看起来简单，但一旦写错，OJ 报的往往是 RE 而不是 WA，定位起来更费劲。

5.4 初始化到底是用 0 还是 -INF

这取决于题目问的是“不超过预算”还是“恰好花完预算”。这道题问的是“花不超过 B 美元能获得的最大甜度”，所以dp数组全部初始化为 0 就可以了。如果题目改问“恰好花完 B 美元”，那初始化就要变成dp[0] = 0，其他位置为负无穷，最后还要判断dp[B]是否仍然是负无穷。这两个模型在背包题里反复出现，我每次写题之前都会先对着原题读一遍，确认是“不超过”还是“恰好”。

5.5 常见问题速查表

6. 刷题打卡复盘：这道题让我想明白的事

6.1 陌生题怎么翻译成已知模型

我刷题很看重“翻译”这一步。拿到 Candy S 这种故事性强的题目，第一步不是想“怎么买糖”，而是想“这是什么结构”。它有容量、有物品、有数量上限、有最大化收益，四个要素齐全，那就是背包问题。先定模型，再看数据范围，选择优化手段，最后写代码。这个流程走通了，USACO 很多看似刁钻的题其实都是老朋友换马甲。

6.2 二进制优化值得多写几遍

二进制拆分看起来只有几行代码，但真正闭卷手写还是容易在边界上出问题。我建议刷题的朋友在纸上多推几个例子，比如 c = 1、c = 2、c = 7、c = 8、c = 10，手动拆一遍，再对着代码验证。写多了之后，你会形成一种条件反射：看到多重背包就想到拆包，看到拆包就想会不会丢组合，这个肌肉记忆在考场上能帮你省下大量调试时间。

6.3 这道题的后续扩展方向

做完这道题之后，我还顺手把同类的题目又看了一遍。比如完全背包和多重背包混合出现的场景，再比如把“价格”换成一个不能被简单求和的维度、变成二维费用背包，思路都是一样的。如果你想测试自己是不是真懂了二进制优化，可以试着重构一下：不用 vector 存物品，而是直接在 DP 循环里对每组拆分做一次 01 背包转移，内存占用会更小，代码也更紧凑。

我个人经验是：背包专题的题,不要光刷数量，每刷一道都要想清楚它的状态定义、转移来源和优化动机。像 P2998 这种题，它就那么几行核心代码，真正值钱的不是代码，而是那个“把多拆成一、把复杂拆成简单”的思考方式。后面再遇到类似的题，稍微变一变壳子，你就不会再慌了。