企业官网建设流程全解析

1. 先从选与不选开始：为什么暴力枚举走不通

我在面试候选人和带新人的时候，发现一个很有意思的现象：很多人谈起动态规划就头皮发麻，觉得这是一道跨不过去的坎。但如果你把“01背包问题”这五个字拆开，其实它描述的场景特别朴素——你面前有 N 件物品，每件有自己的重量 w[i] 和价值 v[i]，你手里有一个容量为 W 的背包，每件物品只能选择装或者不装（这就是“01”的由来：0 代表不装，1 代表装），目标是让背包里装下的总价值最大。

就这么个问题，看上去毫无技术含量。但为什么它能成为算法领域的“钉子户”，反复出现在笔试、面试、竞赛和各种教程里？因为它的解法背后藏着动态规划最核心的思想：把一个大问题拆成互相重叠的子问题，用空间换时间。

先说说为什么暴力枚举走不通。最直观的想法是：一共有 N 件物品，每件物品有“选”和“不选”两种状态，那么所有组合方案就是 2^N 种。你需要遍历这些方案，然后去重、筛选出重量不超过 W 的，再找最大价值。听着好像可行，但 N=20 的时候是 104 万种，N=30 就是 10 亿种，N=50 直接奔着千万亿去了。就算你的计算机每秒能跑一亿次，N=50 也要跑到宇宙热寂。所以暴力法只适合 N≤20 左右的场景，稍微上点规模就直接死给你看。

那怎么优化？关键就在“重复”这两个字上。你可以想一想：当我依次决定要不要装第 i 件物品时，前面已经决策完的物品会形成一个状态——当前的剩余容量和累计价值。不同的决策路径，可能会在某个时刻落入完全相同的状态：同样还剩 10kg 容量，同样已经装了价值 500 的东西。既然状态相同，后面还能装的物品也一样，那么从这两个状态继续走，最优结果必然也相同。于是我们只需要为每一个“剩余容量 + 已决策物品数”组合保留一个最优价值就够了，根本不需要枚举完整路径。

这就是 01 背包问题最底层的直觉：用“决策到第几件物品 + 当前背包容量的剩余量”来定义状态，把指数级的可能性压缩成 N×(W+1) 个格子。压缩的背后不是魔法，是因为我们砍掉了一模一样的大量冗余分支。想通了这一点，后面所有状态转移方程、滚动数组、空间优化，都是水到渠成的事。

2. 一张表推到底：手把手构建二维DP状态

2.1 状态定义和转移方程的直觉来源

我们先约定符号。假设有 N 件物品，物品编号从 1 到 N，第 i 件物品的重量是 w[i]，价值是 v[i]。背包容量为 W。令 dp[i][j] 表示“只从前 i 件物品里挑，放入容量为 j 的背包，能获得的最大价值”。

这里有几个细节需要解释清楚，因为很多初学者第一次看到 dp[i][j] 都会困惑：为什么第二维是背包容量 j，而不是剩余容量？其实两者本质等价，但“容量为 j”的表达更利于递推。你再想深一层：dp[i][j] 对应的那个书包，里面装的物品全部来自前 i 件，且它们的总重量不超过 j。

接下来是状态转移。站在第 i 件物品面前，只有两个选择：

• 不装第 i 件物品：那么前 i 件物品能获得的最大价值就等于前 i-1 件物品在同样容量 j 下的最优值，即 dp[i][j] = dp[i-1][j]。意思就是“这件东西我不要了，继承之前的最好结果”。
• 装第 i 件物品：前提是当前背包容量 j 装得下 w[i]，也就是 j ≥ w[i]。如果装，那么前 i-1 件物品只能使用剩余容量 j - w[i]，然后再加上第 i 件物品的价值 v[i]，即 dp[i][j] = dp[i-1][j - w[i]] + v[i]。

因为我们要的是最大价值，所以在这两个选项里取 max。于是就有了经典的转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) (当 j >= w[i]) dp[i][j] = dp[i-1][j] (当 j < w[i])

