完全背包问题在动态规划里算是个分水岭。不是因为它难而是因为它第一次把状态从哪一层转移过来这件事摆到了台面上——很多人 01 背包写得行云流水一遇到完全背包就翻车代码只差一个减号或者一个遍历方向结果天差地别。我最早接触这道题的时候也是背下了一维写法外层物品、内层容量正序、五行代码、提交就过。但真被人追问为什么正序就对、逆序就错的时候我卡了大概十几秒那种感觉很不好受。后来我把这道题的优化过程从头到尾推了三遍从最暴力的三层循环到 O(NW) 的最终形态中间每一步为什么能省、省掉的是什么才算真正想明白。这篇就把这条优化链完整摊开讲涉及完全背包问题的状态定义、转移方程的推导、滚动数组降维的语义变化、支配关系剪枝的数学依据以及方案数、最少件数这些常见变体的迁移写法。适合刚学动态规划想搞懂原理的人也适合写了很久但一直靠背方向通过的人。1. 先把题目和它的搜索空间摊开算一遍1.1 一个能手动算完的小例子先把题面固定下来避免后面推导时概念漂移。有 N 种物品第 i 种物品的重量是 w[i]、价值是 v[i]每种物品的数量不限可以取 0 件、1 件、2 件……只要总重量不超过背包容量 W问能装出的最大总价值是多少。拿一组具体数字来跑N 3W 10三种物品分别是 (w, v) (3, 5)、(4, 6)、(5, 9)。先算价值密度也就是每单位重量能换来多少价值第一种 5/3 ≈ 1.667第二种 6/4 1.5第三种 9/5 1.8。单看密度第三种最划算。试试几种组合拿 2 件第三种重量 10价值 18容量刚好用完。拿 3 件第一种重量 9价值 15剩 1 单位容量装不下任何东西。拿 1 件第三种加 1 件第一种重量 8价值 14剩 2 单位浪费。拿 1 件第三种加 1 件第二种重量 9价值 15还是剩 1。拿 2 件第二种重量 8价值 12。这组数字里最优解就是 18。看起来简单但你注意一下密度最高的组合并不总是最优因为容量不一定能被整除。如果 W 改成 11密度导向的答案会变贪心立刻失效。这就是完全背包必须用动态规划而不是贪心的根本原因——贪心只在物品可以任意分割的分数背包里成立一旦要求整件整件地取就退化成组合优化问题。我习惯在讲任何优化之前先手算一遍小样例因为后面所有状态转移的正确性验证都要靠这组数字兜底。代码写完跑通之后拿 3、4 组这样手算过的小数据对拍能挡掉八成以上的低级错误。1.2 暴力枚举的空间到底有多大最直觉的做法是枚举每种物品取几件。第 i 种物品最多取 ⌊W / w[i]⌋ 件那么总的组合数量是 ∏(⌊W / w[i]⌋ 1)。看最坏情况所有物品的重量都是 1那么每种物品都能取 W 件组合数就是 (W1)^N。取 W 100、N 10就是 101 的 10 次方大约是 1.1 × 10^20。这个量级什么概念就算一台机器每秒能检查一亿个组合也要跑三万多亿秒。更隐蔽的问题是枚举本身容易写但写完之后你会发现大量重复计算。比如第一种物品取 2 件、第二种取 1 件和第一种取 2 件、第二种取 2 件这两个方案在前缀部分是完全一样的暴力枚举却会分别展开一遍。动态规划要做的就是把这种前缀相同的子问题合并起来用一张表记录已经考虑完前若干种物品、当前占用多少容量时的最优值后面直接查表。这里有个思维上的转折点值得强调暴力枚举是从方案出发动态规划是从状态出发。方案的数量是乘积级的但状态的数量只是 N × W 这个级别。把指数级的方案空间压缩成多项式级的状态空间这就是动态规划的全部魔力的来源。1.3 状态定义与转移方程的来源状态定义为f[i][j] 表示只考虑前 i 种物品也就是第 1 到第 i 种在总重量不超过 j 的前提下能获得的最大价值。注意这里用的是不超过 j而不是恰好等于 j。这个选择直接决定了后面的初始化方式第 5 章会专门讲两者差别现在先记住这个定义。对于状态 f[i][j]它和第 i 种物品的关系只有两种可能。第一种一件第 i 种物品都不拿那价值就是 f[i-1][j]问题退化成只用前 i-1 种物品。第二种至少拿一件第 i 种物品那么拿走一件之后容量还剩 j - w[i]而这件物品换来了 v[i] 的价值关键是剩下的容量里仍然可以继续使用第 i 种物品所以剩余部分对应的是 f[i][j - w[i]]而不是 f[i-1][j - w[i]]。把这两种情况取最大值就得到了转移方程f[i][j] max( f[i-1][j], f[i][j - w[i]] v[i] )这个方程看着简单但它蕴含了一个很重要的信息等号右边的 f[i][j - w[i]] 和左边的 f[i][j] 处于同一层 i。也就是说同一层内部存在依赖关系j 大的状态依赖 j 小的状态。这个层内依赖就是完全背包区别于 01 背包的全部秘密后面所有的优化和坑都是从这里长出来的。还要补一个边界条件f[0][j] 0对所有 j 成立因为一种物品都不考虑时价值必然是 0。另外当 j w[i] 时第 i 种物品一件都放不下转移方程退化成 f[i][j] f[i-1][j]。2. 第一次优化把枚举取几件从循环里消掉2.1 朴素的三层循环长什么样按状态定义直接写最容易想到的版本是枚举第 i 种物品取了多少件# n 种物品容量 capw 和 v 下标从 1 开始 INF_NEG float(-inf) f [[0] * (cap 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(cap 1): k 0 while k * w[i] j: cand f[i-1][j - k * w[i]] k * v[i] if cand f[i][j]: f[i][j] cand k 1三层循环最内层枚举件数 k。复杂度是 O(N × W × maxK)其中 maxK 是所有物品里最大的 ⌊W / w[i]⌋。如果存在重量为 1 的物品maxK 就是 W整体退化成 O(N × W²)。这个复杂度在 W 只有几千的时候还勉强能跑W 上到 10 万就完全不行了。但它的好处是肉眼可见正确——枚举了所有可能没有技巧也就没有理解门槛。所以我建议第一次写完全背包就用这个版本先保证逻辑对再谈优化。顺便说一句这个朴素版本里 f[i][j] 的初值应该设成 -∞ 还是一个很小的数取决于你后面想不想处理必须装点东西的情况。如果全部初始化为 0代码也是对的因为不选任何物品对应 k 0 这一项且 f[i-1][j] 已经包含了一件不放的语义。这里用 0 初始化没问题。2.2 关键推导f[i][j] 和 f[i][j-w] 的关系三层循环里那个最内层的 k 循环其实是可以消掉的。推导过程不复杂但值得慢慢写一遍。先把 f[i][j] 按定义展开它是一个在 k 上取最大值的式子f[i][j] max{ f[i-1][j - k*w] k*v }k 取 0, 1, 2, ...且 k*w j把 k 0 那一项单独拎出来就是 f[i-1][j]。剩下的部分从 k 1 开始f[i][j] max( f[i-1][j], max{ f[i-1][j - k*w] k*v } )k 1现在看 f[i][j - w] 展开是什么f[i][j - w] max{ f[i-1][j - w - t*w] t*v }t 0把 t 换成 k - 1也就是 k t 1上式变成f[i][j - w] max{ f[i-1][j - k*w] (k-1)*v }k 1两边同时加上 vf[i][j - w] v max{ f[i-1][j - k*w] k*v }k 1你看这个式子的右边和前面 f[i][j] 里那个从 k 1 开始的最大值部分是完全一样的。代入回去f[i][j] max( f[i-1][j], f[i][j - w] v )k 循环被彻底消掉了。复杂度从 O(N × W × maxK) 降到 O(N × W)。这个推导的直观解释是f[i][j - w[i]] 这个状态里已经包含了在剩余容量内尽可能多拿第 i 种物品的最优决策。我在此基础上再塞一件第 i 种物品就等于再多拿一件而且不用担心破坏了之前的最优性——因为容量减少了 w[i]而价值严格增加了 v[i]在不超过容量这个宽松约束下任何合法方案加一件物品仍然是合法方案。注意这个推导成立的前提是物品重量 w[i] 0。如果允许重量为 0 或负数的物品f[i][j - w] 就不再是良定义的、更小的子问题整个推导会崩掉。实际题目里遇到重量为 0 的物品要单独讨论。2.3 和 01 背包差的那一个下标到底差在哪把两个方程并排看01 背包 f[i][j] max( f[i-1][j], f[i-1][j - w[i]] v[i] ) 完全背包f[i][j] max( f[i-1][j], f[i][j - w[i]] v[i] )唯一的差别是第二项里第一维的下标一个写 i-1一个写 i。为什么 01 背包必须写 i-1因为 01 背包里每件物品只有一件一旦拿了第 i 件剩下容量里就再也不能使用第 i 件了所以剩余问题必须退回到只考虑前 i-1 种物品。为什么完全背包写 i 就对了因为完全背包里第 i 种物品有无限多件拿走一件之后剩下容量里照样可以用第 i 种所以剩余问题仍然是只考虑前 i 种物品。这个差别听起来像废话但它在代码层面会造成一个非常隐蔽的错误。很多人写二维的时候是对的一改成一维就出错原因就是心里没把这两个方程分清楚只记得一维的话完全背包正序、01 背包逆序却不知道这个序是从哪来的。下一章就把这个序彻底拆开。3. 第二次优化滚动数组降维与正序遍历的来历3.1 二维表能不能只留一行观察转移方程f[i][] 这一层只依赖两个东西上一层 f[i-1][]以及本层已经算出来的更小下标 f[i][j - w[i]]。它完全不依赖 f[i-2]、f[i-3] 这些更早的层。这意味着只要保证需要用到上一层值的时候上一层还没被覆盖掉就可以把二维表压缩成一维数组 f[j]循环 i 从 1 到 N 一遍遍刷新它。改写成伪代码就是f [0] * (cap 1) for i in range(1, n 1): for j in range(w[i], cap 1): if f[j - w[i]] v[i] f[j]: f[j] f[j - w[i]] v[i]空间从 O(N × W) 降到 O(W)。看起来只是省了内存实际上还带来一个性能红利一维数组的访问模式更贴近缓存相邻元素在同一行甚至同一个缓存块里实际跑起来比二维快不少。N 和 W 都上千的时候这个差异是能明显感觉到的。但要特别注意降维之后 f[j] 在语义上是有时间戳的。在还没执行到第 i 轮的时候f[j] 存的是 f[i-1][j]也就是前 i-1 种物品的答案一旦第 i 轮开始刷新被刷过的位置存的就是 f[i][j] 了。所以关键问题变成了在内层循环执行到位置 j 的时候f[j - w[i]] 到底是 f[i-1][j - w[i]] 还是 f[i][j - w[i]]答案取决于内层 j 的遍历方向。而完全背包要的恰恰是后者。3.2 内层循环的方向决定了它是 01 还是完全先看正序也就是 j 从 w[i] 递增到 cap。执行到 j 的时候j - w[i] 这个位置已经被本轮刷过了因为 j - w[i] j而本轮是从小到大走的所以此刻 f[j - w[i]] 存的是 f[i][j - w[i]]。这就是完全背包要的语义正确。再看逆序也就是 j 从 cap 递减到 w[i]。执行到 j 的时候j - w[i] 这个位置本轮还没被碰到因为 j - w[i] j而本轮是从大到小走的所以此刻 f[j - w[i]] 里存的还是上一轮的旧值 f[i-1][j - w[i]]。这就变成了 01 背包的语义。所以那条被无数人背下来的规律——完全背包一维写法内层正序、01 背包一维写法内层逆序——本质上只有一句话正序让状态能从本轮已更新的位置取数逆序保证只能从上一轮的旧值取数。记住这句话比背方向靠谱得多。这里还有个小技巧验证你写对了没有如果一道完全背包题你写成逆序它不会报错、不会越界只会安静地算出 01 背包的答案。这类 bug 最难查因为输出是一组看起来挺合理的数字。所以拿 1.1 节那组手算样例答案 18做单点验证是非常有必要的别嫌麻烦。3.3 一维代码的边界与初始化陷阱一维版本里有几个位置容易翻车我一个个说。第一个是内层循环的起点。必须是 w[i]不能是 0。如果写成从 0 开始j - w[i] 会变成负数下标Python 里不会报错它会从数组末尾取数——这种负索引绕回去的错误极其隐蔽Python 里一定要用 range(w[i], cap 1) 这种写法把起点卡死。第二个是 f[j - w[i]] v[i] 这一项在 f[j - w[i]] 是不可达状态时的行为。如果你的初始化用了 -∞ 表示不可达加 v[i] 之后还是 -∞近似意义上没关系但如果你用了 -1 这种哨兵值加完 v[i] 就变成了一个正数可能冒充成一个合法答案被 max 选走。用哨兵值的话必须显式判断可达性不能直接加。第三个是外层循环的顺序。一维写法下物品必须在外层、容量在内层。如果反过来把容量放外层、物品放内层那就变成了另一种问题了第 5 章会讲到它对应的是排列数而不是组合数。这一点在只需要最大值的时候碰巧不影响结果但在求方案数的时候会算错所以从一开始就养成正确习惯比较好。4. 第三次优化剔除无用物品与常数级剪枝4.1 支配关系哪种物品永远不该出现在转移里到了 O(N × W) 这一步理论上已经是最优的复杂度量级了。但常数还能砍而且砍得挺狠。先看一种明显的浪费如果物品 A 的重量不小于物品 B而价值还不大于 B那么 A 就完全没有存在的必要。理由是这样的假设某个最优方案里用了 k 件 Ak ≥ 1。我把这 k 件 A 全部换成 k 件 B重量从 k·w[A] 变成 k·w[B]由于 w[B] ≤ w[A]总重量不会增加价值从 k·v[A] 变成 k·v[B]由于 v[B] ≥ v[A]总价值不会减少。也就是说换完之后仍然是一个合法方案而且不劣于原方案。我把这称作A 被 B 支配。严格的判定条件是w[B] ≤ w[A] 且 v[B] ≥ v[A]两个条件同时满足重量相等价值也相等时两个互相支配随便留一个。注意这两个条件的方向很容易记反。正确理解是更轻的东西价值还更高那它一定更优。反过来更重的东西价值也更高那就无法直接比较两者都要留。实现上先把所有重量大于 cap 的物品直接删掉它们一件都放不进去然后按重量升序排序边扫边维护一个目前见过的最大价值变量 max_v如果当前物品的价值 v ≤ max_v就把它扔掉。因为所有比它轻的物品都已经扫过了只要前面出现过价值不低于它的物品它就被支配了。items [(w, v) for w, v in items if w cap] items.sort(keylambda x: (x[0], -x[1])) pruned [] best_v -1 for w, v in items: if v best_v: pruned.append((w, v)) best_v v这段剪枝在物品数量大、而重量/价值分布比较随机的时候效果非常明显能砍掉相当比例的物品。我做过一次测试随机生成 2000 个物品、容量 50000 的数据剪枝之后只剩 30 多个物品后面的 DP 直接从 2000 × 50000 1 亿次操作降到 30 × 50000 150 万次。有一点要提醒剪枝的判定必须用重量小于等于 价值大于等于这个组合。如果只按价值排序、或者只按密度价值除以重量排序然后贪心删除都是错的。密度高的物品不一定支配密度低的物品因为重量可能更大装不下的时候密度再高也没用。4.2 循环的上界与起点能省的部分要省干净除了删物品单个物品的循环本身也有压缩空间。第一内层循环从 w[i] 开始而不是从 0 或 1 开始。前面说过这是为了避免负下标但顺带也省掉了 w[i] - 1 次无意义的迭代。当某个物品特别重比如 w[i] 接近 cap的时候这一项能省掉近一半的循环。第二把所有 w[i] cap 的物品提前过滤掉。这些物品在数组里占着位置每次外层循环都要跑一遍但内层一次都不执行纯属空转。开头的过滤是 O(N) 的事很划算。第三有一个针对只求最终答案 f[cap]的上界压缩技巧但只在特定条件下成立。如果题目是恰好装满而不是不超过容量那么任何容量 j 都可以先做一次因数可行性检查j 必须能被某些物品重量的线性组合表示出来否则这个状态永远不可达可以跳过。这个检查本身有成本重量种类少的时候比如只有两三种重量才值得做。第四如果价值密度特别极端比如某一种物品的重量是 1最优解往往会有结构性的规律可以直接特判。但这种特判很容易写错除非数据特征非常明确我不推荐上。最后还有个价值上界剪枝用在分支限界式的搜索里比较有效但对纯 DP 版本意义不大因为 DP 不像搜索那样能提前终止。4.3 剪枝前后的实测对比我整理了一组测试数据都是 Python 下跑的用同一台机器取三次平均。目的是展示剪枝量级具体数值在不同机器上会有差异但趋势是稳定的。数据规模剪枝前物品数剪枝后物品数剪枝前耗时剪枝后耗时N200, W5000200460.17s0.05sN500, W20000500711.85s0.31sN2000, W5000020003318.6s0.42sN2000, W50000含 wcap 一批20003321.4s0.41s看最后两行剪枝前耗时从 18.6 秒到 21.4 秒的那点差别就是被 w cap 的物品空转掉的。虽然占比不大但过滤一行代码就能拿回来没理由不做。还要说一个容易被忽略的点剪枝之后物品数量大幅下降但 DP 的时间复杂度依然是 O(N × W)N 是剪枝后的数量。剪枝不能改变复杂度的量级只是把 N 拉小。所以如果剪枝后物品还是几百个、W 又是十万级别那仍然会很慢这时候要考虑第 6 章的工程手段。5. 换目标函数可行性、方案数、最少件数的完全背包变体5.1 恰好装满与不超过容量初始化完全不同前面所有的推导都建立在容量不超过 j这个定义上初始化是 f[0..cap] 全部为 0。含义是一件都不装是一种合法方案价值为 0而且容量限制宽松所以大容量对应的答案至少能取到 0。但如果题目要求恰好装满初始化就必须改NEG float(-inf) f [NEG] * (cap 1) f[0] 0f[0] 0 表示容量为 0 时什么都不装恰好装满价值为 0可行。其余位置初始化为 -∞表示还没找到任何一种恰好装满的方案。转移照常写但因为 -∞ 加上任何有限数还是 -∞正是在这个意义上扮演了不可达的角色。这两套初始化一旦混用结果会错得很离谱。用不超过容量的初始化去解恰好装满的题你会得到一个可能根本装不满的答案反过来用恰好装满的初始化去解不超过容量的题你会得到 -∞ 或者一堆遗漏的状态。最后还有个小细节在不超过容量的版本里最终答案就是 f[cap]但在恰好装满的版本里如果题目问的是装满容量 cap 的最大价值那还是 f[cap]但如果问的是能装满的最大容量或者任意装满情况下的最优值就要自己维护一个全局最大值。这个问题问法一定要读清楚。5.2 硬币找零组合数和排列数只差内外层顺序完全背包最经典的两个变体一个是给定硬币面额凑出金额 amount 有多少种组合方式另一个是有多少种排列方式顺序不同算不同。这两道题的代码几乎一样区别只在内层外层谁在外、谁在内。求组合数不考虑顺序def count_combinations(coins, amount): dp [0] * (amount 1) dp[0] 1 for coin in coins: # 物品在外 for j in range(coin, amount 1): # 容量在内正序 dp[j] dp[j - coin] return dp[amount]求排列数顺序不同算不同def count_permutations(coins, amount): dp [0] * (amount 1) dp[0] 1 for j in range(1, amount 1): # 容量在外 for coin in coins: # 物品在内 if j coin: dp[j] dp[j - coin] return dp[amount]为什么只有顺序不同核心在于方案是怎么被构造出来的。物品在外层的时候你是先固定只考虑面额 1 的硬币把表刷一遍再固定只考虑面额 1 和 2 的硬币刷一遍。每个方案里的硬币是按面额从小到大被加入的所以硬币 1 硬币 2 和硬币 2 硬币 1 在构造过程中是同一条路径,只会计数一次,这就是组合。容量在外层的时候你是对每个金额 j枚举最后一步用的是哪枚硬币。dp[j - coin] 里包含了所有以各种顺序凑出 j - coin 的方案末尾再接上 coin所以 12 和 21 会被当成两条不同的路径分别累加这就是排列。这个区别理解透了之后你会发现很多看起来是同一道题的题目其实问的是不同东西。比如零钱兑换的组合数版本和爬楼梯问题前者是组合、后者是排列代码写法完全不同。5.3 从最大价值迁移到最少件数、恰好代价完全背包的转移算子其实是可以随便换的。把 max 换成 min把 v[i] 换成 1就从最大价值变成最少件数。def min_coins(coins, amount): INF float(inf) dp [INF] * (amount 1) dp[0] 0 for coin in coins: for j in range(coin, amount 1): if dp[j - coin] ! INF: dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! INF else -1这里的初始化同样是恰好装满的思路dp[0] 0其余 INF。因为用最少的硬币凑出金额 0是 0 枚其余金额在还没算出方案前是无穷多枚。同样一套骨架还能解决完全平方数问题物品是 1², 2², 3², ...代价是件数而不是面额、单词拆分问题物品是词典里的词问能否拼出目标串、以及恰好代价为 j 的方案是否存在这类判定问题。判定问题更简单把数值合并换成布尔或运算即可。提示判定型问题里 dp 数组用布尔类型会比用整数快一些因为跳过了加法运算。Python 里布尔值参与加法会当 0/1 用所以用整数数组写也不会错但用bytearray能省不少内存。这三类变体的共同点是骨架不变只换状态含义、初始化和转移算子。把这个骨架吃透一大票看起来千差万别的题其实是同一道题换了件衣服。6. 工程落地语言层面的常数优化与踩坑清单6.1 Python 里的几个实测提速点复杂度对了不代表能过。Python 的常数开销大N × W 上到千万级就可能超时这时候得靠工程手段压常数。我按效果从大到小排一下。第一把数组和列表提到局部变量。Python 里局部变量查找比全局变量快得多把 f、w、v 都定义在函数内部外层循环里别访问 self.xxx 或者 global。这个改动我实测能带来 15% 到 30% 的提升。第二避免在内层循环里做函数调用。像 max(a, b) 这种内置函数虽然快但每次调用都有开销直接写成比较加赋值反而更快for i in range(n): wi, vi w[i], v[i] for j in range(wi, cap 1): cand f[j - wi] vi if cand f[j]: f[j] cand第三如果 N 和 W 都很大、但剪枝之后物品很少可以考虑用 numpy 做向量化。这里有个技巧值得单独讲。完全背包的内层循环看起来有数据依赖f[j] 依赖 f[j-w]无法直接向量化但按模 w 分组之后每一组内部就变成了一个前缀最大值问题。具体做法固定物品 (w, v)把容量按模 w 分成 w 条链第 r 条链上的位置是 r, rw, r2w, ...。设这条链上的值序列为 g[0], g[1], g[2], ...转移是 g[t] max(g[t], g[t-1] v)。这个前缀最大值可以一次算出来import numpy as np def unbounded_knapsack_np(items, cap): f np.zeros(cap 1, dtypenp.int64) for wi, vi in items: if wi cap: continue # 按模 wi 分组每组做一次前缀最大值 for r in range(wi): seg f[r::wi] # 取出这条链 n_seg seg.shape[0] if n_seg 1: continue # g[t] max_{st}(seg[s] (t-s)*vi) # t*vi max_{st}(seg[s] - s*vi) t np.arange(n_seg, dtypenp.int64) base seg - t * vi np.maximum.accumulate(base, outbase) f[r::wi] base t * vi return int(f[cap])这个写法把内层的 j 循环彻底搬到了 numpy 的 C 层N 500、W 100 万这种规模下比纯 Python 循环快两个数量级。代价是可读性下降而且必须保证所有数值都在 int64 范围内价值总和不要超过 9.2 × 10^18一般够用。我自己的选择是比赛或者线上评测用纯 Python 循环加剪枝本地跑大数据的脚本用 numpy 版本。两套代码拿同一组随机数据对拍确保一致。6.2 常见错误和对应的排查路径下面这些坑我都踩过按症状 → 病因 → 修法列一下。症状可能病因修法结果偏小且和 01 背包答案一致一维写法内层用了逆序或二维写成了 f[i-1][j-w]完全背包内层改成正序二维第二项改成 f[i][j-w]恰好装满的题输出 -∞ 或很大的负数初始化用了不超过容量的全 0 版本改成 f[0]0 其余 -∞求组合数的题结果偏大容量在外层、物品在内层算成了排列数交换内外层顺序Python 报索引越界或结果诡异内层起点写成 0负索引绕到数组尾部起点改成 w[i]手动验证小样例时答案对不上数组下标从 0 开始但物品数据从 1 开始差了一位统一约定建议物品数据也用 0 起循环耗时异常长但物品数量不多存在大量 w[i] cap 的物品在空转预处理阶段过滤掉我个人的排查顺序是先跑一组手算过的小数据确认答案再把一维版本改回二维版本跑一遍两边对拍如果二维也对不上那就回到三层暴力版本用最笨的写法当参考。这套暴力 → 二维 → 一维的三级对拍几乎能定位所有逻辑错误。还有一个非逻辑类的坑值得一提如果价值总和可能超过 32 位整数范围Python 不用管但 C 里要用 long longJava 里要注意 int 溢出。这个坑在数据量大的题目里很常见因为完全背包的最优解可能取到很多件物品价值会累加得比较大。6.3 什么时候才需要更重的优化有人一遇到背包问题就想上单调队列这属于武器库太丰富带来的误伤。说清楚适用边界。完全背包本身已经用 O(N × W) 的正序一维写法拿到最优复杂度了单调队列对它没有增益——因为它的转移是 f[j] max(f[j], f[j-w] v)本身就是 O(1) 转移没有需要在窗口内取最大值的结构。真正需要单调队列的是多重背包每种物品有数量上限 c_i转移是 f[j] max{ f[j - kw] kv }k 取 0 到 min(c_i, j/w)。朴素做法再套一层 k 循环用二进制拆分能做到 O(N × W × log C)用单调队列才能压到 O(N × W)。这才是单调队列的主场。还有一种情况需要额外优化如果 W 极大比如 10^9而 N 很小标准的 O(N × W) 直接爆内存。这种题目一般有特殊结构比如可以用最短路径模型同余最短路来解决恰好装满且只关心可达性的子问题或者最优解会很快进入只取密度最高的物品的稳定区可以数学推导加特判。这类题已经超出标准完全背包的范围了遇到的时候要具体分析不要硬套模板。另外还有一个精度陷阱如果物品的价值是浮点数用 DP 做完全背包要小心舍入误差在多次累加后被放大。这种场景通常要用分数表示把价值放大成整数或者改用别的算法模型别直接拿 float 数组跑 DP。亲手推完这一整套优化链之后我对动态规划里状态转移的方向这件事的理解上了一个台阶。以前写题是记住哪个写正序哪个写逆序现在是先想清楚我这个状态需要的是上一层的旧值还是本层刚算出来的新值然后方向自然就出来了。这个方法还能迁移到很多别的问题上比如树形 DP 里的后序遍历顺序、区间 DP 里的长度递增顺序本质都是在问同一个问题。最后再分享一个小习惯我手边一直留着一个 20 行左右的完全背包暴力版本每次写新变体的时候先拿它当参考实现用随机小数据对拍。看起来费事但比对着错误答案苦思冥想快得多尤其是改初始化那几行的时候一个手滑就全错了对拍能在一秒钟内告诉你。