你是不是也遇到过这样的情况一看到「背包问题」四个字脑子里飘过各种 01、完全、多重、分组但真到上手做题的时候状态定义写得歪歪扭扭转移方程不是少了边界就是漏了初始化明明背过模板一调试就露馅。背包问题在算法面试、竞赛和日常刷题里都属于“高频常客”它的地位基本等同于排序算法在数据结构里的位置。但背包问题的难点从来不是代码本身而是“什么时候用哪个模板、为什么这么写”。这篇文章就把我这些年总结的背包问题算法模板一次说透从 01 背包最底层的一维滚动数组出发到完全背包的遍历顺序玄机再到多重背包的二进制拆分、分组背包的嵌套顺序最后配上方案数、恰好装满等高频变形。每套模板我都会把“为什么这么设计”讲清楚再给出可以直接抄的代码方便你建立一套属于自己的背包模板库。1. 背包问题的本质与模板化思路1.1 所有背包问题的共同骨架背包问题的本质说白了就是“有限资源下的最优选择问题”。你有一个容量有限的背包有一堆体积不同、价值不同的物品目标是在不超过背包容量的前提下最大化装入物品的总价值。这个模型能覆盖的场景远比字面意思广投入有限预算拿最大收益、有限时间内安排任务、服务器资源分配……都能套进这个框架。所有背包变体的核心状态定义都是一样的dp[i][j] 表示“处理完前 i 件物品背包容量为 j 时能获得的最大价值”。转移方程也几乎一样只有“当前这件物品能不能选、能选几次”的区别不选当前物品状态从 dp[i-1][j] 继承选择当前物品状态从 dp[i-1][j - w[i]] 转移过来加上价值 v[i]这就是背包问题的“原型模板”。后面的 01、完全、多重、分组全部只是在这个骨架上做细节修改。理解了这一点你就不再需要死记十几个看似不同、实则同源的循环写法了。1.2 常见变体的分类方式我习惯把背包问题按“物品的选择规则”分五类每一类是下一类的扩展01 背包是地基每件物品最多选一次完全背包是放宽限制每件物品无限次可选多重背包是中间状态每件物品有固定数量限制分组背包则是把物品分成若干组每组至多选一个混合背包就是以上几类的任意组合。还有二维费用、依赖关系、求方案数等其他维度本质都是在“选或不选”这个决策树上加约束。我把它们整理成一张速查表刷题的时候扫一眼就能定位背包类型遍历顺序核心转移典型场景01 背包物品外层循环容量倒序dp[j] max(dp[j], dp[j-w]v)每件商品最多买一次完全背包物品外层循环容量正序dp[j] max(dp[j], dp[j-w]v)无限量供应场景多重背包二进制拆分后按 01 处理拆分后同上库存有限、数量明确分组背包组外层循环容量倒序组内物品最内层dp[j] max(dp[j], dp[j-w]v)每组选一个的互斥选择二维费用两维容量按 01 或完全规则遍历dp[j][k] max(dp[j][k], dp[j-w][k-c]v)同时受两种资源限制1.3 为什么背模板不如理解模板我见过不少同学把模板代码抄在小本本上结果面试官把题目从“求最大价值”改成“求恰好装满的方案数”就不知道怎么调了。原因很简单模板背的只是“形”没理解“神”。模板的“神”是三件事状态定义是什么、遍历顺序为什么这么定、初始化传达了什么样的语义。只要把这三件事想明白任何背包题都可以现场推导出正确写法。所以下面的每一套模板我都会从这三个角度拆开讲而不是丢一段代码让你死记。2. 01 背包模板一切背包问题的地基2.1 二维朴素写法先把转移想明白老读者都知道我的习惯先写能保证正确的朴素版本再优化空间。01 背包的二维写法是理解一切后续模板的起点代码非常直白# w: 每件物品的体积v: 每件物品的价值W: 背包总容量 def knapsack_01_2d(w, v, W): n len(w) dp [[0] * (W 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, W 1): if j w[i - 1]: dp[i][j] dp[i - 1][j] else: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] v[i - 1]) return dp[n][W]这里 dp[i][j] 只跟 dp[i-1][...] 有关也就是“上一件物品处理完的状态”。这个“只用上一行”的特点非常关键它就是空间优化的入口。你不需要把 n 行的表格都存下来只需要保留上一行就可以滚动推导出当前行。很多初学者忽略了这个细节导致后面理解一维倒序遍历时一头雾水。2.2 一维滚动数组为什么容量必须倒序空间优化后只需要一个一维数组 dp[j]每次从后往前更新容量def knapsack_01_1d(w, v, W): dp [0] * (W 1) for i in range(n): for j in range(W, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[W]很多人背住了“容量倒序”但不知道为什么要倒序。我用一个生活化的例子解释假设你只有一个背包容量 10只有一件体积 5、价值 100 的物品。如果容量正序遍历dp[5] 先被更新成 100等你遍历到 dp[10] 的时候发现 dp[10 - 5] dp[5] 已经是 100于是 dp[10] 被更新成 200但这件物品被用了两次。倒序遍历时dp[10] 更新时读到的 dp[5] 还是更新前的旧值这就保证了每件物品最多被选一次。这个“读旧值”还是“读新值”的差异就是 01 背包和完全背包的全部区别所在。记住这一点比背十遍代码都管用。2.3 初始化细节不超过容量与恰好装满这是背包问题里最常踩的坑也是面试官最爱挖的细节。上面代码里的 dp 数组全部初始化为 0表示“容量不超过 j 时能装的最大价值”这时 dp 数组天然允许装不满背包。但如果题目要求“恰好装满背包”初始化就要改dp [-inf] * (W 1) dp[0] 0把非 0 位置初始化为负无穷是为了让“从非法状态转移过来”的结果依然是非法值。只有 dp[0] 是合法的起点意思是“恰好占满容量 0”是可行的价值为 0。这样最终 dp[W] 如果还是负无穷就说明“恰好装满”根本做不到如果是个正常值那它就是正确答案。我习惯把初始化理解为“状态的合法起点”。起点设得不对后面推导出的答案就全部失去意义。3. 完全背包模板正序遍历背后的数学直觉3.1 模板代码就改一个遍历方向完全背包的特点是每件物品可以无限使用。你可能会以为需要加一层循环来枚举“选几件”但其实不用完全背包的核心模板只比 01 背包改了一个地方容量遍历改成正序。def knapsack_complete(w, v, W): n len(w) dp [0] * (W 1) for i in range(n): for j in range(w[i], W 1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[W]为什么正序就支持无限取用回到我前面说的“读新值”逻辑。正序遍历时dp[j] 用到 dp[j - w[i]]而这个 dp[j - w[i]] 可能已经在当前这轮物品中被更新过了也就是已经考虑过“再选一次当前物品”的情况。于是同一件物品可以连续选择多次直到把容量撑爆为止。3.2 完全背包的排列与组合计数完全背包还有一个高频变形不需求最大价值而是求“凑成某个金额总共有多少种方案”。这时候细分出两个模板一个是组合数不区分顺序比如 23 和 32 算同一种一个是排列数区分顺序。它们的写法区别会直接导致结果不同务必要分清。组合数的标准写法是外层枚举物品内层枚举容量def combination_sum4_combo(nums, target): dp [0] * (target 1) dp[0] 1 for num in nums: for j in range(num, target 1): dp[j] dp[j - num] return dp[target]440 排列数的标准写法是外层枚举容量内层枚举物品def combination_sum4_permutation(nums, target): dp [0] * (target 1) dp[0] 1 for j in range(1, target 1): for num in nums: if j num: dp[j] dp[j - num] return dp[target]组合数模板对应 LeetCode 518零钱兑换 II排列数模板对应 LeetCode 377组合总和 Ⅳ。这两道题我每次讲的时候都会特意强调先想清楚题目要求“顺序相不相同算不算一种方案”再决定内外层循环的摆放顺序。交换这两个循环答案会完全不同。3.3 完全背包求最大价值的经验如果你做的是“无限取物品求最大价值”的题目比如 LeetCode 322零钱兑换记得用下面的模板def coin_change(coins, amount): dp [inf] * (amount 1) dp[0] 0 for coin in coins: for j in range(coin, amount 1): dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! inf else -1这里如果把 min 换回 max把初始化改成 -inf就变成“求最多能用多少硬币”同样是一道高频笔试题。我建议你在本地把这段代码的 min 和 max 来回切换着跑一遍对比一下结果很快就能理解“完全背包模板其实只是一个壳具体求什么取决于你想让 dp 数组存什么”。4. 多重背包模板二进制拆分的思路4.1 朴素版三重循环直接枚举件数多重背包比完全背包多一个限制每件物品有明确的库存数量 cnt[i]。最朴素的写法当然是在 01 背包基础上加一层循环枚举这件物品选 0、1、2、…、cnt[i] 件def knapsack_multi_naive(w, v, cnt, W): n len(w) dp [0] * (W 1) for i in range(n): for j in range(W, w[i] - 1, -1): for k in range(1, cnt[i] 1): if j k * w[i]: dp[j] max(dp[j], dp[j - k * w[i]] k * v[i]) return dp[W]这个写法正确但复杂度太高。如果物品数 n 是 100容量 W 是 1000每件物品库存 100循环次数轻松上千万。笔试里能过但竞赛里大概率超时。所以需要引入二进制拆分。4.2 二进制拆分模板把多重背包磨成 01 背包二进制拆分的核心思想是任何数量 cnt[i]都可以拆成若干个 2 的幂之和比如 13 拆成 1、2、4、6注意不是 1、2、4、8因为拆到 8 加起来超过 13 了所以最后一项是 13-1-2-46。这几组数可以组合出 0 到 13 之间的任意数量不信你可以自己验算。于是问题就变成了把 cnt[i] 件同种物品按二进制拆成几“堆”每一堆看成一个新物品它的体积是 kw[i]价值是 kv[i]这堆只能整体选或不选再用 01 背包跑一遍就行。模板如下def knapsack_multi_binary(w, v, cnt, W): new_w, new_v [], [] for i in range(len(w)): k 1 while cnt[i] 0: take min(k, cnt[i]) new_w.append(take * w[i]) new_v.append(take * v[i]) cnt[i] - take k 1 dp [0] * (W 1) for i in range(len(new_w)): for j in range(W, new_w[i] - 1, -1): dp[j] max(dp[j], dp[j - new_w[i]] new_v[i]) return dp[W]这段代码里最关键的是 take min(k, cnt[i]) 这步。有人会问为什么不按 1、2、4、8 一直拆到 13 拆出 1、2、4、8 四个数因为 1、2、4、8 组合出的最大数是 15超过了 13这会让模板错误地允许拿 14 件或 15 件而你实际上库存只有 13。用 min 控制最后一项保证新物品组合的上限刚好等于库存数。4.3 什么时候需要上单调队列优化二进制拆分后的复杂度大约是 O(W * 总log(cnt))绝大多数场景足够用。但如果物品数量级特别大比如背包容量 10000、每件库存 10000二进制拆分后仍然可能超时就需要借助单调队列把多重背包优化到 O(W * n)。这个模板写起来比较绕思路是把容量 j 按模 w[i] 的余数分组处理每组内用单调队列维护滑动窗口内的最大 dp 值。不过以我刷题的经验面试和大多数笔试根本不会逼你用单调队列。二进制拆分模板已经能覆盖 95% 的题目建议先把拆分逻辑练熟再去研究单调队列不要一上来就啃硬骨头。5. 分组背包与更进阶的模板变形5.1 分组背包三重循环嵌套顺序千万不要错分组背包是这么一类问题物品被分成若干组每组内最多只能选一件。经典题目是 LeetCode 1155掷骰子的方法和竞赛里的“分组选课”问题。模板结构是三层循环先遍历组再遍历容量最后遍历组内物品。def knapsack_group(groups, W): # groups: 每组是一个列表每个元素是 (体积, 价值) dp [0] * (W 1) for group in groups: for j in range(W, -1, -1): for weight, value in group: if j weight: dp[j] max(dp[j], dp[j - weight] value) return dp[W]这里的嵌套顺序很有讲究容量循环放在组内物品循环之前并且容量要倒序。目的跟 01 背包一样保证同一组的物品最多只有一个被选中。如果顺序调换就会出现同一组内多个物品叠加的情况答案就错了。我见过太多人把这一层的顺序写反排查半天才发现是循环位置放错了。5.2 有依赖的背包树形 DP 与分组合并进阶一点的背包题长这样物品之间存在依赖关系比如“想选电脑必须先选电源”类似依赖树。LeetCode 没有特别典型的模板题但竞赛里的“金明的预算方案”就是经典代表。处理依赖背包的常规套路是先用 DFS 遍历树结构把每个子树看成一个分组然后在父节点做分组背包合并。核心模板可以这样理解每棵子树返回一个“不同容量下的最优价值表”上一层的节点就把这些表挨个合并进自己的 dp 数组。我坦白讲这个模板比较吃递归功底而且状态转移里“选主件”和“不选主件”两条分支经常把人绕晕。我的建议是先用 01 背包把主件的取舍处理清楚再把附件按分组背包的方式合并到主件状态上拆成两个问题逐个击破比直接背整棵树的转移方程容易得多。5.3 模板速查从 01 到混合背包的完整对比背包类型循环层数容量遍历方向核心技巧备注01 背包2 层倒序每件物品选一次一切背包的基石完全背包2 层正序每件物品无限选求方案数时注意内外层顺序多重背包2 层拆分后倒序二进制拆分成 01注意最后一项用 min 控制上限分组背包3 层倒序组内物品最内层容量循环必须在组内物品循环外混合背包按类型分段分情况先拆多重再按 01/完全处理按物品类型分别套模板二维费用3 层倒序多一维容量数组类似两维的 01 背包这张表是我自己的“作弊小抄”每次刷题前扫一遍基本能快速定位该用哪套模板。6. 模板背不住也不慌调试与实战经验6.1 状态转移写不下去时先回到二维定义写不出转移方程的时候我的习惯是先别想优化老实把二维 dp[i][j] 的表格画出来。比如容量从 0 到 6物品就三件手动填一遍表观察当前格子的值是从哪个格子来的。这个过程不丢人反而能最快帮你建立“决策就是选或不选”的直觉。状态转移写不下去多半不是循环写错而是状态定义本身还是模糊的。这里给一个自查清单是我教学生时常用的状态 dp 数组存的到底是最优值、方案数还是可行性布尔值容量维度是“不超过”还是“恰好等于”每件物品是可重复选、最多选一次还是有固定库存内外层循环的顺序是不是符合当前背包类型的语义这四个问题想清楚模板基本不会写翻车。6.2 常见问题与调试技巧实录我在实际刷题和工程里碰到的坑主要集中在下面几个地方第一个是初始化错误。恰好装满类型的题目非 0 位置不置负无穷结果答案算出来永远比真实值小因为非法状态被当成 0 参与了转移。这个坑隐蔽性很高特别是数据恰好全为正数时你甚至会得到一个看起来“合理”的错误答案。第二个是遍历顺序错位。01 背包用了正序完全背包用了倒序两者结果都错得离谱。如果你确认状态转移没问题先怀疑是不是把这两个顺序写反了。我的经验是给每个模板起一个小注释比如“01-倒序”“complete-正序”抄代码的时候瞄一眼就能避雷。第三个是容量边界。内层循环的范围写成了 range(W, 0, -1) 而不是 range(W, w[i]-1, -1)导致 j 根本装不下当前物品时仍然访问 dp[j-w[i]]。虽然 Python 负索引不会直接报错但拿到的状态数据完全是乱的。刷 C 的话更是容易越界。边界最好统一写成for j in range(W, w[i] - 1, -1)一步到位。6.3 手写模板的两个独家技巧再分享两个我自己的习惯。第一个是“造最小用例”调试法。任何背包模板写完先拿容量 3、两件物品体积 1 价值 2体积 2 价值 3这种最小数据手推一遍在代码里跑出预期结果再提交。这个习惯帮我省了无数 debug 时间。第二个是对拍。写一个绝对正确但复杂度高的朴素版本再写一个优化版本用随机小数据反复对比输出。两边结果一致再提交上去基本不会出错。这个方法不仅适合背包几乎适用于所有动态规划类题目强烈建议养成习惯。7. 最后再说几句实在话模板这个东西背得住是本事用得对才是真功夫。我至今面试候选人的时候不会问“你会不会背背包模板”而是丢一道稍微拐弯的类似题看你能不能自己推导出遍历顺序。能推出来的说明对状态定义有真理解背出来的碰到变形就露馅。个人的建议是把 01 背包的二维转一维过程亲手推导三遍以上直到你能不假思索地说出“倒序是为了防止重复选”为止。其他的完全、多重、分组模板全部从 01 背包这个根源出发去理解差异你会发现它们根本不需要死记都是同一棵树上的几个分支而已。最后再分享一个我自己的小技巧真正上考场或面试前不要临时翻模板而是在纸上把每个模板的核心循环手写一遍。手写得出来说明这套模板已经是你的东西了。写不出来的地方才是你接下来要补的短板。