1. 从会求最优解到会求方案差在哪一步很多人学01背包能把状态转移方程背得滚瓜烂熟for i in range(1, n 1): for j in range(V, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])一维滚动数组几行代码最大价值就算出来了。然后突然遇到两个进阶问法当场卡壳求方案数达到这个最大价值的选法一共有多少种求具体方案到底是选了哪几件物品比如经典例子物品有(重量2, 价值3)、(重量3, 价值4)、(重量5, 价值7)背包容量5。最大价值一眼就能算出来是7但再追问一句有几种选法能凑出7很多人就开始懵了——单独选第3件能凑出7选第1件加第2件也能凑出7一共2种。这个例子简单心算都能算一旦物品数量涨到几十上百靠人脑枚举完全不现实。更麻烦的是第二个问题。滚动数组算完dp之后你手里只有一个最大价值的数字中间过程全被覆盖了根本不知道选了哪些物品。你必须重新设计状态和遍历顺序才能把方案抠出来。这篇文章要做的就是把这两件事彻底讲透。我会从状态定义的角度重新推导说明为什么求方案数和求具体方案需要不同的做法然后给一个综合题目的完整解法最后把我实际写题时踩过的坑全部列出来。内容覆盖Python和C两种实现思路竞赛党和刷题党都能直接用。2. 求方案数为什么加法原理可以直接叠加先明确一下这个问题的标准定义给定n件物品每件只选一次和背包容量V在总重量不超过V的前提下总价值达到最大值的选法有多少种。选法不同指选的物品集合不同。2.1 状态设计必须用恰好装满的背包求最大价值时dp[j]表示容量不超过j的最大价值这样做很舒服因为初始化全0就行。但求方案数时这种定义会有问题——你分不清dp[j]到底是通过哪条路到达的。我推荐的方案是改用恰好装满语义dp[j]恰好使用容量j时能获得的最大价值如果这个容量无法被恰好凑出记为负无穷。cnt[j]恰好使用容量j、且价值达到dp[j]的方案数。初始化时dp[0] 0cnt[0] 1。容量0恰好装满只有什么都不选这一种方案。其余dp[j] 负无穷cnt[j] 0。转移时对第i件物品重量w价值v倒序遍历jif dp[j - w] ! NEG: if dp[j - w] v dp[j]: dp[j] dp[j - w] v cnt[j] cnt[j - w] elif dp[j - w] v dp[j]: cnt[j] cnt[j - w]这段代码的逻辑值得细品。更新方式只有两种情形替换从j-w这个容量转移过来价值比当前dp[j]更大那么能凑出j-w的方案数就是能凑出j的方案数直接赋值。累加转移过来的价值恰好等于当前dp[j]说明多了一条并列最优的路径方案数相加。这里有一个新手最容易搞错的点为什么不能直接写cnt[j] cnt[j-w]因为如果新方案价值更低它根本不属于最优方案如果价值更高旧方案要被淘汰而不是保留。只有价值相等才有资格做加法。2.2 最后一步把所有最优容量累加跑完所有物品后最大价值未必只出现在容量V上。比如某件物品重量是0或者物品总重量小于V最大价值对应的容量可能是V也可能是更小的某个容量j。所以最终答案不能直接输出cnt[V]而是要先找出所有dp[j]中的最大值max_val然后把所有dp[j]等于max_val的cnt[j]加起来max_val max(dp) ans 0 for j in range(V 1): if dp[j] max_val: ans cnt[j]不同容量j对应的选法集合一定不同因为总重量不同所以不会重复计数。我用前面那个例子走一遍过程。物品(2,3)、(3,4)、(5,7)容量V5。处理第1件物品(2,3)后dp[2]3cnt[2]1。 处理第2件物品(3,4)后dp[3]4cnt[3]1dp[5]7cnt[5]1即第1件第2件。 处理第3件物品(5,7)后dp[5]本来已经是7新方案单独选第3件价值也是7于是cnt[5]从1变成2。最终max_val7满足dp[j]7的只有j5答案为cnt[5]2。和心算结果一致。注意一个细节必须用倒序遍历j保证每件物品只被选一次。如果你在这里写成正序遍历就变成完全背包了方案数会严重偏大这属于经典错误后面我会专门讲。3. 具体方案为什么必须换一个方向做DP求方案数只需要数字但求具体方案需要把选了哪几件完整还原出来。这件事如果用一维滚动数组做基本无解——滚动数组的目的是覆盖状态节省空间但也把决策路径抹掉了。3.1 先看错误思路正向做完再逆推有些同学会想我用二维dp[i][j]跑完然后从in往前倒推如果dp[i][j] dp[i-1][j-w[i]] v[i]就说明第i件被选了然后j减掉w[i]继续看下一件。这个思路在方案唯一的情况下行得通但一旦出现并列最优就会出问题。举个简单例子容量5物品(2,3)、(3,4)、(5,7)。最终最优价值是7对应方案有{3}和{1,2}两个。从i3往前推发现dp[3][5] dp[2][0] 7说明第3件可以选但如果选第3件就漏掉了{1,2}这个方案。你机器判断时不知道哪个方案更优只能靠额外规则。3.2 字典序最小方案把逆向过程变成正向选择如果题目要求输出字典序最小的方案经典做法是彻底反转DP方向dp[i][j]重新定义为从第i件物品到最后一件物品在容量j下能获得的最大价值。遍历物品时从n往1做。输出方案时从1往n判断。核心就一句话**编号小的物品在决策时优先级最高。**只要选了编号小的物品仍然能达到全局最优就一定要选它。这样从编号1扫到n得到的方案字典序最小。看代码更直观dp [[0] * (V 1) for _ in range(n 2)] for i in range(n, 0, -1): w, v items[i] for j in range(V 1): dp[i][j] dp[i 1][j] if j w: dp[i][j] max(dp[i][j], dp[i 1][j - w] v) j V chosen [] for i in range(1, n 1): w, v items[i] if j w and dp[i][j] dp[i 1][j - w] v: chosen.append(i) j - w注意输出阶段的判断条件dp[i][j] dp[i 1][j - w] v成立说明选第i件物品能达到dp[i][j]这个最优价值。这里包含了两种可能不选第i件价值更低必须选才能达到最优。不选和选价值一样高但为了字典序最小优先选。只有当这个等式不成立时才说明选了第i件反而达不到当前最优这时才跳过去选后面的物品。3.3 为什么从n到1做DP是关键你可能想问为什么不能沿用正向dp[i][j]前i件物品的范围然后把输出循环改成从n往1判断答案是输出阶段从1往n扫描需要知道我后面剩哪些物品可选而正向dp[i][j]只知道我已经考虑了前i件你无法回答第i件到第n件这个区间内的最优情况。换个角度理解。dp[i][j]是从i到n这个后缀区间的状态所以从1开始输出时每一件物品能否选择等价于在当前剩余容量下能否找到一条以它为起点的最优路径。如果没有反转方向这个能否根本判断不了。反过来说如果题目要求任意方案而非字典序最小通常从n往1倒推反而更自然。但很多题不会明确说任意方案而会用字典序最小来消除多解性所以直接掌握从n到1的做法性价比最高。4. 完整题解最优价值方案数字典序最小方案一次搞定把上面两个问题合并就是一个非常典型的综合题。这里我给出完整可运行的Python代码并逐步解释每个变量的作用。4.1 题目描述有n件物品每件物品有重量w[i]和价值v[i]背包容量为V。每件物品最多选一次。要求输出能获得的最大价值。输出达到该最大价值的不同选法数量。在这些最优选法中输出字典序最小的方案编号序列。约束n≤1000V≤1000w[i]和v[i]为正整数。4.2 完整代码def solve(): n, V map(int, input().split()) w [0] * (n 1) v [0] * (n 1) for i in range(1, n 1): w[i], v[i] map(int, input().split()) # ---------- 第一部分求最大价值一维经典写法 ---------- dp1 [0] * (V 1) for i in range(1, n 1): for j in range(V, w[i] - 1, -1): dp1[j] max(dp1[j], dp1[j - w[i]] v[i]) max_val max(dp1) # ---------- 第二部分求方案数恰好装满语义 ---------- NEG -10**9 dp2 [NEG] * (V 1) cnt [0] * (V 1) dp2[0] 0 cnt[0] 1 for i in range(1, n 1): for j in range(V, w[i] - 1, -1): if dp2[j - w[i]] NEG: continue new_val dp2[j - w[i]] v[i] if new_val dp2[j]: dp2[j] new_val cnt[j] cnt[j - w[i]] elif new_val dp2[j]: cnt[j] cnt[j - w[i]] ways 0 for j in range(V 1): if dp2[j] max_val: ways cnt[j] # ---------- 第三部分求字典序最小方案从n到1做DP ---------- dp3 [[0] * (V 1) for _ in range(n 2)] for i in range(n, 0, -1): for j in range(V 1): dp3[i][j] dp3[i 1][j] if j w[i]: dp3[i][j] max(dp3[i][j], dp3[i 1][j - w[i]] v[i]) chosen [] j V for i in range(1, n 1): if j w[i] and dp3[i][j] dp3[i 1][j - w[i]] v[i]: chosen.append(i) j - w[i] print(max_val) print(ways) print(*chosen) if __name__ __main__: solve()4.3 三段代码为什么不共用同一个dp很多读者会疑惑第一段已经求出了最大价值第二段为什么不能直接用dp1来统计方案因为dp1的语义是容量不超过j的最大价值初始化全0导致你没法区分什么都没放和恰好凑满某个容量这两种情况。方案数统计非常依赖初始状态的唯一性——只有容量0算作一种已凑满的状态其他容量必须标记为不可达这样方案数才不会凭空多出来。第三段用二维数组而不是滚动数组原因更直接输出方案需要回溯完整的决策路径。滚动数组会把第i件物品处理之前的状态覆盖掉回溯时根本无法判断dp[i][j]是从哪个状态转移过来的。这三个部分独立开来反而比硬凑一个dp更清晰。实际竞赛中时间允许的话我也推荐分三步写一是逻辑好验证二是出错了好定位。5. 实测踩坑记录方案数计数翻倍与INF边界问题这块内容我觉得比原理还重要。能写出上面代码的人不少但能在30分钟内调对的人不多。以下是我自己反复踩过的坑。5.1 坑一把cnt[j] cnt[j-w]放在价值转移外面最经典的错误写法for j in range(V, w - 1, -1): if dp[j - w] v dp[j]: dp[j] dp[j - w] v cnt[j] cnt[j - w]这段代码的问题在于即使新组合的价值低于当前dp[j]它也被算进了方案数。比如容量5那个例子处理到第3件物品(5,7)时j5的新方案价值7和dp[5]相等加一次没问题。但如果换一件物品新方案价值小于当前最优这行cnt[j] cnt[j-w]就会把次优方案错误计入。踩过一次就记住一个原则**方案数只累加在价值等于当前最优的分支上其他情况一律不更新。**价值更新的三条分支大于、等于、小于对应方案数的处理分别是覆盖、累加、不动。5.2 坑二负无穷设得太小导致加法溢出我一开始写NEG -10**18在Python里还好换成C时如果后面加v[i]两个负无穷相加会溢出。更隐蔽的问题是当dp[j-w]是NEG时dp[j-w] v仍然是一个很大的负数如果后续代码只比较大小结果可能还是正确的但一旦有把dp[j]拿去初始化其他地方的逻辑就会出诡异问题。我的建议**转移前先判断dp[j-w]是否等于NEG等于就跳过这次更新。**这比依赖负无穷加正数还是负无穷这个隐式逻辑要安全得多。C选手可以把NEG设为-0x3f3f3f3f这个值比所有合法答案都小而且加上任意v[i]也不会溢出int范围。5.3 坑三统计方案数时漏掉容量小于V的最优状态这是求方案数代码里最容易翻车的地方。跑完所有物品后你可能理所当然地认为最大价值一定在dp[V]于是直接输出cnt[V]。但假如物品总重量小于V或者正好有一件重量为0的物品虽然题目通常排除但有些变种题会出最大价值对应的容量可能是V-2、V-3这样的位置。正确做法是先求max(dp)再遍历所有j把dp[j]max的cnt加起来。这个步骤一分钟就能写完但漏掉它可能让你在某个隐蔽数据上WA到怀疑人生。5.4 坑四打印方案时只判断能不能选而不判断是否最优if j w[i]: chosen.append(i) j - w[i]这样写等于把DP结果全扔了纯靠贪心从前往后选。在01背包里前面能塞下不代表塞进去之后整体还是最优因为后面的组合可能因为容量不足被破坏。正确判断必须是dp[i][j] dp[i1][j-w[i]] v[i]。换句话说你要确信选了这件之后剩余容量下的最优价值仍然接得上才能确定这件在最优路径上。5.5 坑五把01背包的遍历顺序写反求方案数必须倒序遍历j否则同一件物品会被选多次。比如处理物品(2,3)时j从2到V正序遍历计算dp[4]时可能用上刚更新过的dp[2]相当于同一件物品被用了两次。01背包和完全背包的区别其实只在一个遍历顺序上但错误产生的影响会直接传导到方案数的统计里——方案数会变成可以重复选物品的计数大得离谱。调试这类问题有个技巧找一个小数据比如n3, V5把dp数组每一步的更新过程打印出来和手算对照。只要能看出第2次更新依赖了第1次更新的结果就能意识到遍历顺序出了问题。6. 延伸与总结从01背包到其他背包问题的方案问法掌握了01背包求方案数和具体方案后其他背包变种基本可以触类旁通。这里我把常见变种的关键区别列一下方便你以后遇到直接对照。问题类型求方案数的遍历顺序求具体方案的关键01背包倒序从n到1做二维DP输出从1到n完全背包正序可以选的次数不唯一通常有数量限制时才求方案分组背包组内倒序组外按组遍历记录每组的决策输出时先判断选组内哪一件多重背包二进制拆分/单调队列优化后按01背包处理拆分后方案会变复杂一般只求最优价值完全背包求方案数代码几乎一样唯一区别是把内层循环改成for j in range(w, V1)。但有个隐含条件如果物品可以无限取方案数可能是指数级增长记得按题目要求取模。分组背包稍微复杂一点。因为一组内最多选一件状态转移时要在组内做一次选哪一件的决策。求具体方案时输出阶段要额外记录每组的选取情况不能再简单地按单件物品判断。最后说一个通用的方法论。不管是标准01背包还是各种奇奇怪怪的变种凡是求具体方案的题思路都可以归结为两步用DP算出每个状态下的最优价值。从终点倒推或者从起点正推每到一个状态就判断当前这一步是否构成了最优路径上的一环判断方式就是比较状态转移方程两边是否相等。这个思路几乎可以通吃所有DP求方案问题不只是背包。我在做最长上升子序列、编辑距离这些题目时也是用同样的逻辑把具体方案扣出来的。回到开头那个问题。会写状态转移方程只是入门能根据题目要求灵活调整状态定义、遍历方向、统计逻辑才算真正理解背包。方案数考的是一套独立的计数思维具体方案考的是对决策过程的理解两者结合基本就把01背包考透了。这篇文章里所有代码我都实际跑过直接复制到题目里就能用但建议你读完原理之后自己写一遍效果会好得多。要是调试过程中有别的问题欢迎在评论区把我没提到的坑补充进来。