说实话背包问题在动态规划里算是“入门容易进阶难”的典型代表。很多人能把 01背包 的最大价值写出来但一旦碰上“请输出具体选了哪些物品”或者“一共有多少种选法能凑出这个价值”立马就卡住了。这个标题把三个知识点串在一起——01背包基础、求方案数、求具体方案——正好是算法题里从“会做”到“能做对”的分水岭。这篇文章我不打算只贴代码而是把每一步的推导逻辑、为什么要这么做、以及我在实际刷题和笔面试里踩过的坑全部讲清楚。无论你是刚学会滚动数组的新手还是准备冲击大厂笔试的选手这篇都能给你一些值得反复看的东西。1. 从0到1重排01背包核心思想1.1 为什么先要重新理解“状态定义”很多人学01背包的时候状态定义是背下来的dp[i][j]表示前 i 个物品中容量恰好为 j 或不超过 j 时的最大价值。但到了求方案数和求具体方案时这个“恰好”和“不超过”的区别会直接决定你后面代码怎么写。我倾向于把01背包理解为一种“决策过程”。每个物品只有两种状态拿或者不拿。这本质上是一个子集选择问题只不过我们要求在容量限制下使总价值最大。递推公式是dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])这里左边是不拿第 i 个物品右边是拿。注意右边成立的前提是 j w[i]也就是当前容量能装下这个物品。很多初学者在这里漏掉边界判断导致数组越界或者答案是错的。在实际面试里我见过的考题几乎不会直接问你“最大价值是多少”而是喜欢加一层包装比如“凑出这个价值需要选哪几个物品”或者“有多少种选法能达到最优价值”。这些变体都是在基础递推之上加一个“记忆”或者“计数”的维度。1.2 “最大价值”和“选的方案”为什么不是一件事这里必须强调一个新手经常混淆的概念最大价值只是一个数而方案是“从 N 个物品中挑出一个子集这个子集的总价值等于最大价值且总重量不超过容量”。前者是数值目标后者是构造目标。打个比方你有一堆水果要选出总重量不超过 10kg、总热量最大的一组。最大热量值你可以靠递推算出来但如果面试官让你说出“你具体选的是苹果还是香蕉”你就需要额外记录“这个最优值是从哪个状态转移过来的”。这就是求具体方案的核心思路在 DP 表里不仅要记录最优值还要记录“当前这一格的最优值是谁传给它的”。这就像你沿着一条河流回溯每一段都清楚知道自己是从哪个支流流过来的最后就能从终点逆着走回起点。理解了这一点我们下面就能自然引出两条求方案的技术路线。2. 求具体方案的两条经典路线2.1 路线一正向DP后从终点反向贪心回溯这是最直觉化的做法先跑一遍正常的01背包填出dp[i][j]表然后从i N, j V开始往回看判断第 i 个物品到底选没选。判断条件很简单if (dp[i][j] dp[i-1][j]) { // 说明第 i 个物品没拿因为不拿它也能得到同样的价值 } else { // 说明第 i 个物品拿了j 减去 w[i]并记录这个物品 }不过这里有个细节如果dp[i][j] dp[i-1][j]且dp[i][j] dp[i-1][j-w[i]] v[i]同时成立说明选或不选价值一样。这时候你选择“不选”还是“选”会影响最终输出的方案。如果题目要求“输出字典序最小的方案”这里就不能简单地说“不选”了需要结合字典序要求反过来处理。这个坑我后面专门讲。2.2 路线二逆向DP然后从起点正向贪心这条路线的原理和路线一完全对称但在处理字典序时极其好用。做法是定义dp[i][j]为从第 i 个物品到第 N 个物品中任意选取若干个物品放入容量为 j 的背包中能获得的最大价值。递推方向是从后往前for (int i N; i 1; i--) { for (int j 0; j V; j) { dp[i][j] dp[i1][j]; if (j w[i]) { dp[i][j] max(dp[i][j], dp[i1][j - w[i]] v[i]); } } }这样填完表之后dp[1][V]就是整个问题的最大价值。接下来我们从i 1, j V开始正向判断如果dp[i][j] dp[i1][j - w[i]] v[i]成立说明选第 i 个物品可以达到最优那么选它。否则不选继续看下一个物品。关键点在于判断时优先往“选”的方向靠这样天然就得到了字典序最小的方案。因为从编号小的物品开始决策能选就选结果一定是字典序最小的。这个方法之所以优于路线一就是因为它避免了“回溯时在相等分支里选谁”的麻烦直接用正向贪心锁定了字典序最小的分支。2.3 一个必考的变形字典序最小方案很多题目会在“求具体方案”后面加一个限定条件“输出字典序最小的方案”。这个限制一加很多人的代码就挂了。原因在于如果你用正向DP然后回溯当“选或不选价值一样”时你从终点往前回溯时先遇到编号大的物品。如果你在相等时优先判断“没选”那么编号大的物品会被跳过这反而可能是字典序更大的方案。因为你想要的是编号小的尽量选而不是编号大的尽量不选。解决办法有两条修正向回溯在终点的判断里如果选和不选价值相同优先判定为“选了”。虽然这听起来简单但容易出bug因为终点处你没法直接知道这条路是否真的能走到起点。用逆向DP正向贪心因为决策顺序是从编号1到N每次判断都是“能选就选”天然满足字典序最小。我在实际比赛中几乎无脑用第二种因为代码逻辑更直观也不容易在边界条件上翻车。下面给一个完整的 C 实现用于输出字典序最小的具体方案逆向DP法#include bits/stdc.h using namespace std; const int MAXN 1005; int w[MAXN], v[MAXN]; int dp[MAXN][MAXN]; // dp[i][j] 表示从 i 到 N 中选容量不超过 j 的最大价值 int main() { int N, V; cin N V; for (int i 1; i N; i) { cin w[i] v[i]; } // 逆向DP for (int i N; i 1; i--) { for (int j 0; j V; j) { dp[i][j] dp[i1][j]; if (j w[i]) { dp[i][j] max(dp[i][j], dp[i1][j - w[i]] v[i]); } } } // 正向贪心求字典序最小方案 int j V; for (int i 1; i N; i) { if (j w[i] dp[i][j] dp[i1][j - w[i]] v[i]) { cout i ; j - w[i]; } } cout endl; return 0; }这里最关键的一行是if (j w[i] dp[i][j] dp[i1][j - w[i]] v[i])。它判断的是当前状态下如果选第 i 个物品剩下的容量j - w[i]还能不能由后面的物品组合出和dp[i][j]匹配的最优价值。如果能就选。因为是从1到N正向扫描所以选出来的编号序列就是字典序最小的。3. 求方案数从“最优值”到“有多少种方法”3.1 计数DP的底层逻辑加法原理与不重不漏求方案数和求最优值是两种不同的DP思维。最优值关心的是“最大能够达到多少”方案数关心的是“有多少种不同的选法能够达到某个状态”。前者的转移用max后者的转移用。01背包方案数的经典状态定义是dp[i][j]表示前 i 个物品中恰好凑出容量 j 的选法数量。转移方程dp[i][j] dp[i-1][j] (j w[i] ? dp[i-1][j - w[i]] : 0)理解起来并不难不拿第 i 个物品那方案数就等于前 i-1 个物品凑出 j 的方案数拿第 i 个物品那就等于前 i-1 个物品凑出 j - w[i] 的方案数。两种情况互不重叠加起来就是当前状态的方案数。初始化是dp[0][0] 1表示“一个都不选容量0正好有一种方案”。其他dp[0][j]j0都是0因为无法凑出正容量。3.2 滚动数组与方案数的隐蔽陷阱很多人会想到用一维滚动数组优化空间但方案数问题有个隐蔽陷阱如果你把二维压缩成一维需要确保枚举容量时是倒序的否则一个物品会被重复使用多次方案数就会偏大。vectorint dp(V 1, 0); dp[0] 1; for (int i 1; i N; i) { for (int j V; j w[i]; j--) { dp[j] dp[j - w[i]]; } }这里dp[j]更新时用的是上一轮前 i-1 个物品的dp[j - w[i]]倒序保证dp[j - w[i]]还没有被当前物品污染。这个道理和求最大价值的滚动数组完全一样但很多初学者在求方案数时会忘记因为加法不像 max 那样“看起来”容易出错。如果你要用模数取模比如题目说答案很大需要 mod 1e97那就在加法时取模。但要注意dp[j] dp[j - w[i]]后可能超过 int 范围建议用 long long 存储最后再取模或者转 int。3.3 从“任意容量”到“恰好容量”的边界处理方案数题还有一个常见坑题目问“你最多能凑出多少种不超过容量 V 的方案”和“恰好凑出容量 V 的方案”是两回事。如果是前者你可以在二维状态里定义成“容量不超过 j 的方案数”或者更简单地对所有dp[i][j]求前缀和如果是后者那么就是上面说的“恰好”定义dp[N][V]就是答案。这两个定义的区别和开头提到的1.1节相呼应。在面试中我习惯先和面试官确认题目里的“方案数”到底要求的是恰好等于容量 V还是不超过 V。这个确认能避免你写出一个逻辑自洽但答案完全错误的代码。下面给一个完整的 C 示例求恰好装满容量 V 的方案数并对 1e97 取模#include bits/stdc.h using namespace std; const int MOD 1e9 7; int main() { int N, V; cin N V; vectorint w(N 1); for (int i 1; i N; i) cin w[i]; vectorlong long dp(V 1, 0); dp[0] 1; for (int i 1; i N; i) { for (int j V; j w[i]; j--) { dp[j] (dp[j] dp[j - w[i]]) % MOD; } } cout dp[V] endl; return 0; }4. 双重要求既求方案数又求具体方案4.1 同时维护两张表有些题会这样出先问有多少种方案能达到最大价值再让你输出其中字典序最小的具体方案。这种题看似吓人但本质上就是把前面两个问题合并成两遍DP一遍求最优价值一遍在“只保留达到最优价值的转移路径”上求方案数。具体思路是用普通01背包 DP 求出dp_max[i][j]得到最大价值。用第二张表dp_cnt[i][j]记录达到dp_max[i][j]这个最优价值的方案数。在回溯具体方案时依然用字典序贪心。第二张dp_cnt的转移需要和第一张配合。对于每个状态 (i, j)比较从上一个状态转移过来的两个候选值int cand1 dp_max[i-1][j]; // 不选第 i 个 int cand2 dp_max[i-1][j - w[i]] v[i]; // 选第 i 个 if (cand1 cand2) { dp_max[i][j] cand1; dp_cnt[i][j] dp_cnt[i-1][j]; } else if (cand1 cand2) { dp_max[i][j] cand2; dp_cnt[i][j] dp_cnt[i-1][j - w[i]]; } else { dp_max[i][j] cand1; // 两者相等 dp_cnt[i][j] (dp_cnt[i-1][j] dp_cnt[i-1][j - w[i]]) % MOD; }注意这里的坑当两个候选值相等时方案数要相加因为两条路径都能达到同样价值。如果你只是简单地把dp_cnt继承其中一个答案就会少算。4.2 求方案数的“防重”思维求方案数最忌讳的是重复计数。我见过很多人写的代码在普通状态下跑出的数字偏大就是因为没有想清楚“两个不同的选择序列但物品集合一样”这种情况。01背包中物品的编号是固定的每个物品只能选一次所以“选法”本质上就是一个子集。两个不同的子集只要包含的物品不同就算不同方案只要物品集合相同哪怕选择的顺序不同也是同一种方案。而01背包的DP天然就是以“物品编号从1到N依次决策”的方式进行的不会产生顺序导致的重复所以直接累加就是正确的。但如果你把物品循环放在内层或者用多层循环模拟完全背包就可能出现同一个子集被统计多次的情况。因此写代码时永远记住外层循环物品内层循环容量这样才能保证每个子集只会被一个特定顺序枚举到。4.3 完整例题带字典序约束的方案数假设一个场景有 N 个物品第 i 个物品重量为 w[i]价值为 v[i]背包容量为 V。要求先输出最大价值再输出达到该价值的方案数最后输出其中字典序最小的选物品方案。这个问题把前面所有知识点全部串起来了。我的实现思路是用逆向DP从 N 到 1计算dp[i][j]并获得最大价值。同时用cnt[i][j]记录达到这个价值的方案数。正向从 i1 开始扫描如果能选就选得到字典序最小的具体方案。代码结构大致如下#include bits/stdc.h using namespace std; const int MOD 1e9 7; const int MAXN 1005; int w[MAXN], v[MAXN]; int dp[MAXN][MAXN]; long long cnt[MAXN][MAXN]; int main() { int N, V; cin N V; for (int i 1; i N; i) cin w[i] v[i]; // 逆向DP求最大价值 for (int i N; i 1; i--) { for (int j 0; j V; j) { dp[i][j] dp[i1][j]; if (j w[i]) { dp[i][j] max(dp[i][j], dp[i1][j - w[i]] v[i]); } } } // 正向DP求方案数需要和最大价值对应 cnt[0][0] 1; for (int i 1; i N; i) { for (int j 0; j V; j) { if (dp[1][V] dp[i][j]) { // 只统计最优路径上的状态 cnt[i][j] ... } } } // 实际写起来比这个复杂需要对每个状态单独判断从哪个转移而来 // 我建议直接用记忆化搜索每到一个状态判断两个转移哪个等于当前 dp 值 // 这样逻辑最清晰也最好debug }说实话同时维护两张表并且保证路径正确直接用DP写容易乱。我自己更推荐用记忆化搜索从(1, V)出发每次判定两个转移是否与当前最优值相等相等就累加对应子状态的方案数。这样代码量反而更少逻辑也更清晰。5. 常见问题与排查技巧实录5.1 滚动数组写完后输出发现方案和期望不符我在一开始学回溯方案时总是想当然地把二维DP压缩成一维然后发现回溯时根本拿不到之前的状态。因为一维数组只保留最后一轮的结果中间任何时刻的容量值都被覆盖掉了。解决办法求具体方案时不要用滚动数组老老实实用二维。空间复杂度 O(N*V) 在 N1000、V1000 时完全没有压力。如果题目的 N 是 1e5 级别那通常不会要求输出具体方案因为方案本身可能有 O(N) 个输出量就很大如果仍然要求那就得考虑用路径压缩或者特殊的数据结构但这种情况很少见。5.2 求方案数时答案比预期小这个问题十有八九出在初始化上。dp[0][0] 1很多人会漏写或者写成dp[0][0] 0那整个递推结果就变成0了。另外如果你用“不超过容量 V”的前缀和方法要特别注意最后答案是sum(dp[N][j])而不是单个dp[N][V]。这里也是最容易踩的边界坑。5.3 字典序输出怎么调都不对遇到这种情况先停下来画一个小例子比如3个物品容量5自己手写一遍DP表然后追踪回溯过程。我敢说90%的字典序问题靠画表都能解决不要硬调试代码。我常用的一个方法用 Python 写一个暴力枚举所有子集的脚本和DP输出的方案对拍。对于 N20 的数据暴力是完全可行的。对拍几次之后哪个分支选择逻辑有问题就一目了然。下面是一个 Python 对拍脚本的简化版适合用来验证字典序方案import itertools def brute_force(N, V, w, v): best_val 0 best_mask 0 for mask in range(1 N): total_w 0 total_v 0 for i in range(N): if mask i 1: total_w w[i] total_v v[i] if total_w V: if total_v best_val or (total_v best_val and is_lex_smaller(mask, best_mask, N)): best_val total_v best_mask mask return best_val, best_mask def is_lex_smaller(a, b, N): # 输出时按编号升序比较第一个不同位置 for i in range(N): ba (a i) 1 bb (b i) 1 if ba ! bb: return ba bb # 编号小的优先选所以a中该位为1更好 return False这个脚本虽然效率低但在小数据上调错已经足够。5.4 方案数过大数据溢出的判定如果题目要求 mod 1e97那么加法过程中每个中间结果都要取模。需要注意的是dp[j] (dp[j] dp[j - w[i]]) % MOD一定要在每次加上去后立即取模不要在最后统一取模。因为中间结果可能已经超过 long long 范围。另外cnt[i][j]和dp_max[i][j]两张表如果都用 long long空间可能翻倍对于 1005*1005 的规模问题不大但如果 N 和 V 都到 5000那就要考虑一下内存是否足够必要时换用 int 配合const int MOD处理。6. 思维拓展从“求方案”到“决策还原”6.1 动态规划的本质是“记录决策过程”很多人学动态规划只关注状态和转移却忽略了 DP 表本身是一个完整的“决策记录”。当你需要回答案子集、方案数、具体路径时本质上是在问这个最优结果是如何一步步形成的这让我想到一个类比动态规划就像在一座迷宫里走你知道每一步选哪条路能让你离出口最近但如果你不记住自己走过的路走到终点后你是无法原路返回的。而“求具体方案”就是要求你反推出这一整条路线。所以我在做题时一定会问自己一个问题“如果我要把决策过程还原出来需要哪些信息”答案往往是两种要么多开一张“转移来源表”要么把 DP 顺序设计成可以直接判断流向的形式。6.2 同类型扩展多重背包与完全背包的求方案掌握了01背包求方案数之后完全背包和多重背包的求方案数几乎可以顺势推出来。完全背包因为每个物品可以无限取内层循环改成从小到大多重背包可以用二进制拆分后当成01背包处理。但求具体方案的方向略有不同完全背包回溯时你可能需要递归地判断“当前物品还能不能再拿一次”所以回溯的条件要写成 while 循环。这一点和01背包是一次性判断、拿完就跳到下一个物品不太一样。学有余力的读者可以尝试自己推导一下如果题目改成“每种物品有无限件求凑出容量 V 的方案数”为什么内层循环改为正序就是对的想清楚了你对背包的理解就真的上一个台阶。6.3 什么时候用“正向思维”什么时候用“逆向思维”正向 DP 求价值、逆向 DP 还原方案这是很多参考书里的经典搭配。但我个人的体会是如果题目不仅要求输出方案还要求字典序最小那就不要犹豫直接用逆向DP正向贪心。这条路最省心。如果只是要求输出任意一个方案那正向DP回溯也完全够用。我在笔试中经常先用正向DP写一个能跑出方案的版本再根据题目要求判断是否需要改成字典序版本。先保证正确再优化是最稳妥的策略。我在实际刷题过程中养成了一个习惯每做完一道背包题都主动问自己一句“如果题目改成求方案数/求具体方案/求字典序最小方案我要改哪几行代码”用这种方式训练下来你对背包问题的理解会非常深刻。