今天刷题打卡刷到了第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 只有 302^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^8C 优化一下输入输出是完全可以跑的。所以这道题真正想考的是你能不能把一个带数量限制的背包问题转化成没有数量限制的 01 背包问题。“转化”这个词就是这道题的核心价值。2. 朴素做法为什么不香2.1 最直接的三重循环 DP如果什么都不想直接套多重背包的定义可以写出这样一个状态转移。设 dp[j] 表示花不超过 j 美元能获得的最大甜度枚举每一种糖果 i再枚举总花费 j再枚举这种糖果买多少颗 kfor (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 100B 100000c_i 1000。那么总操作次数大约是100 × 100000 × 1000 10^1010 的 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因为 1248 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 29 6 2 110 6 413 6 4 2 1。一个不落。为什么这个性质成立我习惯用一个砝码的类比来解释你不需要准备 13 个 1g 砝码才能称出 1 到 13g 的重量只要准备 1g、2g、4g、6g 这四个砝码就够了。二进制优化的本质就是把“重复的单个物品”压缩成“可以组合的标准包”。3.2 组合覆盖性的严谨证明光有感觉还不够信奥题讲究逻辑闭环。我们用一个比较形式化的说法证明“拆出来的包能组合出 0 到 c[i] 任意数量”。假设循环拆出来的二的幂次组是 1、2、4、…、2^k它们的总和是 2^(k1) - 1记为 S。最后剩下的余数是 r满足 r 2^(k1)并且 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; vectorItem 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 背包 vectorlong 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 13k 1c 1拆出 1 包c 变成 12k 变成 2c 12k 2拆出 2 包c 变成 10k 变成 4c 10k 4拆出 4 包c 变成 6k 变成 8c 6k 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 常见问题速查表症状可能原因验证方法解决办法答案比预期大01背包循环写成正序输出中间 dp 数组改为倒序循环答案比预期小二进制拆分漏掉剩余组检查拆分后物品个数补上if (c 0)超时三重循环朴素多重背包估算复杂度使用二进制优化RE 或越界下标访问负数打印 j 和 price加边界判断负数答案int 溢出检查价格甜度乘积全部改用 long long6. 刷题打卡复盘这道题让我想明白的事6.1 陌生题怎么翻译成已知模型我刷题很看重“翻译”这一步。拿到 Candy S 这种故事性强的题目第一步不是想“怎么买糖”而是想“这是什么结构”。它有容量、有物品、有数量上限、有最大化收益四个要素齐全那就是背包问题。先定模型再看数据范围选择优化手段最后写代码。这个流程走通了USACO 很多看似刁钻的题其实都是老朋友换马甲。6.2 二进制优化值得多写几遍二进制拆分看起来只有几行代码但真正闭卷手写还是容易在边界上出问题。我建议刷题的朋友在纸上多推几个例子比如 c 1、c 2、c 7、c 8、c 10手动拆一遍再对着代码验证。写多了之后你会形成一种条件反射看到多重背包就想到拆包看到拆包就想会不会丢组合这个肌肉记忆在考场上能帮你省下大量调试时间。6.3 这道题的后续扩展方向做完这道题之后我还顺手把同类的题目又看了一遍。比如完全背包和多重背包混合出现的场景再比如把“价格”换成一个不能被简单求和的维度、变成二维费用背包思路都是一样的。如果你想测试自己是不是真懂了二进制优化可以试着重构一下不用 vector 存物品而是直接在 DP 循环里对每组拆分做一次 01 背包转移内存占用会更小代码也更紧凑。我个人经验是背包专题的题,不要光刷数量每刷一道都要想清楚它的状态定义、转移来源和优化动机。像 P2998 这种题它就那么几行核心代码真正值钱的不是代码而是那个“把多拆成一、把复杂拆成简单”的思考方式。后面再遇到类似的题稍微变一变壳子你就不会再慌了。 
长河君 · 2026/10/23 22:20:42 · 阅读 1.2k 多重背包二进制优化：从USACO Candy S看C++背包问题高效解法
今天刷题打卡刷到了第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 只有 302^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^8C 优化一下输入输出是完全可以跑的。所以这道题真正想考的是你能不能把一个带数量限制的背包问题转化成没有数量限制的 01 背包问题。“转化”这个词就是这道题的核心价值。2. 朴素做法为什么不香2.1 最直接的三重循环 DP如果什么都不想直接套多重背包的定义可以写出这样一个状态转移。设 dp[j] 表示花不超过 j 美元能获得的最大甜度枚举每一种糖果 i再枚举总花费 j再枚举这种糖果买多少颗 kfor (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 100B 100000c_i 1000。那么总操作次数大约是100 × 100000 × 1000 10^1010 的 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因为 1248 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 29 6 2 110 6 413 6 4 2 1。一个不落。为什么这个性质成立我习惯用一个砝码的类比来解释你不需要准备 13 个 1g 砝码才能称出 1 到 13g 的重量只要准备 1g、2g、4g、6g 这四个砝码就够了。二进制优化的本质就是把“重复的单个物品”压缩成“可以组合的标准包”。3.2 组合覆盖性的严谨证明光有感觉还不够信奥题讲究逻辑闭环。我们用一个比较形式化的说法证明“拆出来的包能组合出 0 到 c[i] 任意数量”。假设循环拆出来的二的幂次组是 1、2、4、…、2^k它们的总和是 2^(k1) - 1记为 S。最后剩下的余数是 r满足 r 2^(k1)并且 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; vectorItem 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 背包 vectorlong 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 13k 1c 1拆出 1 包c 变成 12k 变成 2c 12k 2拆出 2 包c 变成 10k 变成 4c 10k 4拆出 4 包c 变成 6k 变成 8c 6k 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 常见问题速查表症状可能原因验证方法解决办法答案比预期大01背包循环写成正序输出中间 dp 数组改为倒序循环答案比预期小二进制拆分漏掉剩余组检查拆分后物品个数补上if (c 0)超时三重循环朴素多重背包估算复杂度使用二进制优化RE 或越界下标访问负数打印 j 和 price加边界判断负数答案int 溢出检查价格甜度乘积全部改用 long long6. 刷题打卡复盘这道题让我想明白的事6.1 陌生题怎么翻译成已知模型我刷题很看重“翻译”这一步。拿到 Candy S 这种故事性强的题目第一步不是想“怎么买糖”而是想“这是什么结构”。它有容量、有物品、有数量上限、有最大化收益四个要素齐全那就是背包问题。先定模型再看数据范围选择优化手段最后写代码。这个流程走通了USACO 很多看似刁钻的题其实都是老朋友换马甲。6.2 二进制优化值得多写几遍二进制拆分看起来只有几行代码但真正闭卷手写还是容易在边界上出问题。我建议刷题的朋友在纸上多推几个例子比如 c 1、c 2、c 7、c 8、c 10手动拆一遍再对着代码验证。写多了之后你会形成一种条件反射看到多重背包就想到拆包看到拆包就想会不会丢组合这个肌肉记忆在考场上能帮你省下大量调试时间。6.3 这道题的后续扩展方向做完这道题之后我还顺手把同类的题目又看了一遍。比如完全背包和多重背包混合出现的场景再比如把“价格”换成一个不能被简单求和的维度、变成二维费用背包思路都是一样的。如果你想测试自己是不是真懂了二进制优化可以试着重构一下不用 vector 存物品而是直接在 DP 循环里对每组拆分做一次 01 背包转移内存占用会更小代码也更紧凑。我个人经验是背包专题的题,不要光刷数量每刷一道都要想清楚它的状态定义、转移来源和优化动机。像 P2998 这种题它就那么几行核心代码真正值钱的不是代码而是那个“把多拆成一、把复杂拆成简单”的思考方式。后面再遇到类似的题稍微变一变壳子你就不会再慌了。