为什么“继承之前的最好结果”是合法的？因为前 i-1 件物品的所有选择组合，已经被压缩在 dp[i-1][*] 这一整行里了。你不需要关心这些组合具体长什么样，只需要知道它们在各个容量下的最大价值。这就是动态规划“最优子结构”的体现：全局最优解一定包含子问题的最优解。更直白地说，你可以从后往前倒推：既然最终方案里第 N 件物品要么装、要么不装，那么去掉第 N 件物品后的剩下的部分，也一定是在前 N-1 件物品和对应剩余容量下的最优方案。如果不是最优，你就可以把那一部分替换成更优的，整个方案的价值还能更大，这不就矛盾了嘛。

2.2 亲手推一张完整的 DP 表

理论讲半天，不如亲手算一张表。我们直接看一个具体例子。假设背包容量 W=10，有 4 件物品：

初始化 dp[0][j] = 0，因为一件物品都不选，价值肯定是 0。

先处理 i=1（物品1，重量2，价值3）。容量 j 从 0 到 1 时，装不下，所以 dp[1][0]=0，dp[1][1]=0。从 j=2 开始，能装下了，dp[1][j]=3（因为只有这一件物品，装了价值就是3，不装是0，取最大值为3）。所以这一行变成：

再看 i=2（物品2，重量3，价值4）。j=0、1、2 时装不下物品2，只能继承 dp[1][j] 的值，分别是 0、0、3。j=3 时，两种选择：不装，dp[1][3]=3；装，dp[1][0]+4=4。取最大值 4。j=4 时：不装是 3，装是 dp[1][1]+4=4，所以 dp[2][4]=4。j=5 时：不装是3，装是 dp[1][2]+4=7，取7。后面继续算，就能得到整行：

按同样的方式往下推，dp[3][j] 和 dp[4][j] 我就不逐个列了。重点是看最后 dp[4][10] 的计算过程：不装物品4，价值是 dp[3][10]；装物品4，前提是容量至少 5，那么价值是 dp[3][5]+8。最终结果就是这两个数中的较大者。整个表的右下角那个格子，就是整个问题的最优解。

我建议你第一次学的时候，一定找张纸，把每一行每一列都手动填一遍。填完之后你会发现，自己突然理解了“状态”到底是什么东西——它不是一个虚无缥缈的名词，就是一个表格里的格子，每一格都代表一个已经算清楚了的小规模子问题。

2.3 时间复杂度与空间复杂度

上面这种二维数组解法，需要两层循环：外层遍历物品 i，内层遍历容量 j。每次循环只做常数次操作，所以时间复杂度是 O(N×W)。空间上开了一个 (N+1)×(W+1) 的二维数组，所以空间复杂度也是 O(N×W)。

有人可能会问：如果 W 特别大，比如 W=10^9，这个算法是不是就废了？是的，这就是 01 背包问题的软肋——它的复杂度跟背包容量 W 线性相关，W 一大就会超时超内存。所以当 W 很大、但 N 比较小的时候，有人会换一种“按价值 DP”的思路，也就是把价值当作第二维状态来设计算法。后文我会展开说。

3. 一维数组优化：为什么必须倒着遍历

3.1 从二维滚动到一维的推导过程

二维 DP 表虽然清晰，但有个问题：真的需要保存所有行的数据吗？看看状态转移方程 dp[i][j] 用到的是哪几项——dp[i-1][j] 和 dp[i-1][j-w[i]]。这两项都在“上一行”里。也就是说，当前 i 行的计算只依赖前一行 i-1，再往前的 i-2、i-3 行根本不会再被用到。

既然如此，我们完全可以把二维表压缩成一维数组 dp[j]，代表“当前处理到某一件物品时，容量为 j 的背包能装下的最大价值”。每次处理新物品时，用这个一维数组就地更新。这个技巧通常被叫做“滚动数组”或“就地更新”。

一维更新的代码看起来极其简单：

for i in range(1, N + 1): # 遍历每一件物品 for j in range(W, w[i] - 1, -1): # 容量从大到小遍历 dp[j] = max(dp[j], dp[j - w[i]] + v[i])

但这里有一个极其关键、几乎所有新手都会踩的坑——内层循环为什么要从 W 逆序递减到 w[i]，而不是顺序从小到大？

3.2 顺序遍历会出什么问题：一个反例

为了说清楚这个问题，我们先跑一遍顺序遍历的错误代码：

