企业官网建设流程全解析

说实话，背包问题在动态规划里算是“入门容易进阶难”的典型代表。很多人能把 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[i+1][j]; if (j >= w[i]) { dp[i][j] = max(dp[i][j], dp[i+1][j - w[i]] + v[i]); } } }

这样填完表之后，dp[1][V]就是整个问题的最大价值。接下来我们从i = 1, j = V开始正向判断：

• 如果dp[i][j] == dp[i+1][j - w[i]] + v[i]成立，说明选第 i 个物品可以达到最优，那么选它。
• 否则不选，继续看下一个物品。

关键点在于：判断时优先往“选”的方向靠，这样天然就得到了字典序最小的方案。因为从编号小的物品开始决策，能选就选，结果一定是字典序最小的。

这个方法之所以优于路线一，就是因为它避免了“回溯时在相等分支里选谁”的麻烦，直接用正向贪心锁定了字典序最小的分支。

2.3 一个必考的变形：字典序最小方案

很多题目会在“求具体方案”后面加一个限定条件：“输出字典序最小的方案”。这个限制一加，很多人的代码就挂了。

原因在于：如果你用正向DP然后回溯，当“选或不选价值一样”时，你从终点往前回溯时，先遇到编号大的物品。如果你在相等时优先判断“没选”，那么编号大的物品会被跳过，这反而可能是字典序更大的方案。因为你想要的是编号小的尽量选，而不是编号大的尽量不选。

解决办法有两条：

1. 修正向回溯：在终点的判断里，如果选和不选价值相同，优先判定为“选了”。虽然这听起来简单，但容易出bug，因为终点处你没法直接知道这条路是否真的能走到起点。
2. 用逆向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[i+1][j]; if (j >= w[i]) { dp[i][j] = max(dp[i][j], dp[i+1][j - w[i]] + v[i]); } } } // 正向贪心求字典序最小方案 int j = V; for (int i = 1; i <= N; i++) { if (j >= w[i] && dp[i][j] == dp[i+1][j - w[i]] + v[i]) { cout << i << " "; j -= w[i]; } } cout << endl; return 0; }

这里最关键的一行是if (j >= w[i] && dp[i][j] == dp[i+1][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]（j>0）都是0，因为无法凑出正容量。

3.2 滚动数组与方案数的隐蔽陷阱

很多人会想到用一维滚动数组优化空间，但方案数问题有个隐蔽陷阱：如果你把二维压缩成一维，需要确保枚举容量时是倒序的，否则一个物品会被重复使用多次，方案数就会偏大。

vector<int> 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 1e9+7，那就在加法时取模。但要注意，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 的方案数，并对 1e9+7 取模：

#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; int main() { int N, V; cin >> N >> V; vector<int> w(N + 1); for (int i = 1; i <= N; i++) cin >> w[i]; vector<long 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：一遍求最优价值，一遍在“只保留达到最优价值的转移路径”上求方案数。

具体思路是：

1. 用普通01背包 DP 求出dp_max[i][j]，得到最大价值。
2. 用第二张表dp_cnt[i][j]记录达到dp_max[i][j]这个最优价值的方案数。
3. 在回溯具体方案时，依然用字典序贪心。

第二张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。要求：先输出最大价值，再输出达到该价值的方案数，最后输出其中字典序最小的选物品方案。

这个问题把前面所有知识点全部串起来了。我的实现思路是：

1. 用逆向DP（从 N 到 1）计算dp[i][j]，并获得最大价值。
2. 同时用cnt[i][j]记录达到这个价值的方案数。
3. 正向从 i=1 开始扫描，如果能选就选，得到字典序最小的具体方案。

代码结构大致如下：

#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[i+1][j]; if (j >= w[i]) { dp[i][j] = max(dp[i][j], dp[i+1][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) 在 N<=1000、V<=1000 时完全没有压力。如果题目的 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输出的方案对拍。对于 N<=20 的数据，暴力是完全可行的。对拍几次之后，哪个分支选择逻辑有问题就一目了然。

下面是一个 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 1e9+7，那么加法过程中每个中间结果都要取模。需要注意的是，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写一个能跑出方案的版本，再根据题目要求判断是否需要改成字典序版本。先保证正确，再优化是最稳妥的策略。

我在实际刷题过程中养成了一个习惯：每做完一道背包题，都主动问自己一句“如果题目改成求方案数/求具体方案/求字典序最小方案，我要改哪几行代码？”用这种方式训练下来，你对背包问题的理解会非常深刻。