先说明一下背景。01背包做到一定阶段，最让人头疼的不是最大价值怎么算，而是题目突然加一句“输出具体方案”或者“求最优方案数”。很多同学在二维状态能写对、一维滚动也能优化之后，碰到这类问法还是会卡住。原因很简单：求最值只需要把状态值算出来，而求方案需要在状态转移的“决策路径”上做文章，相当于你要从结果反推过程，或者从过程直接记录选择依据。这篇就围绕“求具体方案”和“求方案数”两条线展开，把原理、代码、套路、坑全部说透，顺便把“字典序最小方案”这个高频考点一起拿下。 整个内容偏向实战，我把题目场景设定成最常见的组合形式：给定 n 个物品，每个物品有体积 v[i] 和价值 w[i]，背包容量为 V。目标有三个方向可以考：最大价值是多少、达到最大价值的具体方案是什么、达到最大价值的方案数有多少。有时候三者合在一题里考，理解它们之间的关联就非常重要。 ## 1. 为什么“求具体方案”和“求方案数”不是新算法 ### 1.1 从状态转移反推最优决策 动态规划之所以能做“求具体方案”这个操作，核心原因是：**每个状态的值，都来自一个可回溯的决策**。 拿最经典的二维 01 背包来说，状态定义是 dp[i][j] 表示从前 i 个物品中选择，总体积不超过 j 的最大价值。转移方程很熟悉： ```cpp if (j >= v[i]) { dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]); } else { dp[i][j] = dp[i-1][j]; }这里 dp[i][j] 的来源有两个可能：
- 不选第 i 个物品，值等于 dp[i-1][j]；
- 选第 i 个物品，值等于 dp[i-1][j-v[i]] + w[i]。
当 dp[i][j] 等于后者的值时，说明“选择第 i 个物品”是一个合法的、达到当前状态最优值的决策。倒过来从最后的 dp[n][V] 开始往前看，每一层都能判断当前物品是否被选中。这就是回溯方案的原理。
很多人第一次接触这个概念会觉得抽象，我习惯把它类比成“走地图查轨迹”。动态规划算出的不是一个点，而是一整张状态表，最大值只是终点值。你要找的路径，藏在这张表的每个相等关系里。简而言之，dp 表不丢，方案就有迹可循。
1.2 求方案数本质上是在“维护计数信息”
求方案数也不是新算法，它只是把 dp 数组从“存一个数”变成“存两个数”：一个存最大价值，一个存达到这个最大价值的方案数量。
这有点像在原有 DP 的“决策图”上额外叠加了一层计数逻辑。每当我们发现一个新的决策可以让当前状态价值更大，就把它对应的方案数覆盖过来；如果两个决策价值一样大，就把两个方向的方案数加起来。
所以求方案数这个问题的本质是：在状态转移中同步维护方案总数。它不需要另起炉灶，不需要套新的模板，只需要在原转移方程上做一点扩展。
2. 求具体方案的实现方式与易错点
2.1 最简单可靠的方案：二维 dp 表 + 反向遍历判断
先上最通用的代码。假设物品编号从 1 到 n，v 和 w 数组分别存储体积和价值，V 是背包容量。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; const int MAXV = 1005; int dp[MAXN][MAXV]; int v[MAXN], w[MAXN]; int main() { int n, V; cin >> n >> V; for (int i = 1; i <= n; i++) { cin >> v[i] >> w[i]; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= V; j++) { dp[i][j] = dp[i-1][j]; if (j >= v[i]) { dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]); } } } // 回溯具体方案 int j = V; vector<int> ans; for (int i = n; i >= 1; i--) { if (j >= v[i] && dp[i][j] == dp[i-1][j-v[i]] + w[i]) { ans.push_back(i); j -= v[i]; } } reverse(ans.begin(), ans.end()); cout << "最大价值: " << dp[n][V] << '\n'; cout << "方案: "; for (int id : ans) cout << id << ' '; cout << '\n'; return 0; }这段代码里有一个关键点：回溯时为什么 dp[i][j] == dp[i-1][j-v[i]] + w[i] 就选择第 i 个物品？
因为如果这个等式成立，说明从“前 i-1 个物品、容量 j-v[i]”这个状态再放入第 i 个物品，恰好能得到当前状态的最优值。也就是说，第 i 个物品处于某条最优路径上。选择它，然后把剩余容量减掉，继续往前判断。
这里要注意：回溯时不能只看 dp[i-1][j] 和 dp[i-1][j-v[i]] + w[i] 谁大谁小。因为 dp[i][j] 本身已经包含了最大值信息，你只需要判断当前状态是否等于某个来源，不需要重新求 max。很多同学在这一步又写一遍比较逻辑，结果在多个方案同时最优时选错分支。
如果你只需要任意一组方案，这种写法已经够了。但很多题目会额外要求“字典序最小”，那就要用另一种更讲究的写法。
2.2 字典序最小方案：换个方向做 dp
关于“字典序最小的具体方案”，先明确定义：如果把选出来的物品编号按从小到大排成一列，这个序列字典序最小。
著名的题目如 AcWing 12《背包问题求具体方案》，要求的就是字典序最小方案。这类题目有一个非常经典的处理技巧：把 dp 方向反过来做。
也就是说，让 dp[i][j] 表示从第 i 个物品到第 n 个物品（即物品 i, i+1, ..., n），在容量不超过 j 的情况下能获得的最大价值。转移方程变为：
for (int i = n; i >= 1; i--) { for (int j = 0; j <= V; j++) { dp[i][j] = dp[i+1][j]; if (j >= v[i]) { dp[i][j] = max(dp[i][j], dp[i+1][j-v[i]] + w[i]); } } }构造方案时，从第 1 个物品开始正着判断：
int j = V; vector<int> ans; for (int i = 1; i <= n; i++) { if (j >= v[i] && dp[i][j] == dp[i+1][j-v[i]] + w[i]) { ans.push_back(i); j -= v[i]; } }这样设计的巧妙之处在于：从编号小的物品开始做决策，只要发现“选第 i 个物品也能达到当前最优”，就立刻选它。因为编号越小，选它之后输出的字典序就越小，所以天然得到字典序最小方案。
我最初做这题的时候，第一反应是“先正常 dp，再倒序回溯，最后 reverse”。但这样得到的方案不一定字典序最小。举例说明：如果存在两条最优路径，一条包含物品 1，另一条包含物品 2，从末尾回溯时会优先选编号大的物品，得到的序列反而可能是字典序比较大的那条。所以“求字典序最小”一定要正向决策，也就是反着 dp、正着构造。
很多题解里直接说“倒序枚举物品，能选就选”，其实省略了关键原因：只有当 dp 正着定义从 i 到 n 时，正向构造才能保证选小的编号优先。这点需要自己动手推一遍，印象才深。
2.3 用一维 dp 时，还能回溯方案吗
很多同学习惯用一维滚动数组优化 01 背包，因为代码短、空间省。但到了求具体方案这一步，一维 dp 是没法直接回溯的。
原因很简单：一维滚动数组在更新过程中会把上一层 dp[i-1] 的数据覆盖，你最后拿到的是最后一层的 dp[j]，而回溯时需要的“每个历史状态”已经不存在了。
解决办法有三种：
- 老老实实开二维 dp 表；
- 开一个额外的二维数组 decide[i][j] 记录第 i 个物品在容量 j 时是否被选；
- 先一维求最大价值，再根据物品信息做一次“重新推导”式的构造。
第三种写法比较 tricky：你已经知道了最大价值 maxVal，然后从最后一个物品开始，手动判断如果 j >= v[i] 且 dp[j-v[i]] + w[i] == maxVal，就把当前物品选进方案，同时 j -= v[i]，maxVal -= w[i]。这种做法本质上是在做一次“后验推理”，需要小心 maxVal 的更新。代码虽然可行，但现场容易写乱，不太推荐竞赛时用。
提示：求具体方案时，优先用二维 dp。如果题目空间卡得很死，再考虑二维决策数组，而不是硬用一维滚动。
3. 求方案数的完整推导与代码细节
3.1 扩展状态：用 cnt 数组维护最优方案数
现在把问题升级：不仅求最大价值，还要求达到最大价值的不同方案数目。
需要开两个数组：dp[i][j] 表示最大价值，cnt[i][j] 表示达到该价值的方案数。二者需要同步更新。
初始情况下，dp[0][j] = 0，表示一件物品都不放，容量为 j 时最大价值是 0，方案数为 1（什么都不选）。
转移时分成三种情况：
for (int i = 1; i <= n; i++) { for (int j = 0; j <= V; j++) { dp[i][j] = dp[i-1][j]; cnt[i][j] = cnt[i-1][j]; if (j >= v[i]) { int val = dp[i-1][j-v[i]] + w[i]; if (val > dp[i][j]) { dp[i][j] = val; cnt[i][j] = cnt[i-1][j-v[i]]; } else if (val == dp[i][j]) { cnt[i][j] = (cnt[i][j] + cnt[i-1][j-v[i]]) % MOD; } } } }这里一段段解释：
- 先默认不选第 i 个物品，把上一层的状态和方案数抄下来；
- 如果能选第 i 个物品，就计算选它后的价值 val；
- 如果 val 比当前最优值更大，说明新的最优决策是选它，方案数直接用 cnt[i-1][j-v[i]] 覆盖；
- 如果 val 和当前最优值相等，说明既不选它、选它都能达到最优，则方案数相加。
这段逻辑非常像“在原 dp 转移里做分类讨论”。只要把三种情况分清楚，方案数就能正确维护。
3.2 初始化细节：cnt 数组到底置 0 还是置 1
初始化是求方案数时最容易出错的一环。
一般情况下，我们定义的是“总体积不超过容量 V”的最优方案数。此时 dp[0][j] = 0，cnt[0][j] = 1。为什么？因为前 0 个物品什么都不选，在任意容量 j 下都是一种合法方案，而且最大价值就是 0，所以方案数就是 1。
如果你遇到的是“恰好装满背包”的方案数，那初始化就不同了：只有 dp[0][0] = 0，cnt[0][0] = 1；对于 j > 0，dp 初始化为负无穷，cnt 初始化为 0。这样才能保证“恰好装满”的转移路径不会被“不完整体积”的状态污染。
两种问法在很多教材里都有，务必看清楚题目要求。我之前就因为默认“不超过容量”的初始化，结果做一道“恰好装满”的题，输出方案数直接翻倍，排查了半小时才发现是初始化的问题。
3.3 取模问题与大数据量优化
方案数往往很大，题目一般会给出模数，常见的是 1e9 + 7。取模时要注意：方案数加法时取模，覆盖时不需要取模，但为了统一也可以在最后取。
如果不需要取模，那么可能要用大整数或者 Python 这类高精度语言。C++ 下通常都会有模数，所以不用担心。不过即使有模数，也不能省略判断相等的部分。因为取模后的方案数相加，本质上还是在统计数量。
如果数据范围特别大，二维 cnt 会占用额外空间，可以优化成一维。一维更新时需要注意倒序循环，并且 cnt 数组也要跟着 dp 一起倒序更新：
for (int i = 1; i <= n; i++) { for (int j = V; j >= v[i]; j--) { int val = dp[j-v[i]] + w[i]; if (val > dp[j]) { dp[j] = val; cnt[j] = cnt[j-v[i]]; } else if (val == dp[j]) { cnt[j] = (cnt[j] + cnt[j-v[i]]) % MOD; } } }一维版本看上去简洁，但很容易犯一个错：val 是用这一轮更新过的 dp[j-v[i]] 算出来的，还是上一轮的？由于 j 从大到小循环，j-v[i] 一定小于 j，所以在本轮中还没有被更新，用的还是上一轮的值。这个性质保证了 01 背包一维优化的正确性，cnt 更新同理。理解了这个，一维写起来就不虚。
4. 一道综合例题：把三个问题串起来
4.1 题目与输入
手工构造一道综合题，把“最大价值、具体方案、方案数”一次问完：
有 5 个物品，背包容量为 8。
| 物品编号 | 体积 | 价值 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
| 4 | 5 | 6 |
| 5 | 1 | 2 |
问：最大价值是多少？请输出字典序最小的具体方案。有多少种方案能达到这个最大价值？
4.2 dp 表推演
我们按二维 dp 来计算，并对关键容量状态做记录。
先初始化 dp[0][j] = 0。
处理物品 1（体积 2，价值 3）：
- 容量 j < 2 时为 0；
- j >= 2 时，dp[1][j] = 3。
处理物品 2（体积 3，价值 4）：
- j = 3 时，max(dp[1][3]=3, dp[1][0]+4=4) = 4；
- j = 4 时，max(3, dp[1][1]+4=4) = 4；
- j = 5 及以上时，max(3, dp[1][2]+4=7) = 7。
处理物品 3（体积 4，价值 5）：
- j = 4 时，max(dp[2][4]=4, dp[2][0]+5=5) = 5；
- j = 5 时，max(7, dp[2][1]+5=5) = 7；
- j = 6 时，max(7, dp[2][2]+5=8) = 8；
- j = 7 时，max(7, dp[2][3]+5=9) = 9；
- j = 8 时，max(7, dp[2][4]+5=9) = 9。
处理物品 4（体积 5，价值 6）：
- j = 5 时，max(7, dp[3][0]+6=6) = 7；
- j = 6 时，max(8, dp[3][1]+6=6) = 8；
- j = 7 时，max(9, dp[3][2]+6=9) = 9；
- j = 8 时，max(9, dp[3][3]+6=10) = 10。
处理物品 5（体积 1，价值 2）：
- j = 3 时，max(dp[4][3]=4, dp[4][2]+2=5) = 5；
- j = 4 时，max(5, dp[4][3]+2=6) = 6；
- j = 5 时，max(7, dp[4][4]+2=7) = 7；
- j = 6 时，max(8, dp[4][5]+2=9) = 9；
- j = 7 时，max(9, dp[4][6]+2=10) = 10；
- j = 8 时，max(10, dp[4][7]+2=11) = 11。
所以最大价值是 11，dp[5][8] = 11。
4.3 字典序最小方案构造
按照前面说的反向 dp 正向构造，我们其实可以直接用正向定义来推导。但为了直观展示两种思路，这里采用“正向构造”的判断方式。
已知 dp[5][8] = 11，从物品 5 往前判断是否能通过与物品 5 相关的转移得到：
对于物品 5（体积 1，价值 2），dp[5][8] == dp[4][7] + 2 = 9 + 2 = 11，说明物品 5 在最优路径上。选择物品 5，剩余容量变为 7。
对于物品 4（体积 5，价值 6），dp[4][7] == dp[3][2] + 6 = 3 + 6 = 9，说明物品 4 也在某条最优路径上；同时 dp[4][7] == dp[3][7] = 9，说明不选它也成立。如果要求字典序最小，我们应该优先选编号更小的物品。但这里是倒着判断，选物品 4 会得到更小还是更大的字典序，需要进一步看后续选择。继续推导看结果。
如果选择物品 4，剩余容量变为 2，此时只能再选物品 1，方案为 {1, 4, 5}。
如果不选物品 4，继续看物品 3（体积 4，价值 5）。dp[3][7] == dp[2][3] + 5 = 4 + 5 = 9，可以选物品 3，剩余容量变为 3；再选物品 2，剩余容量变为 0，方案为 {2, 3, 5}。
两个方案价值都是 11。比较 {1,4,5} 和 {2,3,5} 的字典序，因为 1 < 2，所以字典序最小方案是 {1, 4, 5}。
这里也验证了前面说的：倒序 dp、正着判断会自然得到字典序最小方案；从后往前回溯时，要额外判断并比较才能得到最小值。实际写代码时用正向构造最安全。
4.4 方案数统计
根据转移过程中的分类讨论，容量 8 对应两个方向都能达到最优，所以方案数为 2。稍后再把这个结论对应到代码里去，就非常清晰了。
此题虽然简单，但把“最值、方案、方案数”三个层次都包含了。做通这一道，01 背包变式的基本功就差不多了。
5. 常见问题与排查技巧实录
5.1 为什么回溯出来不是最优方案
最常见的症状是：最大值算对了，但回溯出的物品总价值小于最大值。这通常是因为你在回溯时用了滚动数组后的 dp[j]，而不是二维的 dp[i][j]。
另一个原因是没有判断 j >= v[i] 就直接比较，导致数组越界或者访问到错误状态。回溯时的循环一定要先检查剩余容量是否足够，再判断相等关系。
建议排查时写一段测试：输出选中的物品编号、体积之和、价值之和，和价值表里的 dp[n][V] 对比。如果不等，基本就是回溯状态用错了。
5.2 方案数为什么会算多
方案数算多，通常是初始化问题。如果你把 cnt[0][j] 全部初始化为 1，但在“恰好装满”的题目里，j > 0 时应该是 0；反过来，如果题目只是“不超过容量”，你却用“恰好装满”的负无穷初始化，方案数会偏少。
还有一种情况：在转移时，把“可选可不选”当成了两个完全独立的方案，但实际上它们可能重合。比如一个物品体积为 0 时，选和不选在编号序列上是两种不同的方案，此时确实应该分别计数；一旦体积不为 0，只要状态来源不同，就可以放心相加，不会重复。
5.3 输出方案时物品顺序反了
很多题目要求输出的方案是按编号从小到大排列。反向回溯后需要 reverse 一次。如果要求字典序最小，更推荐直接反着 dp、正着构造，这样不需要 reverse，也不容易出现顺序错误。
5.4 多组最优方案如何输出全部方案
如果题目要求输出所有最优方案，而不是只输出一个，就需要写成递归回溯了。用 DFS 从 dp[n][V] 开始，对每一件物品分“选”与“不选”两条路走，剪枝条件就是 dp[i][j] 必须等于对应来源的值。这里不再展开，但思路是从“找一个方案”变成“找所有方案”，状态多的时候会非常耗时，要谨慎使用。
6. 思维层面做个收束
把求具体方案、求方案数这两个问题放在一起看，会发现它们的底层逻辑高度一致：动态规划不只是算一个答案，它更是在记录所有决策路径的权重关系。求最值是顺着转移方向往前推，求具体方案是逆着转移方向找路径，求方案数则是在转移过程中维护路径的条数。
掌握了这个视角，01 背包就从一个“模板”变成了一套“工具”。看到新题时，先想清楚题目问的是值、路径还是路径数量，然后再决定要不要保存二维表、要不要加 cnt 数组、要不要反向 dp。思路清晰了，代码自然不容易写错。
我在实际做题的过程中，最大的体会是：不要嫌二维 dp 浪费空间而一上来就写一维优化。求具体方案和求方案数这类题，二维表本身就是最直观的资料，等你完全理解了再根据题目要求去优化，效率会高很多。
最后分享一个小技巧：做这类综合题时，建议先把小数据样例的 dp 表用手算填一遍，肉眼看到最优路径和方案数量，再去套代码。手推一遍比敲十遍代码都管用，很多“灵光一现”的解法都是从表里看出来的。后面遇到“求具体方案”的变体题，不妨也先填表找规律，再动手写转移方程。