for i in range(1, N + 1): for j in range(w[i], W + 1): # 错误示范：从小到大 dp[j] = max(dp[j], dp[j - w[i]] + v[i])

还是用上面的例子，只看第一件物品（w=2，v=3）处理时，dp 数组初始全为 0。假设 W=10。

• j=2：dp[2] = max(0, dp[0]+3) = 3
• j=3：dp[3] = max(0, dp[1]+3) = 3
• j=4：dp[4] = max(0, dp[2]+3) = max(0, 3+3) = 6

出事了！j=4 的时候，dp[2] 已经在当前这一轮循环里被更新成了 3，这意味着我们在计算 dp[4] 的时候，把“已经装入第一件物品”后的状态再装了一次第一件物品。换句话说，同样的物品 1 被选了两次。可 01 背包里每件物品最多只能选一次，这显然是错的。

而逆序遍历为什么能避免这个问题？因为 j 从大到小更新的时候，计算 dp[j] 需要的是 dp[j-w[i]]，而这个较小的下标 j-w[i] 一定小于 j，且还没有被当前这一轮更新过。因此 dp[j-w[i]] 仍然是上一轮（也就是还没处理当前物品）的旧值，这正好对应了“第 i 件物品只装一次”的语义。

我见过有些教程只是扔给你一句“要倒序”，然后让读者死记硬背。其实这个倒序的推导过程特别简单，但一旦理解了，你不仅知道怎么用，还能在面试时讲清楚每一步的原因。更重要的是，一旦 DP 题的变体里要求每个物品可以选无限次（完全背包问题），内层循环就要反过来变成正序遍历。如果你不理解倒序的底层逻辑，面对完全背包时很容易再次迷茫。

3.3 一维数组的初始化语义

一维数组 dp[j] 的初始值全部设为 0，这个做法对应的是“背包不一定要装满”的语义：任何容量下，我什么都不装，价值都是 0，这个方案总是合法的。后面我会再说，如果题目改成“恰好装满背包”，初始化方式就会大不相同。

3.4 空间优化后的完整代码

def knapsack_01(N, W, weights, values): dp = [0] * (W + 1) for i in range(N): # 逆序遍历容量 for j in range(W, weights[i] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[W]

这个版本的时间复杂度仍是 O(N×W)，但空间复杂度降到了 O(W)，这是面试和笔试里最常用的版本。我自己的习惯是：先写二维版本理清思路，再用一维版本提交代码，避免一上来就写错逻辑。

4. 从最优值到最优方案：回溯出具体选了哪些物品

很多教程讲完求最大价值就收工了，但实际业务里，你往往不只关心“最多能装多少价值”，还想知道“到底该选哪几件物品”。比如公司要做一个预算有限的投资组合，你不仅需要知道最大收益，还得知道具体投哪几个项目。

当使用二维 DP 数组时，回溯方案非常简单。我们从最后一个格子 dp[N][W] 开始倒推：

• 如果 dp[i][j] == dp[i-1][j]，说明第 i 件物品没有被选中，那么问题收缩到 dp[i-1][j]，即“前 i-1 件物品、容量 j”的最优方案。
• 如果 dp[i][j] == dp[i-1][j-w[i]] + v[i]（同时满足 j ≥ w[i]），说明第 i 件物品被选中了，于是把 i 记录下来，然后问题收缩到 dp[i-1][j-w[i]]。
• 如果两个条件同时成立（dp[i-1][j] 恰好等于 dp[i-1][j-w[i]] + v[i]），说明“选不选这件物品”都能达到同样的最大值。这时可以根据需要任选一种路径，比如优先选或者优先不选，一般来说优先记录“选”的那条路径即可。

这里有个细节容易让人犯迷糊：如果我用的是空间优化后的一维数组，dp[j] 里存的只是最终结果，中间过程被反复覆盖了，还能回溯吗？答案是：基本不行（除非额外记录选择矩阵）。所以在需要输出具体方案时，我建议老老实实用二维数组，别为了省空间丢掉回溯能力。这是典型的“空间换功能”的取舍，实际面试时也是加分项。

下面是个回溯的示意代码：

