1. 背包问题到底在解决什么事1.1 从“装箱子”说起问题的真实原型我第一次接触背包问题是在准备算法竞赛的时候当时看了一堆教材公式推导写得密密麻麻但就是不明白为什么一个“往包里塞东西”的问题能成为动态规划的入门必学。后来做了几十道变形题才反应过来背包问题之所以经典是因为它把“资源有限、选择离散、求最优”这三个现实中最常见的约束条件压缩到了一个极简模型里。你手上有一个容量为 W 的背包面前摆着 n 件物品每件物品有自己的重量 w[i] 和价值 v[i]。你要做的是挑出一部分物品放进去在总重量不超过 W 的前提下让总价值最大。这个场景在现实中随处可见预算有限时怎么分配广告投放、服务器内存有限时怎么选缓存对象、出差行李箱空间有限时怎么选带哪些设备。问题的外壳在变内核始终是那一套。01背包和完全背包的区别只有一句话01背包里每件物品最多拿一次完全背包里每件物品可以拿任意多次。就这么一个小小的条件差异导致状态转移方程的形式完全不同遍历方向也正好相反。很多人学的时候把两者混在一起记结果一上考场就写反循环这也是我在刷题群里见到最多的提问之一。所以这篇文章我打算把两者的推导过程完整走一遍把“为什么是这个方向”讲透而不是让你背代码。1.2 状态定义这一步决定了后面所有的复杂度动态规划最核心的一步从来不是写转移方程而是定义状态。状态定得好转移方程是自然长出来的状态定歪了后面怎么推都别扭。背包问题里最直觉的状态定义是二维的dp[i][j] 表示只考虑前 i 件物品在背包容量为 j 的情况下能获得的最大总价值。这里有两个维度需要理解清楚。第一个维度 i 是“决策阶段”代表我们已经对前 i 件物品做出了取舍决定后面的物品还没考虑。第二个维度 j 是“资源剩余”代表当前容量约束。两个维度合起来就把整个求解过程切成了 n × (W1) 个子问题。我特别想强调一下“只考虑前 i 件”这个措辞。很多人初学时会写成“从前 i 件里选”这两种写法在结果上一样但在理解上差别很大。“只考虑前 i 件”是一种阶段划分的思想——我们按顺序一件一件做决策做完第 i 件的决策后局面就固定下来了不会再回头改。这种“无后效性”正是动态规划能成立的前提。如果你定义状态时掺杂了“后面可能还要换”的念头那这题就没法用 DP 做了。2. 01背包每个物品只有一次机会2.1 状态转移方程的推导过程有了状态定义接下来就是推导转移。面对第 i 件物品我们只有两个选择拿或者不拿。这两条路各自对应一个结果我们取其中的较大值。不拿第 i 件物品的时候问题直接退化成“只考虑前 i-1 件容量还是 j”对应的值就是 dp[i-1][j]。注意这里容量没有变化因为你不拿它重量自然不消耗。拿第 i 件物品的时候前提是当前容量 j 得放得下它也就是 j w[i]。放进去之后背包容量变成了 j - w[i]而剩下的决策空间是前 i-1 件物品——因为物品 i 已经被用掉了不能再用第二次。所以对应的值是 dp[i-1][j-w[i]] v[i]。把两条路合起来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])这个方程里最值得琢磨的是第二项为什么是 dp[i-1] 而不是 dp[i]。答案就在“01”这两个字里每件物品只能用一次所以当你决定拿第 i 件的时候第 i 件的名额就已经消耗掉了接下来只能从前 i-1 件里选。如果你写成了 dp[i][j-w[i]] v[i]那实际上是在说“拿完第 i 件之后还可以继续拿第 i 件”这就变成完全背包了。我当初就是在这里卡了整整一个下午反复检查代码逻辑却找不到问题最后才意识到自己是把 i-1 写成了 i。所以你在手推的时候务必把“当前物品用没用掉”这件事想在前面。2.2 二维到一维为什么能省掉第一维二维写法的时间复杂度是 O(nW)空间复杂度也是 O(nW)。对于 W 达到几万、n 达到几千的题目二维数组很容易超出内存限制。这时候就需要做滚动数组优化把第一维压掉。压缩的依据在于计算 dp[i][j] 时只依赖 dp[i-1][...] 这一行的数据第 i-2 行及更早的数据再也用不到了。所以我们可以只用一维数组 dp[j]然后按 i 从 1 到 n 的顺序逐行更新每一轮更新都在“覆盖”上一轮的结果。但这里有一个非常关键的细节内层循环必须倒序遍历。原因在于dp[j] 在更新时需要读取 dp[j-w[i]] 的旧值也就是上一轮 i-1 的值但如果 j 是从小到大遍历的那么 dp[j-w[i]] 很可能在本轮已经被更新过了读到的是本轮 i 的新值。一旦读到了新值就意味着物品 i 被重复使用了01背包就退化成了完全背包。我用一个具体例子手推一遍你就明白了。假设物品 1 的重量 w2价值 v5背包容量 W6。一开始 dp 数组全是 0。倒序遍历 j 从 6 到 2jdp[j-w] 的值候选值 dp[j-w]v原 dp[j]更新后 dp[j]6dp[4]05055dp[3]05054dp[2]05053dp[1]05052dp[0]0505每一步读到的 dp[j-w] 都还是初始值 0因为 j-w 总是小于当前的 j而我们是倒着走的那些位置还没被本轮更新过。这样物品 1 就只被用了一次。如果是正序遍历 j 从 2 到 6j2 时 dp[2] 被更新为 5j4 时读取 dp[2] 得到的是刚更新的 5于是 dp[4] 55 10j6 时读取 dp[4]10dp[6]15。结果背包里塞了三个物品 1这显然是 01背包不允许的。这个对比非常直观我建议你自己拿笔推一遍印象会比看十遍书都深。2.3 倒序遍历的真正原因用一句话记住很多人把“01背包倒序、完全背包正序”当成口诀背下来但一到变形题就懵。我的记忆方式是倒序保证每个物品只被当前这一轮考虑一次正序允许同一个物品在当前轮被反复考虑。换个角度说正序遍历实际上是在“同一行内传递状态”也就是 dp[i][j] 可以从 dp[i][j-w] 推出来这恰好对应完全背包“可以重复拿”的语义。倒序遍历则是“跨行传递状态”dp[i][j] 只能从 dp[i-1][j-w] 推出来对应 01背包“只能拿一次”的语义。所以遍历方向不是随便定的它是语义的一部分。理解了这一点以后碰到“每个物品最多拿 k 次”这种变形你就知道该怎么想了——是用二进制拆分还是加一层循环控制次数。3. 完全背包物品可以无限次拿3.1 从二维写法和它的三重循环说起完全背包的二维转移方程长这样dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i]) (j w[i])和 01背包唯一的区别就是第二项里的 i-1 变成了 i。这个改动看似微小含义却完全不同dp[i][j-w[i]] 表示“在已经考虑过第 i 件物品的基础上容量还剩 j-w[i] 时的最大价值”也就是说第 i 件物品可以继续被选择。这就是“无限次拿”的数学表达。如果你按二维方程直接写代码会是一个三层循环外层枚举物品 i中层枚举容量 j内层还要枚举“拿几个第 i 件物品”。内层那层循环就是 k 从 0 到 j/w[i]逐一比较拿 0 个、拿 1 个、拿 2 个……的最大值。这种写法的时间复杂度是 O(nW·(W/w))在数据量大的时候会直接超时。优化的思路是既然 dp[i][j-w[i]] 已经把“再拿一个第 i 件”的情况包含进去了那我们就没必要单独枚举拿几个直接用它就行。这层优化把复杂度降回 O(nW)代价是我们要保证 dp[i][j-w[i]] 在计算 dp[i][j] 时已经算好了——而这正好要求 j 从小到大遍历。3.2 正序遍历的数学依据现在把二维压成一维。一维数组 dp[j] 的更新公式和 01背包看起来一模一样dp[j] max(dp[j], dp[j-w[i]] v[i])区别只在 j 的遍历方向。完全背包用正序理由在 2.2 节里已经反着讲过了正序遍历时dp[j-w[i]] 在本轮已经被更新过读到的是本轮 i 的新值这就等价于“第 i 件物品可以被再次选择”。所以正序不是巧合它是完全背包语义的直接映射。我做个对称的手推验证。物品 1 的重量 w2价值 v5容量 W6正序遍历jdp[j-w] 的值候选值 dp[j-w]v原 dp[j]更新后 dp[j]2dp[0]05053dp[1]05054dp[2]5100105dp[3]5100106dp[4]1015015可以看到 dp[2]、dp[4]、dp[6] 依次递增正好对应拿了 1 个、2 个、3 个物品 1。这就是完全背包想要的结果。3.3 两个问题的代码只差一个循环方向把两段核心代码摆在一起对比你会发现它们的骨架几乎完全相同# 01背包 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]) # 完全背包 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])唯一的差别就是 range 的第三个参数。这也是为什么面试官特别喜欢让你手写这两个背包——不是考你记不记得代码而是考你懂不懂那个减号和方向背后的道理。我在帮别人看代码的时候只要看到这个方向反了基本就能判断他对状态转移的理解还停留在背诵阶段。另外补充一个完全背包的等价写法。有些题目里 W 特别大而物品种类很少这时可以换一种循环顺序外层枚举容量、内层枚举物品。对于完全背包这两种循环顺序都成立因为每个物品可以无限取循环顺序不影响结果。但对 01背包来说外层必须枚举物品、内层必须枚举容量且倒序顺序换了就会出错。这个细节在做多重背包混合题的时候尤其容易踩坑。4. 边界处理与初始化那些让人 WA 一整晚的细节4.1 恰好装满 vs 最多能装多少背包问题有一组非常经典的变体问法从“最多能装多少价值”变成“恰好装满背包时的最大价值”或者“有没有办法恰好装满”。这两种问法的转移方程完全一样区别只在初始化。如果题目问的是“容量不超过 W 的最大价值”那么 dp 数组全部初始化为 0 就行。因为容量小于 W 也是一种合法状态什么都不装也有价值 0这是允许的。如果题目问的是“恰好装满容量为 W 的背包”那么 dp[0] 初始化为 0其余位置全部初始化为负无穷。道理是这样的容量为 0 时什么都不装确实是一种合法的“恰好装满”方案价值为 0而容量为 jj0时如果没有任何物品组合能凑出 j那这个状态就是不可达的必须用一个极小的值标记它防止它被后续转移当成有效状态使用。我实测下来很多新手在这一步翻车。他们写了标准的一维转移代码初始化全填 0然后跑样例发现答案比预期大——因为程序实际上把“不装满”的情况也算进去了结果自然偏大。判断的窍门是如果题目里出现了“恰好”“正好”“刚好”这类词九成需要特殊初始化。4.2 数组下标从 0 还是从 1 开始另一个高频坑是下标起点。物品数组如果从 0 开始存那么循环里读 w[i] 时要格外小心因为 dp 的下标通常从 0 开始二者容易错位。我的习惯做法是输入时把物品重量和价值都存到下标 1 开始的位置也就是让 w[1] 到 w[n] 对应第 1 到第 n 件物品w[0] 空着不用。这样循环从 1 到 n和状态定义的“前 i 件”严格对应几乎不会出错。多开一个位置的内存开销可以忽略不计但它省下的调试时间非常值。如果你坚持用 0 起始下标那么状态定义就得改成“考虑下标 0 到 i 的物品”循环写 range(0, n)转移里用 w[i]。两种写法都对但不要混着用。我见过最隐蔽的 bug 就是状态定义写的是“前 i 件”循环却从 0 开始结果第一件物品被算了两次样例能过是因为样例里第一件物品恰好不优。还有一个小细节当物品重量 w[i] 大于背包容量 W 时一维写法里 j 的循环会直接跳过这个物品因为 range(W, w[i]-1, -1) 在 w[i] W 时是空区间。这个行为是正确的但在二维写法里需要显式写 dp[i][j] dp[i-1][j]不然会漏掉状态。一维写法在这里反而更省心。5. Python实现与性能优化实操5.1 基础版本代码与逐行注释先给你一份可以直接复制运行的完整代码包含输入处理和两个背包的求解。import sys def solve(): data sys.stdin.read().split() idx 0 n int(data[idx]); idx 1 W int(data[idx]); idx 1 w [0] * (n 1) v [0] * (n 1) for i in range(1, n 1): w[i] int(data[idx]); idx 1 v[i] int(data[idx]); idx 1 # 01背包 dp1 [0] * (W 1) for i in range(1, n 1): for j in range(W, w[i] - 1, -1): dp1[j] max(dp1[j], dp1[j - w[i]] v[i]) # 完全背包 dp2 [0] * (W 1) for i in range(1, n 1): for j in range(w[i], W 1): dp2[j] max(dp2[j], dp2[j - w[i]] v[i]) print(dp1[W], dp2[W]) solve()这份代码里有几个我特意处理的地方。用sys.stdin.read().split()一次性读入所有输入比逐行 input() 快很多在 n 和 W 上万的时候差距明显。数组开 n1 和 W1 的大小是为了让下标和物品编号、容量值直接对应省掉所有减一的操作。两个背包分别用独立的 dp 数组避免状态互相污染。5.2 常数优化与复杂度分析O(nW) 的复杂度虽然已经是最优的量级但在常数上还有不少压缩空间。我在实际做题时常用的几个技巧第一重量超过容量的物品直接跳过。反正放不下参与循环只会浪费时间。可以在输入后先过滤掉 w[i] W 的物品。第二去掉被支配的物品。如果存在物品 A 和物品 B满足 w[A] w[B] 且 v[A] v[B]那么 A 永远不会被选——同样的重量 B 更轻价值还更高。把这类物品剔除后剩下的物品重量严格递增、价值也严格递增循环次数会减少。第三缩小 j 的循环下界。设后面所有物品的总重量为 rest那么在处理第 i 件物品时容量 j 不需要从 W 一直枚举到 w[i]只需要枚举到 max(w[i], W - rest) 就够了。因为如果剩余容量大于后面所有物品的总重量那多出来的容量无论如何也用不上。这个优化在物品数量多、总重量远小于 W 的时候效果非常明显。做一个粗略的性能估算n1000、W10000 时内层循环总共执行约一千万次Python 里大概跑 3 到 5 秒。加上上面的常数优化通常能压到 1 秒以内。如果还是不够快可以考虑用数组模块或者把内层循环改写成列表推导但这些属于进阶技巧初学阶段先把逻辑跑通更重要。# 常数优化的写法示例 rest sum(w[1:]) lower 0 for i in range(1, n 1): rest - w[i] lower max(w[i], W - rest) for j in range(W, lower - 1, -1): if dp1[j - w[i]] v[i] dp1[j]: dp1[j] dp1[j - w[i]] v[i]这里我把 max 函数换成了 if 判断因为 Python 里函数调用的开销不小在大循环里累积起来很可观。这个改动很土但实测能省百分之十几的时间。6. 常见问题与排查技巧实录6.1 常见错误速查表下面这张表是我整理的高频出错点几乎覆盖了我在刷题群里见到的大部分提问。建议你写完代码后对着表自查一遍。现象可能原因排查方法答案比预期大01背包内层写成了正序检查 range 第三个参数是否为负数答案比预期小完全背包内层写成了倒序同上方向应该反过来恰好装满问题答案错误初始化没设负无穷dp[0]0其余为 -inf程序报下标越界循环起点小于 w[i]j 的下界设为 w[i]部分物品没被考虑循环范围写成了 range(n) 但物品从 1 存统一用 range(1, n1)内存超限用了二维数组改用一维滚动数组结果随机波动dp 数组没清空就复用了每个测试用例重新初始化6.2 变形题识别方法掌握基础模板之后真正的挑战是识别变形。我总结了一个三步判断法用来应对绝大多数背包变形题。第一步看“选择次数”。如果每个物品只能选 0 或 1 次走 01背包如果可选无限次走完全背包如果有个上限 k走多重背包。多重背包的通用解法是二进制拆分把 k 个相同的物品拆成 1、2、4、8……这些 2 的幂次组合转换成 01背包来做。比如某物品最多拿 13 次就拆成 1、2、4、6 四组每组作为一个新的 01背包物品。这样任意 0 到 13 的次数都能用这几组凑出来而且组数是对数级别的效率很高。第二步看“约束维度”。如果只有一个容量约束就是标准背包如果多了一个约束比如体积和重量同时限制那就是二维费用背包dp 数组要升到两维两个容量都要倒序或正序。第三步看“问法”。问最大值用 max 转移问方案数就把 max 换成加法问是否存在就把值域换成布尔。方案数类问题特别容易漏掉取模我在一次比赛里就是因为忘了取模明明思路全对却只过了一半的测试点。6.3 手推小数据的方法最后分享一个我自己一直在用的调试习惯写任何背包代码之前先用纸笔手推一遍 n3、W5 这样的小数据。把 dp 数组的每一轮变化都写出来对照你期望的答案检查。这个习惯看起来笨但它的价值在于它逼着你把状态转移的每一步都想清楚而不是依赖编译器告诉你哪里错了。尤其是 01背包和完全背包容易混淆的时候手推一次倒序和正序的差异比看十篇博客都管用。我到现在遇到复杂的背包变形比如有依赖关系的树形背包还是会先在纸上画一遍状态表格确认转移方向没写反再动手敲代码。另外一个手感上的经验是如果你发现自己在反复修改循环边界那大概率是状态定义没想清楚。这时候正确做法不是继续试参数而是回到第 1.2 节把“dp[i][j] 到底代表什么”重新写一遍。状态定义一旦明确边界和方向基本都是唯一的不需要猜。对于刚开始学的朋友我的建议是先老老实实把 01背包的二维版本写对再理解一维优化为什么能省空间最后才去记“倒序”这个结论。跳过中间步骤直接背模板短期内能过题但一遇到变形就会露馅。背包问题是动态规划里少有的、可以被完全吃透的模型花两天时间把它彻底搞明白后面学区间 DP、树形 DP 的时候会轻松非常多。