尧图网站建设 
1. 先从选与不选开始为什么暴力枚举走不通我在面试候选人和带新人的时候发现一个很有意思的现象很多人谈起动态规划就头皮发麻觉得这是一道跨不过去的坎。但如果你把“01背包问题”这五个字拆开其实它描述的场景特别朴素——你面前有 N 件物品每件有自己的重量 w[i] 和价值 v[i]你手里有一个容量为 W 的背包每件物品只能选择装或者不装这就是“01”的由来0 代表不装1 代表装目标是让背包里装下的总价值最大。就这么个问题看上去毫无技术含量。但为什么它能成为算法领域的“钉子户”反复出现在笔试、面试、竞赛和各种教程里因为它的解法背后藏着动态规划最核心的思想把一个大问题拆成互相重叠的子问题用空间换时间。先说说为什么暴力枚举走不通。最直观的想法是一共有 N 件物品每件物品有“选”和“不选”两种状态那么所有组合方案就是 2^N 种。你需要遍历这些方案然后去重、筛选出重量不超过 W 的再找最大价值。听着好像可行但 N20 的时候是 104 万种N30 就是 10 亿种N50 直接奔着千万亿去了。就算你的计算机每秒能跑一亿次N50 也要跑到宇宙热寂。所以暴力法只适合 N≤20 左右的场景稍微上点规模就直接死给你看。那怎么优化关键就在“重复”这两个字上。你可以想一想当我依次决定要不要装第 i 件物品时前面已经决策完的物品会形成一个状态——当前的剩余容量和累计价值。不同的决策路径可能会在某个时刻落入完全相同的状态同样还剩 10kg 容量同样已经装了价值 500 的东西。既然状态相同后面还能装的物品也一样那么从这两个状态继续走最优结果必然也相同。于是我们只需要为每一个“剩余容量 已决策物品数”组合保留一个最优价值就够了根本不需要枚举完整路径。这就是 01 背包问题最底层的直觉用“决策到第几件物品 当前背包容量的剩余量”来定义状态把指数级的可能性压缩成 N×(W1) 个格子。压缩的背后不是魔法是因为我们砍掉了一模一样的大量冗余分支。想通了这一点后面所有状态转移方程、滚动数组、空间优化都是水到渠成的事。2. 一张表推到底手把手构建二维DP状态2.1 状态定义和转移方程的直觉来源我们先约定符号。假设有 N 件物品物品编号从 1 到 N第 i 件物品的重量是 w[i]价值是 v[i]。背包容量为 W。令 dp[i][j] 表示“只从前 i 件物品里挑放入容量为 j 的背包能获得的最大价值”。这里有几个细节需要解释清楚因为很多初学者第一次看到 dp[i][j] 都会困惑为什么第二维是背包容量 j而不是剩余容量其实两者本质等价但“容量为 j”的表达更利于递推。你再想深一层dp[i][j] 对应的那个书包里面装的物品全部来自前 i 件且它们的总重量不超过 j。接下来是状态转移。站在第 i 件物品面前只有两个选择不装第 i 件物品那么前 i 件物品能获得的最大价值就等于前 i-1 件物品在同样容量 j 下的最优值即 dp[i][j] dp[i-1][j]。意思就是“这件东西我不要了继承之前的最好结果”。装第 i 件物品前提是当前背包容量 j 装得下 w[i]也就是 j ≥ w[i]。如果装那么前 i-1 件物品只能使用剩余容量 j - w[i]然后再加上第 i 件物品的价值 v[i]即 dp[i][j] dp[i-1][j - w[i]] v[i]。因为我们要的是最大价值所以在这两个选项里取 max。于是就有了经典的转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) (当 j w[i]) dp[i][j] dp[i-1][j] (当 j w[i])为什么“继承之前的最好结果”是合法的因为前 i-1 件物品的所有选择组合已经被压缩在 dp[i-1][*] 这一整行里了。你不需要关心这些组合具体长什么样只需要知道它们在各个容量下的最大价值。这就是动态规划“最优子结构”的体现全局最优解一定包含子问题的最优解。更直白地说你可以从后往前倒推既然最终方案里第 N 件物品要么装、要么不装那么去掉第 N 件物品后的剩下的部分也一定是在前 N-1 件物品和对应剩余容量下的最优方案。如果不是最优你就可以把那一部分替换成更优的整个方案的价值还能更大这不就矛盾了嘛。2.2 亲手推一张完整的 DP 表理论讲半天不如亲手算一张表。我们直接看一个具体例子。假设背包容量 W10有 4 件物品物品编号重量 w[i]价值 v[i]123234345458初始化 dp[0][j] 0因为一件物品都不选价值肯定是 0。先处理 i1物品1重量2价值3。容量 j 从 0 到 1 时装不下所以 dp[1][0]0dp[1][1]0。从 j2 开始能装下了dp[1][j]3因为只有这一件物品装了价值就是3不装是0取最大值为3。所以这一行变成j012345678910dp[1][j]00333333333再看 i2物品2重量3价值4。j0、1、2 时装不下物品2只能继承 dp[1][j] 的值分别是 0、0、3。j3 时两种选择不装dp[1][3]3装dp[1][0]44。取最大值 4。j4 时不装是 3装是 dp[1][1]44所以 dp[2][4]4。j5 时不装是3装是 dp[1][2]47取7。后面继续算就能得到整行j012345678910dp[2][j]00344777777按同样的方式往下推dp[3][j] 和 dp[4][j] 我就不逐个列了。重点是看最后 dp[4][10] 的计算过程不装物品4价值是 dp[3][10]装物品4前提是容量至少 5那么价值是 dp[3][5]8。最终结果就是这两个数中的较大者。整个表的右下角那个格子就是整个问题的最优解。我建议你第一次学的时候一定找张纸把每一行每一列都手动填一遍。填完之后你会发现自己突然理解了“状态”到底是什么东西——它不是一个虚无缥缈的名词就是一个表格里的格子每一格都代表一个已经算清楚了的小规模子问题。2.3 时间复杂度与空间复杂度上面这种二维数组解法需要两层循环外层遍历物品 i内层遍历容量 j。每次循环只做常数次操作所以时间复杂度是 O(N×W)。空间上开了一个 (N1)×(W1) 的二维数组所以空间复杂度也是 O(N×W)。有人可能会问如果 W 特别大比如 W10^9这个算法是不是就废了是的这就是 01 背包问题的软肋——它的复杂度跟背包容量 W 线性相关W 一大就会超时超内存。所以当 W 很大、但 N 比较小的时候有人会换一种“按价值 DP”的思路也就是把价值当作第二维状态来设计算法。后文我会展开说。3. 一维数组优化为什么必须倒着遍历3.1 从二维滚动到一维的推导过程二维 DP 表虽然清晰但有个问题真的需要保存所有行的数据吗看看状态转移方程 dp[i][j] 用到的是哪几项——dp[i-1][j] 和 dp[i-1][j-w[i]]。这两项都在“上一行”里。也就是说当前 i 行的计算只依赖前一行 i-1再往前的 i-2、i-3 行根本不会再被用到。既然如此我们完全可以把二维表压缩成一维数组 dp[j]代表“当前处理到某一件物品时容量为 j 的背包能装下的最大价值”。每次处理新物品时用这个一维数组就地更新。这个技巧通常被叫做“滚动数组”或“就地更新”。一维更新的代码看起来极其简单for i in range(1, N 1): # 遍历每一件物品 for j in range(W, w[i] - 1, -1): # 容量从大到小遍历 dp[j] max(dp[j], dp[j - w[i]] v[i])但这里有一个极其关键、几乎所有新手都会踩的坑——内层循环为什么要从 W 逆序递减到 w[i]而不是顺序从小到大3.2 顺序遍历会出什么问题一个反例为了说清楚这个问题我们先跑一遍顺序遍历的错误代码for i in range(1, N 1): for j in range(w[i], W 1): # 错误示范从小到大 dp[j] max(dp[j], dp[j - w[i]] v[i])还是用上面的例子只看第一件物品w2v3处理时dp 数组初始全为 0。假设 W10。j2dp[2] max(0, dp[0]3) 3j3dp[3] max(0, dp[1]3) 3j4dp[4] max(0, dp[2]3) max(0, 33) 6出事了j4 的时候dp[2] 已经在当前这一轮循环里被更新成了 3这意味着我们在计算 dp[4] 的时候把“已经装入第一件物品”后的状态再装了一次第一件物品。换句话说同样的物品 1 被选了两次。可 01 背包里每件物品最多只能选一次这显然是错的。而逆序遍历为什么能避免这个问题因为 j 从大到小更新的时候计算 dp[j] 需要的是 dp[j-w[i]]而这个较小的下标 j-w[i] 一定小于 j且还没有被当前这一轮更新过。因此 dp[j-w[i]] 仍然是上一轮也就是还没处理当前物品的旧值这正好对应了“第 i 件物品只装一次”的语义。我见过有些教程只是扔给你一句“要倒序”然后让读者死记硬背。其实这个倒序的推导过程特别简单但一旦理解了你不仅知道怎么用还能在面试时讲清楚每一步的原因。更重要的是一旦 DP 题的变体里要求每个物品可以选无限次完全背包问题内层循环就要反过来变成正序遍历。如果你不理解倒序的底层逻辑面对完全背包时很容易再次迷茫。3.3 一维数组的初始化语义一维数组 dp[j] 的初始值全部设为 0这个做法对应的是“背包不一定要装满”的语义任何容量下我什么都不装价值都是 0这个方案总是合法的。后面我会再说如果题目改成“恰好装满背包”初始化方式就会大不相同。3.4 空间优化后的完整代码def knapsack_01(N, W, weights, values): dp [0] * (W 1) for i in range(N): # 逆序遍历容量 for j in range(W, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[W]这个版本的时间复杂度仍是 O(N×W)但空间复杂度降到了 O(W)这是面试和笔试里最常用的版本。我自己的习惯是先写二维版本理清思路再用一维版本提交代码避免一上来就写错逻辑。4. 从最优值到最优方案回溯出具体选了哪些物品很多教程讲完求最大价值就收工了但实际业务里你往往不只关心“最多能装多少价值”还想知道“到底该选哪几件物品”。比如公司要做一个预算有限的投资组合你不仅需要知道最大收益还得知道具体投哪几个项目。当使用二维 DP 数组时回溯方案非常简单。我们从最后一个格子 dp[N][W] 开始倒推如果 dp[i][j] dp[i-1][j]说明第 i 件物品没有被选中那么问题收缩到 dp[i-1][j]即“前 i-1 件物品、容量 j”的最优方案。如果 dp[i][j] dp[i-1][j-w[i]] v[i]同时满足 j ≥ w[i]说明第 i 件物品被选中了于是把 i 记录下来然后问题收缩到 dp[i-1][j-w[i]]。如果两个条件同时成立dp[i-1][j] 恰好等于 dp[i-1][j-w[i]] v[i]说明“选不选这件物品”都能达到同样的最大值。这时可以根据需要任选一种路径比如优先选或者优先不选一般来说优先记录“选”的那条路径即可。这里有个细节容易让人犯迷糊如果我用的是空间优化后的一维数组dp[j] 里存的只是最终结果中间过程被反复覆盖了还能回溯吗答案是基本不行除非额外记录选择矩阵。所以在需要输出具体方案时我建议老老实实用二维数组别为了省空间丢掉回溯能力。这是典型的“空间换功能”的取舍实际面试时也是加分项。下面是个回溯的示意代码def knapsack_with_solution(N, W, weights, values): 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 weights[i - 1]: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] values[i - 1]) else: dp[i][j] dp[i - 1][j] # 回溯选中的物品 selected [] j W for i in range(N, 0, -1): if j weights[i - 1] and dp[i][j] dp[i - 1][j - weights[i - 1]] values[i - 1]: selected.append(i) j - weights[i - 1] selected.reverse() return dp[N][W], selected回溯的复杂度是 O(N)只扫描一遍物品就够了。这里要注意当你发现 dp[i][j] 同时等于不装和装的两种情况时必须按照你自己的业务规则选择一条路径否则你得到的“方案”不一定唯一。比如有些场景希望装更少的物品因为每多一件都要增加管理成本那就在相等时优先“不选”。5. 初始化定义决定题目走向恰好装满与常见变体5.1 “最多能装”和“恰好装满”的初始化玄机关于 01 背包最常被忽略的一个细节就是初始化条件。前面我们一直把 dp 数组全部初始化为 0这是因为题目问的是“在容量 W 内最多能装多少价值”不要求背包装满所有容量的“零价值空包”都是合法的基准状态。但如果题目改成“背包必须恰好装满求能装下的最大价值装不满返回无解或某个特殊值”初始化就要大变。二维版本dp[0][0] 0dp[0][j] 当 j 0 时设为负无穷比如 -inf表示“用 0 件物品根本无法凑出恰好容量 j 的状态”这是非法状态。一维版本dp[0] 0dp[1..W] -inf。这样在状态转移时任何“由非法状态转移而来”的结果都会因为加上 -inf 而仍然保持非法意义不会被错误地当成合法答案。为什么要用负无穷而不是 0举个例子如果初始化全是 0那么容量 j5 时你可能会得到“什么都不装也是合法方案价值是 0”的结论。这在“恰好装满”语义下就错了——容量 5 的背包空空如也哪来的恰好装满所以必须让这些状态从一开始就“烂掉”后续怎么转移都不会被误用。我早年刷题时在这里翻过车。题目要求恰好装满我图省事直接用全 0 初始化结果样例过了、提交全错。排查了半天才意识到不是转移方程的问题是初始状态把非法状态和合法状态混为一谈了。5.2 求方案总数的变体除了求最大价值01 背包家族里还有一个常见变体求“恰好装满背包的方案数”。转移方程变成了dp[j] dp[j] dp[j - w[i]]初始化时 dp[0] 1其余为 0。含义是凑出容量 0 的方案数为 1什么都不选其他容量初始方案数为 0。遍历物品时每件物品选择“取”或“不取”方案数自然就是两者相加。这个变体在 LeetCode 的“目标和”“组合总和 IV”等题目中都有体现核心思想完全一致。5.3 求最小价值的变体有时候题目把“价值”换成“代价”让你求“装满背包的最小代价”。这也很简单把所有 dp[j] 初始化为正无穷dp[0]0转移方程把 max 改成 min 即可。思路和“恰好装满”一模一样区别只是把取最大变成取最小。5.4 二维费用背包再加一个限制维度如果每件物品除了重量之外还有体积或者说背包有两个限制条件那就需要三维 DPdp[i][j][k] 表示前 i 件物品在重量为 j、体积为 k 的限制下能取得的最大价值。转移时会同时考虑重量和体积两个维度。这个变体的思路没有本质变化只是多了一维循环空间和时间复杂度都随之增加。我在项目里遇到过类似场景给服务器分配任务时既怕 CPU 超核又怕内存超限每个任务对两个资源都有需求二维费用背包正好派上用场。6. 实战经验与常见误区盘点6.1 大 W 场景下的“价值反打”技巧前面提到当背包容量 W 特别大时O(N×W) 的复杂度会爆掉。这时有个常见的应对思路如果单件物品的价值 v[i] 比较小且总价值 V 在可接受范围内那就把“价值”当作状态维度dp[v] 表示“凑出价值 v 所需的最小重量”。最后从小到大遍历价值找到第一个 dp[v] ≤ W 的值作为答案。这个算法的时间复杂度是 O(N×V)。我在开源项目代码里见过这种做法专门用来处理 W 高达几千万但单件价值只有几百的题目。6.2 物品重量为 0 或负数时的雷区重量为 0 的物品往往被题目悄悄塞进来当陷阱。如果物品重量是 0逆序遍历和正序遍历就变得没有区别了因为 j-w[i] j无论顺序如何dp[j] 都能被自己更新。处理这类物品时要格外注意是否需要“无限次使用”的语义。至于重量为负的物品那就更麻烦了因为不能再按普通 01 背包处理通常需要特殊平移或重新建模这个超出了本文范围但如果你遇到了别慌先想想能不能把负重量问题转换成“偏移量”问题。6.3 典型误区汇总我在带人刷题时整理了这张高频误区对照表几乎每个人都至少中过一条误区错误表现正确做法内层循环顺序一维优化时正序遍历容量必须逆序防止同一物品被重复选择初始化混乱恰好装满问题用了全 0 初始化dp[0]0其余设正/负无穷回溯方案时用一维数组想让一维 DP 输出选中的物品使用二维 DP 记录完整路径忘记考虑装不下的情况转移时直接计算 dp[i-1][j-w[i]] v[i]但 j w[i] 时越界先判断 j w[i]或循环从 w[i] 开始把状态维度写反dp[i][j] 中 i 代表容量j 代表物品数约定清晰保持一致写代码前先写注释这里再补充一个我自己常犯的失误二维 DP 初始化时我偶尔会把 dp[0][j] 和 dp[i][0] 的边界弄混。dp[0][j] 表示“0 件物品在各种容量下的最大价值”一定是 0dp[i][0] 表示“容量 0 时选前 i 件物品的最大价值”也一定是 0什么都装不下。两者都是合法边界任何一边漏了都会导致后续转移出错。6.4 工程实践里如何选择 DP 数组类型如果你在做算法题int 数组通常够用。但如果题目里的价值和容量数量级都在 10^9 附近加法和比较很容易溢出这时要把 dp 数组声明为 longPython 就没有这个烦恼。另外不可达状态的初始化值要选准求最大值时用负无穷如 -10^18求最小值时用正无穷如 10^18避免在计算 max/min 时被实际可达的边界值干扰。我自己平时写代码有个习惯先写二维版本跑通小样例再改写成一维优化版本。这不是浪费时间而是用二维版本当“参考答案”一旦一维版本出 bug可以快速对照阶段结果定位问题。很多人一上来就想写最精简的代码结果 debug 的时间比写代码还长反而得不偿失。7. 举一反三从 01 背包到完全背包和多重背包搞懂了 01 背包的倒序遍历再去看完全背包每件物品可以选无限次就会豁然开朗for i in range(N): for j in range(weights[i], W 1): # 正序遍历容量 dp[j] max(dp[j], dp[j - weights[i]] values[i])唯一的变化就是把内层循环从逆序改成正序。为什么因为正序意味着在计算 dp[j] 时dp[j-w[i]] 可能已经在当前这轮循环中被更新过等价于“还可以继续选择当前物品”正好符合完全背包“无限取用”的语义。你看理解倒序原理的好处在这里体现得淋漓尽致不需要死记两个版本只要想清楚“一维数组里的旧值代表什么”一切都能推导出来。多重背包则更复杂一些它限制每件物品最多取 c[i] 次。常规做法是把它拆成 01 背包把第 i 件物品拆成多件独立的“01 物品”每件的重量和价值是原物品乘以系数 1、2、4、……二进制拆分这样就能把 c[i] 次选择组合成任意 0 到 c[i] 次。这个技巧本质上还是 01 背包的变形所以你会发现把基础打牢了后面这些变体学起来都是顺水推舟。实际业务里安排服务器资源、预算分配、排产计划、商品打包推荐……这些场景往往都能抽象成某种背包问题。我接过一个需求在广告预算有限的情况下从几十个投放渠道里挑出组合让预估曝光最大化。这不就是标准的 01 背包吗每个渠道是物品预算限额是背包容量预估曝光是价值。虽然数据规模不大但用背包写出来的程序只有几十行比业务同事用 Excel 手动试方案不知道高到哪里去了。关于 01 背包我最后分享一个心得别背代码去背“为什么”。为什么二维能压一维为什么一维要倒序为什么恰好装满要初始化成无穷这三个“为什么”吃透了你就是把 01 背包从“会做题”提升到了“理解它”的层次。做到了这一步不管题目怎么改、数据范围怎么调、是面试手写还是业务落地你都能第一时间反应过来这才是学动态规划真正值钱的地方。 01背包问题完全指南：动态规划核心思想与代码实现
1. 先从选与不选开始为什么暴力枚举走不通我在面试候选人和带新人的时候发现一个很有意思的现象很多人谈起动态规划就头皮发麻觉得这是一道跨不过去的坎。但如果你把“01背包问题”这五个字拆开其实它描述的场景特别朴素——你面前有 N 件物品每件有自己的重量 w[i] 和价值 v[i]你手里有一个容量为 W 的背包每件物品只能选择装或者不装这就是“01”的由来0 代表不装1 代表装目标是让背包里装下的总价值最大。就这么个问题看上去毫无技术含量。但为什么它能成为算法领域的“钉子户”反复出现在笔试、面试、竞赛和各种教程里因为它的解法背后藏着动态规划最核心的思想把一个大问题拆成互相重叠的子问题用空间换时间。先说说为什么暴力枚举走不通。最直观的想法是一共有 N 件物品每件物品有“选”和“不选”两种状态那么所有组合方案就是 2^N 种。你需要遍历这些方案然后去重、筛选出重量不超过 W 的再找最大价值。听着好像可行但 N20 的时候是 104 万种N30 就是 10 亿种N50 直接奔着千万亿去了。就算你的计算机每秒能跑一亿次N50 也要跑到宇宙热寂。所以暴力法只适合 N≤20 左右的场景稍微上点规模就直接死给你看。那怎么优化关键就在“重复”这两个字上。你可以想一想当我依次决定要不要装第 i 件物品时前面已经决策完的物品会形成一个状态——当前的剩余容量和累计价值。不同的决策路径可能会在某个时刻落入完全相同的状态同样还剩 10kg 容量同样已经装了价值 500 的东西。既然状态相同后面还能装的物品也一样那么从这两个状态继续走最优结果必然也相同。于是我们只需要为每一个“剩余容量 已决策物品数”组合保留一个最优价值就够了根本不需要枚举完整路径。这就是 01 背包问题最底层的直觉用“决策到第几件物品 当前背包容量的剩余量”来定义状态把指数级的可能性压缩成 N×(W1) 个格子。压缩的背后不是魔法是因为我们砍掉了一模一样的大量冗余分支。想通了这一点后面所有状态转移方程、滚动数组、空间优化都是水到渠成的事。2. 一张表推到底手把手构建二维DP状态2.1 状态定义和转移方程的直觉来源我们先约定符号。假设有 N 件物品物品编号从 1 到 N第 i 件物品的重量是 w[i]价值是 v[i]。背包容量为 W。令 dp[i][j] 表示“只从前 i 件物品里挑放入容量为 j 的背包能获得的最大价值”。这里有几个细节需要解释清楚因为很多初学者第一次看到 dp[i][j] 都会困惑为什么第二维是背包容量 j而不是剩余容量其实两者本质等价但“容量为 j”的表达更利于递推。你再想深一层dp[i][j] 对应的那个书包里面装的物品全部来自前 i 件且它们的总重量不超过 j。接下来是状态转移。站在第 i 件物品面前只有两个选择不装第 i 件物品那么前 i 件物品能获得的最大价值就等于前 i-1 件物品在同样容量 j 下的最优值即 dp[i][j] dp[i-1][j]。意思就是“这件东西我不要了继承之前的最好结果”。装第 i 件物品前提是当前背包容量 j 装得下 w[i]也就是 j ≥ w[i]。如果装那么前 i-1 件物品只能使用剩余容量 j - w[i]然后再加上第 i 件物品的价值 v[i]即 dp[i][j] dp[i-1][j - w[i]] v[i]。因为我们要的是最大价值所以在这两个选项里取 max。于是就有了经典的转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) (当 j w[i]) dp[i][j] dp[i-1][j] (当 j w[i])为什么“继承之前的最好结果”是合法的因为前 i-1 件物品的所有选择组合已经被压缩在 dp[i-1][*] 这一整行里了。你不需要关心这些组合具体长什么样只需要知道它们在各个容量下的最大价值。这就是动态规划“最优子结构”的体现全局最优解一定包含子问题的最优解。更直白地说你可以从后往前倒推既然最终方案里第 N 件物品要么装、要么不装那么去掉第 N 件物品后的剩下的部分也一定是在前 N-1 件物品和对应剩余容量下的最优方案。如果不是最优你就可以把那一部分替换成更优的整个方案的价值还能更大这不就矛盾了嘛。2.2 亲手推一张完整的 DP 表理论讲半天不如亲手算一张表。我们直接看一个具体例子。假设背包容量 W10有 4 件物品物品编号重量 w[i]价值 v[i]123234345458初始化 dp[0][j] 0因为一件物品都不选价值肯定是 0。先处理 i1物品1重量2价值3。容量 j 从 0 到 1 时装不下所以 dp[1][0]0dp[1][1]0。从 j2 开始能装下了dp[1][j]3因为只有这一件物品装了价值就是3不装是0取最大值为3。所以这一行变成j012345678910dp[1][j]00333333333再看 i2物品2重量3价值4。j0、1、2 时装不下物品2只能继承 dp[1][j] 的值分别是 0、0、3。j3 时两种选择不装dp[1][3]3装dp[1][0]44。取最大值 4。j4 时不装是 3装是 dp[1][1]44所以 dp[2][4]4。j5 时不装是3装是 dp[1][2]47取7。后面继续算就能得到整行j012345678910dp[2][j]00344777777按同样的方式往下推dp[3][j] 和 dp[4][j] 我就不逐个列了。重点是看最后 dp[4][10] 的计算过程不装物品4价值是 dp[3][10]装物品4前提是容量至少 5那么价值是 dp[3][5]8。最终结果就是这两个数中的较大者。整个表的右下角那个格子就是整个问题的最优解。我建议你第一次学的时候一定找张纸把每一行每一列都手动填一遍。填完之后你会发现自己突然理解了“状态”到底是什么东西——它不是一个虚无缥缈的名词就是一个表格里的格子每一格都代表一个已经算清楚了的小规模子问题。2.3 时间复杂度与空间复杂度上面这种二维数组解法需要两层循环外层遍历物品 i内层遍历容量 j。每次循环只做常数次操作所以时间复杂度是 O(N×W)。空间上开了一个 (N1)×(W1) 的二维数组所以空间复杂度也是 O(N×W)。有人可能会问如果 W 特别大比如 W10^9这个算法是不是就废了是的这就是 01 背包问题的软肋——它的复杂度跟背包容量 W 线性相关W 一大就会超时超内存。所以当 W 很大、但 N 比较小的时候有人会换一种“按价值 DP”的思路也就是把价值当作第二维状态来设计算法。后文我会展开说。3. 一维数组优化为什么必须倒着遍历3.1 从二维滚动到一维的推导过程二维 DP 表虽然清晰但有个问题真的需要保存所有行的数据吗看看状态转移方程 dp[i][j] 用到的是哪几项——dp[i-1][j] 和 dp[i-1][j-w[i]]。这两项都在“上一行”里。也就是说当前 i 行的计算只依赖前一行 i-1再往前的 i-2、i-3 行根本不会再被用到。既然如此我们完全可以把二维表压缩成一维数组 dp[j]代表“当前处理到某一件物品时容量为 j 的背包能装下的最大价值”。每次处理新物品时用这个一维数组就地更新。这个技巧通常被叫做“滚动数组”或“就地更新”。一维更新的代码看起来极其简单for i in range(1, N 1): # 遍历每一件物品 for j in range(W, w[i] - 1, -1): # 容量从大到小遍历 dp[j] max(dp[j], dp[j - w[i]] v[i])但这里有一个极其关键、几乎所有新手都会踩的坑——内层循环为什么要从 W 逆序递减到 w[i]而不是顺序从小到大3.2 顺序遍历会出什么问题一个反例为了说清楚这个问题我们先跑一遍顺序遍历的错误代码for i in range(1, N 1): for j in range(w[i], W 1): # 错误示范从小到大 dp[j] max(dp[j], dp[j - w[i]] v[i])还是用上面的例子只看第一件物品w2v3处理时dp 数组初始全为 0。假设 W10。j2dp[2] max(0, dp[0]3) 3j3dp[3] max(0, dp[1]3) 3j4dp[4] max(0, dp[2]3) max(0, 33) 6出事了j4 的时候dp[2] 已经在当前这一轮循环里被更新成了 3这意味着我们在计算 dp[4] 的时候把“已经装入第一件物品”后的状态再装了一次第一件物品。换句话说同样的物品 1 被选了两次。可 01 背包里每件物品最多只能选一次这显然是错的。而逆序遍历为什么能避免这个问题因为 j 从大到小更新的时候计算 dp[j] 需要的是 dp[j-w[i]]而这个较小的下标 j-w[i] 一定小于 j且还没有被当前这一轮更新过。因此 dp[j-w[i]] 仍然是上一轮也就是还没处理当前物品的旧值这正好对应了“第 i 件物品只装一次”的语义。我见过有些教程只是扔给你一句“要倒序”然后让读者死记硬背。其实这个倒序的推导过程特别简单但一旦理解了你不仅知道怎么用还能在面试时讲清楚每一步的原因。更重要的是一旦 DP 题的变体里要求每个物品可以选无限次完全背包问题内层循环就要反过来变成正序遍历。如果你不理解倒序的底层逻辑面对完全背包时很容易再次迷茫。3.3 一维数组的初始化语义一维数组 dp[j] 的初始值全部设为 0这个做法对应的是“背包不一定要装满”的语义任何容量下我什么都不装价值都是 0这个方案总是合法的。后面我会再说如果题目改成“恰好装满背包”初始化方式就会大不相同。3.4 空间优化后的完整代码def knapsack_01(N, W, weights, values): dp [0] * (W 1) for i in range(N): # 逆序遍历容量 for j in range(W, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[W]这个版本的时间复杂度仍是 O(N×W)但空间复杂度降到了 O(W)这是面试和笔试里最常用的版本。我自己的习惯是先写二维版本理清思路再用一维版本提交代码避免一上来就写错逻辑。4. 从最优值到最优方案回溯出具体选了哪些物品很多教程讲完求最大价值就收工了但实际业务里你往往不只关心“最多能装多少价值”还想知道“到底该选哪几件物品”。比如公司要做一个预算有限的投资组合你不仅需要知道最大收益还得知道具体投哪几个项目。当使用二维 DP 数组时回溯方案非常简单。我们从最后一个格子 dp[N][W] 开始倒推如果 dp[i][j] dp[i-1][j]说明第 i 件物品没有被选中那么问题收缩到 dp[i-1][j]即“前 i-1 件物品、容量 j”的最优方案。如果 dp[i][j] dp[i-1][j-w[i]] v[i]同时满足 j ≥ w[i]说明第 i 件物品被选中了于是把 i 记录下来然后问题收缩到 dp[i-1][j-w[i]]。如果两个条件同时成立dp[i-1][j] 恰好等于 dp[i-1][j-w[i]] v[i]说明“选不选这件物品”都能达到同样的最大值。这时可以根据需要任选一种路径比如优先选或者优先不选一般来说优先记录“选”的那条路径即可。这里有个细节容易让人犯迷糊如果我用的是空间优化后的一维数组dp[j] 里存的只是最终结果中间过程被反复覆盖了还能回溯吗答案是基本不行除非额外记录选择矩阵。所以在需要输出具体方案时我建议老老实实用二维数组别为了省空间丢掉回溯能力。这是典型的“空间换功能”的取舍实际面试时也是加分项。下面是个回溯的示意代码def knapsack_with_solution(N, W, weights, values): 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 weights[i - 1]: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] values[i - 1]) else: dp[i][j] dp[i - 1][j] # 回溯选中的物品 selected [] j W for i in range(N, 0, -1): if j weights[i - 1] and dp[i][j] dp[i - 1][j - weights[i - 1]] values[i - 1]: selected.append(i) j - weights[i - 1] selected.reverse() return dp[N][W], selected回溯的复杂度是 O(N)只扫描一遍物品就够了。这里要注意当你发现 dp[i][j] 同时等于不装和装的两种情况时必须按照你自己的业务规则选择一条路径否则你得到的“方案”不一定唯一。比如有些场景希望装更少的物品因为每多一件都要增加管理成本那就在相等时优先“不选”。5. 初始化定义决定题目走向恰好装满与常见变体5.1 “最多能装”和“恰好装满”的初始化玄机关于 01 背包最常被忽略的一个细节就是初始化条件。前面我们一直把 dp 数组全部初始化为 0这是因为题目问的是“在容量 W 内最多能装多少价值”不要求背包装满所有容量的“零价值空包”都是合法的基准状态。但如果题目改成“背包必须恰好装满求能装下的最大价值装不满返回无解或某个特殊值”初始化就要大变。二维版本dp[0][0] 0dp[0][j] 当 j 0 时设为负无穷比如 -inf表示“用 0 件物品根本无法凑出恰好容量 j 的状态”这是非法状态。一维版本dp[0] 0dp[1..W] -inf。这样在状态转移时任何“由非法状态转移而来”的结果都会因为加上 -inf 而仍然保持非法意义不会被错误地当成合法答案。为什么要用负无穷而不是 0举个例子如果初始化全是 0那么容量 j5 时你可能会得到“什么都不装也是合法方案价值是 0”的结论。这在“恰好装满”语义下就错了——容量 5 的背包空空如也哪来的恰好装满所以必须让这些状态从一开始就“烂掉”后续怎么转移都不会被误用。我早年刷题时在这里翻过车。题目要求恰好装满我图省事直接用全 0 初始化结果样例过了、提交全错。排查了半天才意识到不是转移方程的问题是初始状态把非法状态和合法状态混为一谈了。5.2 求方案总数的变体除了求最大价值01 背包家族里还有一个常见变体求“恰好装满背包的方案数”。转移方程变成了dp[j] dp[j] dp[j - w[i]]初始化时 dp[0] 1其余为 0。含义是凑出容量 0 的方案数为 1什么都不选其他容量初始方案数为 0。遍历物品时每件物品选择“取”或“不取”方案数自然就是两者相加。这个变体在 LeetCode 的“目标和”“组合总和 IV”等题目中都有体现核心思想完全一致。5.3 求最小价值的变体有时候题目把“价值”换成“代价”让你求“装满背包的最小代价”。这也很简单把所有 dp[j] 初始化为正无穷dp[0]0转移方程把 max 改成 min 即可。思路和“恰好装满”一模一样区别只是把取最大变成取最小。5.4 二维费用背包再加一个限制维度如果每件物品除了重量之外还有体积或者说背包有两个限制条件那就需要三维 DPdp[i][j][k] 表示前 i 件物品在重量为 j、体积为 k 的限制下能取得的最大价值。转移时会同时考虑重量和体积两个维度。这个变体的思路没有本质变化只是多了一维循环空间和时间复杂度都随之增加。我在项目里遇到过类似场景给服务器分配任务时既怕 CPU 超核又怕内存超限每个任务对两个资源都有需求二维费用背包正好派上用场。6. 实战经验与常见误区盘点6.1 大 W 场景下的“价值反打”技巧前面提到当背包容量 W 特别大时O(N×W) 的复杂度会爆掉。这时有个常见的应对思路如果单件物品的价值 v[i] 比较小且总价值 V 在可接受范围内那就把“价值”当作状态维度dp[v] 表示“凑出价值 v 所需的最小重量”。最后从小到大遍历价值找到第一个 dp[v] ≤ W 的值作为答案。这个算法的时间复杂度是 O(N×V)。我在开源项目代码里见过这种做法专门用来处理 W 高达几千万但单件价值只有几百的题目。6.2 物品重量为 0 或负数时的雷区重量为 0 的物品往往被题目悄悄塞进来当陷阱。如果物品重量是 0逆序遍历和正序遍历就变得没有区别了因为 j-w[i] j无论顺序如何dp[j] 都能被自己更新。处理这类物品时要格外注意是否需要“无限次使用”的语义。至于重量为负的物品那就更麻烦了因为不能再按普通 01 背包处理通常需要特殊平移或重新建模这个超出了本文范围但如果你遇到了别慌先想想能不能把负重量问题转换成“偏移量”问题。6.3 典型误区汇总我在带人刷题时整理了这张高频误区对照表几乎每个人都至少中过一条误区错误表现正确做法内层循环顺序一维优化时正序遍历容量必须逆序防止同一物品被重复选择初始化混乱恰好装满问题用了全 0 初始化dp[0]0其余设正/负无穷回溯方案时用一维数组想让一维 DP 输出选中的物品使用二维 DP 记录完整路径忘记考虑装不下的情况转移时直接计算 dp[i-1][j-w[i]] v[i]但 j w[i] 时越界先判断 j w[i]或循环从 w[i] 开始把状态维度写反dp[i][j] 中 i 代表容量j 代表物品数约定清晰保持一致写代码前先写注释这里再补充一个我自己常犯的失误二维 DP 初始化时我偶尔会把 dp[0][j] 和 dp[i][0] 的边界弄混。dp[0][j] 表示“0 件物品在各种容量下的最大价值”一定是 0dp[i][0] 表示“容量 0 时选前 i 件物品的最大价值”也一定是 0什么都装不下。两者都是合法边界任何一边漏了都会导致后续转移出错。6.4 工程实践里如何选择 DP 数组类型如果你在做算法题int 数组通常够用。但如果题目里的价值和容量数量级都在 10^9 附近加法和比较很容易溢出这时要把 dp 数组声明为 longPython 就没有这个烦恼。另外不可达状态的初始化值要选准求最大值时用负无穷如 -10^18求最小值时用正无穷如 10^18避免在计算 max/min 时被实际可达的边界值干扰。我自己平时写代码有个习惯先写二维版本跑通小样例再改写成一维优化版本。这不是浪费时间而是用二维版本当“参考答案”一旦一维版本出 bug可以快速对照阶段结果定位问题。很多人一上来就想写最精简的代码结果 debug 的时间比写代码还长反而得不偿失。7. 举一反三从 01 背包到完全背包和多重背包搞懂了 01 背包的倒序遍历再去看完全背包每件物品可以选无限次就会豁然开朗for i in range(N): for j in range(weights[i], W 1): # 正序遍历容量 dp[j] max(dp[j], dp[j - weights[i]] values[i])唯一的变化就是把内层循环从逆序改成正序。为什么因为正序意味着在计算 dp[j] 时dp[j-w[i]] 可能已经在当前这轮循环中被更新过等价于“还可以继续选择当前物品”正好符合完全背包“无限取用”的语义。你看理解倒序原理的好处在这里体现得淋漓尽致不需要死记两个版本只要想清楚“一维数组里的旧值代表什么”一切都能推导出来。多重背包则更复杂一些它限制每件物品最多取 c[i] 次。常规做法是把它拆成 01 背包把第 i 件物品拆成多件独立的“01 物品”每件的重量和价值是原物品乘以系数 1、2、4、……二进制拆分这样就能把 c[i] 次选择组合成任意 0 到 c[i] 次。这个技巧本质上还是 01 背包的变形所以你会发现把基础打牢了后面这些变体学起来都是顺水推舟。实际业务里安排服务器资源、预算分配、排产计划、商品打包推荐……这些场景往往都能抽象成某种背包问题。我接过一个需求在广告预算有限的情况下从几十个投放渠道里挑出组合让预估曝光最大化。这不就是标准的 01 背包吗每个渠道是物品预算限额是背包容量预估曝光是价值。虽然数据规模不大但用背包写出来的程序只有几十行比业务同事用 Excel 手动试方案不知道高到哪里去了。关于 01 背包我最后分享一个心得别背代码去背“为什么”。为什么二维能压一维为什么一维要倒序为什么恰好装满要初始化成无穷这三个“为什么”吃透了你就是把 01 背包从“会做题”提升到了“理解它”的层次。做到了这一步不管题目怎么改、数据范围怎么调、是面试手写还是业务落地你都能第一时间反应过来这才是学动态规划真正值钱的地方。