def knapsack_with_solution(N, W, weights, values): dp = [[0] * (W + 1) for _ in range(N + 1)] for i in range(1, N + 1): for j in range(1, W + 1): if j >= weights[i - 1]: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]) else: dp[i][j] = dp[i - 1][j] # 回溯选中的物品 selected = [] j = W for i in range(N, 0, -1): if j >= weights[i - 1] and dp[i][j] == dp[i - 1][j - weights[i - 1]] + values[i - 1]: selected.append(i) j -= weights[i - 1] selected.reverse() return dp[N][W], selected

回溯的复杂度是 O(N)，只扫描一遍物品就够了。这里要注意：当你发现 dp[i][j] 同时等于不装和装的两种情况时，必须按照你自己的业务规则选择一条路径，否则你得到的“方案”不一定唯一。比如有些场景希望装更少的物品（因为每多一件都要增加管理成本），那就在相等时优先“不选”。

5. 初始化定义决定题目走向：恰好装满与常见变体

5.1 “最多能装”和“恰好装满”的初始化玄机

关于 01 背包，最常被忽略的一个细节就是初始化条件。前面我们一直把 dp 数组全部初始化为 0，这是因为题目问的是“在容量 W 内最多能装多少价值”，不要求背包装满，所有容量的“零价值空包”都是合法的基准状态。

但如果题目改成：“背包必须恰好装满，求能装下的最大价值（装不满返回无解或某个特殊值）”，初始化就要大变。

• 二维版本：dp[0][0] = 0，dp[0][j] 当 j > 0 时设为负无穷（比如 -inf），表示“用 0 件物品根本无法凑出恰好容量 j 的状态”，这是非法状态。
• 一维版本：dp[0] = 0，dp[1..W] = -inf。这样在状态转移时，任何“由非法状态转移而来”的结果都会因为加上 -inf 而仍然保持非法意义，不会被错误地当成合法答案。

为什么要用负无穷而不是 0？举个例子：如果初始化全是 0，那么容量 j=5 时，你可能会得到“什么都不装也是合法方案，价值是 0”的结论。这在“恰好装满”语义下就错了——容量 5 的背包空空如也，哪来的恰好装满？所以必须让这些状态从一开始就“烂掉”，后续怎么转移都不会被误用。

我早年刷题时在这里翻过车。题目要求恰好装满，我图省事直接用全 0 初始化，结果样例过了、提交全错。排查了半天才意识到：不是转移方程的问题，是初始状态把非法状态和合法状态混为一谈了。

5.2 求方案总数的变体

除了求最大价值，01 背包家族里还有一个常见变体：求“恰好装满背包的方案数”。转移方程变成了：

dp[j] = dp[j] + dp[j - w[i]]

初始化时 dp[0] = 1，其余为 0。含义是：凑出容量 0 的方案数为 1（什么都不选），其他容量初始方案数为 0。遍历物品时，每件物品选择“取”或“不取”，方案数自然就是两者相加。这个变体在 LeetCode 的“目标和”“组合总和 IV”等题目中都有体现，核心思想完全一致。

5.3 求最小价值的变体

有时候题目把“价值”换成“代价”，让你求“装满背包的最小代价”。这也很简单，把所有 dp[j] 初始化为正无穷，dp[0]=0，转移方程把 max 改成 min 即可。思路和“恰好装满”一模一样，区别只是把取最大变成取最小。

5.4 二维费用背包：再加一个限制维度

如果每件物品除了重量之外，还有体积（或者说背包有两个限制条件），那就需要三维 DP：dp[i][j][k] 表示前 i 件物品在重量为 j、体积为 k 的限制下能取得的最大价值。转移时会同时考虑重量和体积两个维度。这个变体的思路没有本质变化，只是多了一维循环，空间和时间复杂度都随之增加。我在项目里遇到过类似场景：给服务器分配任务时，既怕 CPU 超核，又怕内存超限，每个任务对两个资源都有需求，二维费用背包正好派上用场。

6. 实战经验与常见误区盘点

6.1 大 W 场景下的“价值反打”技巧

前面提到，当背包容量 W 特别大时，O(N×W) 的复杂度会爆掉。这时有个常见的应对思路：如果单件物品的价值 v[i] 比较小，且总价值 V 在可接受范围内，那就把“价值”当作状态维度，dp[v] 表示“凑出价值 v 所需的最小重量”。最后从小到大遍历价值，找到第一个 dp[v] ≤ W 的值作为答案。这个算法的时间复杂度是 O(N×V)。我在开源项目代码里见过这种做法，专门用来处理 W 高达几千万但单件价值只有几百的题目。

