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] = 0，cnt[0] = 1。容量0恰好装满，只有"什么都不选"这一种方案。其余dp[j] = 负无穷，cnt[j] = 0。
转移时，对第i件物品（重量w，价值v），倒序遍历j：
if 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)，容量V=5。
处理第1件物品(2,3)后：dp[2]=3，cnt[2]=1。 处理第2件物品(3,4)后：dp[3]=4（cnt[3]=1），dp[5]=7（cnt[5]=1，即第1件+第2件）。 处理第3件物品(5,7)后：dp[5]本来已经是7，新方案"单独选第3件"价值也是7，于是cnt[5]从1变成2。
最终max_val=7，满足dp[j]==7的只有j=5，答案为cnt[5]=2。和心算结果一致。
注意一个细节：必须用倒序遍历j，保证每件物品只被选一次。如果你在这里写成正序遍历，就变成完全背包了，方案数会严重偏大，这属于经典错误，后面我会专门讲。
3. 具体方案：为什么必须换一个方向做DP
求方案数只需要数字，但求具体方案需要把"选了哪几件"完整还原出来。这件事如果用一维滚动数组做，基本无解——滚动数组的目的是覆盖状态，节省空间，但也把决策路径抹掉了。
3.1 先看错误思路：正向做完再逆推
有些同学会想：我用二维dp[i][j]跑完，然后从i=n往前倒推，如果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}两个。从i=3往前推，发现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≤1000，V≤1000，w[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)时，j=5的新方案价值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[i+1][j-w[i]] + v[i]。换句话说，你要确信"选了这件之后，剩余容量下的最优价值仍然接得上"，才能确定这件在最优路径上。
5.5 坑五：把01背包的遍历顺序写反
求方案数必须倒序遍历j，否则同一件物品会被选多次。比如处理物品(2,3)时，j从2到V正序遍历，计算dp[4]时可能用上刚更新过的dp[2]，相当于同一件物品被用了两次。01背包和完全背包的区别，其实只在一个遍历顺序上，但错误产生的影响会直接传导到方案数的统计里——方案数会变成"可以重复选物品"的计数，大得离谱。
调试这类问题有个技巧：找一个小数据，比如n=3, V=5，把dp数组每一步的更新过程打印出来，和手算对照。只要能看出"第2次更新依赖了第1次更新的结果"，就能意识到遍历顺序出了问题。
6. 延伸与总结：从01背包到其他背包问题的方案问法
掌握了01背包求方案数和具体方案后，其他背包变种基本可以触类旁通。这里我把常见变种的关键区别列一下，方便你以后遇到直接对照。
| 问题类型 | 求方案数的遍历顺序 | 求具体方案的关键 |
|---|---|---|
| 01背包 | 倒序 | 从n到1做二维DP，输出从1到n |
| 完全背包 | 正序 | 可以选的次数不唯一，通常有数量限制时才求方案 |
| 分组背包 | 组内倒序，组外按组遍历 | 记录每组的决策，输出时先判断选组内哪一件 |
| 多重背包 | 二进制拆分/单调队列优化后按01背包处理 | 拆分后方案会变复杂，一般只求最优价值 |
完全背包求方案数，代码几乎一样，唯一区别是把内层循环改成for j in range(w, V+1)。但有个隐含条件：如果物品可以无限取，方案数可能是指数级增长，记得按题目要求取模。
分组背包稍微复杂一点。因为一组内最多选一件，状态转移时要在组内做一次"选哪一件"的决策。求具体方案时，输出阶段要额外记录每组的选取情况，不能再简单地按单件物品判断。
最后说一个通用的方法论。不管是标准01背包，还是各种奇奇怪怪的变种，凡是"求具体方案"的题，思路都可以归结为两步：
- 用DP算出每个状态下的最优价值。
- 从终点倒推（或者从起点正推），每到一个状态就判断"当前这一步是否构成了最优路径上的一环"，判断方式就是比较状态转移方程两边是否相等。
这个思路几乎可以通吃所有DP求方案问题，不只是背包。我在做最长上升子序列、编辑距离这些题目时，也是用同样的逻辑把具体方案扣出来的。
回到开头那个问题。会写状态转移方程只是入门，能根据题目要求灵活调整状态定义、遍历方向、统计逻辑，才算真正理解背包。方案数考的是一套独立的计数思维，具体方案考的是对决策过程的理解，两者结合，基本就把01背包考透了。这篇文章里所有代码我都实际跑过，直接复制到题目里就能用，但建议你读完原理之后自己写一遍，效果会好得多。要是调试过程中有别的问题，欢迎在评论区把我没提到的坑补充进来。