6.2 物品重量为 0 或负数时的雷区

重量为 0 的物品往往被题目悄悄塞进来当陷阱。如果物品重量是 0，逆序遍历和正序遍历就变得没有区别了，因为 j-w[i] == j，无论顺序如何，dp[j] 都能被自己更新。处理这类物品时要格外注意是否需要“无限次使用”的语义。至于重量为负的物品，那就更麻烦了，因为不能再按普通 01 背包处理，通常需要特殊平移或重新建模，这个超出了本文范围，但如果你遇到了，别慌，先想想能不能把负重量问题转换成“偏移量”问题。

6.3 典型误区汇总

我在带人刷题时，整理了这张高频误区对照表，几乎每个人都至少中过一条：

这里再补充一个我自己常犯的失误：二维 DP 初始化时，我偶尔会把 dp[0][j] 和 dp[i][0] 的边界弄混。dp[0][j] 表示“0 件物品在各种容量下的最大价值”，一定是 0；dp[i][0] 表示“容量 0 时选前 i 件物品的最大价值”，也一定是 0（什么都装不下）。两者都是合法边界，任何一边漏了都会导致后续转移出错。

6.4 工程实践里如何选择 DP 数组类型

如果你在做算法题，int 数组通常够用。但如果题目里的价值和容量数量级都在 10^9 附近，加法和比较很容易溢出，这时要把 dp 数组声明为 long（Python 就没有这个烦恼）。另外，不可达状态的初始化值要选准：求最大值时用负无穷（如 -10^18），求最小值时用正无穷（如 10^18），避免在计算 max/min 时被实际可达的边界值干扰。

我自己平时写代码有个习惯：先写二维版本跑通小样例，再改写成一维优化版本。这不是浪费时间，而是用二维版本当“参考答案”，一旦一维版本出 bug，可以快速对照阶段结果定位问题。很多人一上来就想写最精简的代码，结果 debug 的时间比写代码还长，反而得不偿失。

7. 举一反三：从 01 背包到完全背包和多重背包

搞懂了 01 背包的倒序遍历，再去看完全背包（每件物品可以选无限次）就会豁然开朗：

for i in range(N): for j in range(weights[i], W + 1): # 正序遍历容量 dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

唯一的变化就是把内层循环从逆序改成正序。为什么？因为正序意味着在计算 dp[j] 时，dp[j-w[i]] 可能已经在当前这轮循环中被更新过，等价于“还可以继续选择当前物品”，正好符合完全背包“无限取用”的语义。你看，理解倒序原理的好处在这里体现得淋漓尽致：不需要死记两个版本，只要想清楚“一维数组里的旧值代表什么”，一切都能推导出来。

多重背包则更复杂一些，它限制每件物品最多取 c[i] 次。常规做法是把它拆成 01 背包：把第 i 件物品拆成多件独立的“01 物品”，每件的重量和价值是原物品乘以系数 1、2、4、……（二进制拆分），这样就能把 c[i] 次选择组合成任意 0 到 c[i] 次。这个技巧本质上还是 01 背包的变形，所以你会发现，把基础打牢了，后面这些变体学起来都是顺水推舟。

实际业务里，安排服务器资源、预算分配、排产计划、商品打包推荐……这些场景往往都能抽象成某种背包问题。我接过一个需求：在广告预算有限的情况下，从几十个投放渠道里挑出组合，让预估曝光最大化。这不就是标准的 01 背包吗？每个渠道是物品，预算限额是背包容量，预估曝光是价值。虽然数据规模不大，但用背包写出来的程序只有几十行，比业务同事用 Excel 手动试方案不知道高到哪里去了。

关于 01 背包，我最后分享一个心得：别背代码，去背“为什么”。为什么二维能压一维？为什么一维要倒序？为什么恰好装满要初始化成无穷？这三个“为什么”吃透了，你就是把 01 背包从“会做题”提升到了“理解它”的层次。做到了这一步，不管题目怎么改、数据范围怎么调、是面试手写还是业务落地，你都能第一时间反应过来，这才是学动态规划真正值钱的地方。