企业官网建设流程全解析

0-1背包问题几乎是每一门《算法设计与分析》课程的“必考点”，也是动态规划入门时最容易让人卡住的一道坎。网上讲这个问题的文章一抓一大把，但很多要么直接甩公式，要么只给代码不讲为什么，看完似懂非懂，换个题目又不会了。我当年学的时候也在这上面折腾了不少时间，所以这次干脆把0-1背包的动态规划解法从头到尾彻底拆一遍，包含状态定义、转移方程、手算填表、一维数组优化、回溯找具体方案、初始化陷阱，以及考试和面试里最常见的那些变形考法。全文没有任何跳步，你只要能静下心看完，一定能真正把它吃透。

1. 暴力递归的瓶颈：为什么0-1背包不能靠简单的枚举

在正式进入动态规划之前，先回到问题的起点。0-1背包的题面是这样的：有一个容量为W的背包，面前有n件物品，每件物品有自己的重量w[i]和价值v[i]。现在要在不超过背包容量的前提下，从这些物品中挑出若干件，使得装入背包的总价值最大。每件物品只有两个选择——装进去或者不装进去，不存在“装一半”这种操作，所以才叫0-1背包。

初学者最容易产生的疑问就是：那我把所有组合都枚举一遍，找出价值最大的那一组不就行了吗？确实，理论上可以，但现实很骨感。n件物品，每件有“选”和“不选”两种状态，总的组合数是2的n次方，这个增长速度是爆炸性的。

用具体数字感受一下：假设n=10，也就是10件物品，组合数大概是1024种，手算都能接受。但n增加到30，组合数超过10亿；n=60时，组合数已经超过10的18次方，普通计算机一秒钟能执行的运算量也不过是10的8到9次方量级，全部枚举根本跑不完。算法设计与分析这门课里反复强调的“复杂度分析”，在这里第一次展现出它的实际意义。

对于0-1背包的暴力枚举： - 组合总数：2^n - 时间复杂度：O(2^n) - 空间复杂度：O(n)（递归栈或组合生成空间）

如果你用递归来实现暴力枚举，其实就是在构造一棵深度为n的二叉树。树的每一层对应一个物品，左分支代表“不选”，右分支代表“选”。走到叶子节点时，统计一下当前路径上选的物品总重量和总价值，如果重量不超过背包容量，就用这个价值去更新答案。

这个思路非常直觉，代码写起来也不难，但它的致命伤就是前面说的指数级复杂度。我在实际教学中发现，很多同学知道暴力不可行，却说不出为什么动态规划能比暴力快那么多。要理解这一点，得先看清楚暴力搜索的过程里到底浪费了什么。

我画过一棵递归搜索树来观察。以4件物品为例，搜索树从根节点出发，经过4层决策到达叶子，理论上应该有16个叶子节点。但你仔细看中间那些节点的状态就会发现，大量不同的决策路径到达了完全相同的“当前正在处理第i件物品、剩余容量为j”的状态。比如先看第1件物品选不选，再看第2件物品选不选，和先看第2件再看第1件，最终到达第3件物品时，如果剩余容量相同，这两个分支后面的所有决策就是完全重复的计算。

换句话说，暴力搜索是把同一个子问题反复计算了一遍又一遍。动态规划的核心思想，就是把这种重复计算的结果保存下来，下次再遇到直接查表，而不是重新递归。这就是“用空间换时间”的经典体现。想通这一点，动态规划的大门就算真正推开了。

2. 状态设计与转移方程：dp[i][j]从哪来、到哪去

0-1背包动态规划解法里最重要的一步，就是定义状态数组。很多同学在这里犯迷糊，不知道该把哪些维度放进状态里。其实思路很简单：你要问自己，做决策做到一半的时候，当前局面需要用哪些信息来描述，才能决定后面的路怎么走。

对于0-1背包，有两样信息是必不可少的：一是现在已经处理到了哪些物品，也就是“前i件物品”这个范围；二是背包当前的剩余空间。于是就有了最经典的状态定义：

dp[i][j] = 从前i件物品中挑选若干件，装入容量为j的背包时，能获得的最大总价值

注意这里的下标含义。i的取值范围是0到n，j的取值范围是0到W。dp[0][j]表示一件物品都不选时，容量再大价值也是0；dp[i][0]表示背包容量为0时，什么都装不下，价值也是0。

状态定义好了，接下来想状态转移方程。处理第i件物品时，我们面临两个选择：

第一个选择是不选第i件物品。那问题就退化成“从前i-1件物品中选，装入容量为j的背包”，也就是dp[i-1][j]。

第二个选择是选第i件物品。选了它，就要占用w[i]的重量，前提是j >= w[i]。一旦选了，背包剩余容量变成j - w[i]，前面i-1件物品就要在这个更小的容量下做最优选择，即dp[i-1][j-w[i]]，最后再加上第i件物品的价值v[i]。

我们要求的是最大价值，所以取这两种选择中较大的那个：

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件物品中选若干件装入容量j”的最优方案里包含了第i件物品，那么去掉第i件物品后，剩下的部分一定也是“从前i-1件物品中选若干件装入容量j-w[i]”的最优方案。这一点可以用反证法证明：如果剩下的那部分不是最优的，那就能用更优的子方案替换它，从而得到全局更优的方案，产生矛盾。

无后效性指的是，当前状态一旦确定，后续状态的转移只跟当前状态有关，而不需要关心当前状态是怎么一步步走过来的。dp[i][j]已经把“前i件物品在容量j下的最优价值”完全封装好了，至于这个价值是通过怎样的物品组合得到的，对后面的决策没有任何影响。正是因为这个性质，我们才能放心地只保留这个状态值，而不必记录完整的决策路径。

很多同学刚开始学动态规划，喜欢去“背”状态转移方程，我倒不建议这么做。更好的办法是把dp表当作一张二维表格，一行一行地填，填到某个格子时问自己：这个格子代表什么？它的值可能从哪些格子来？想清楚这两个问题，每一种动态规划题目的转移方程其实都能自己推出来。

3. 一张表走完全过程：从4个物品的完整填表看动态规划的逻辑

纸上得来终觉浅，状态转移方程看着简单，但真正要理解它，我建议亲手填一次表。下面我用一个足够简单的实例，把整张dp表从0开始一步步填出来。你跟着走一遍，很多模糊的地方会自动清晰起来。

假设背包容量W=5，有4件物品：

物品编号： 1 2 3 4 重量w： 2 1 3 2 价值v： 12 10 20 15

建立一个二维数组dp，行代表物品编号从0到4，列代表容量从0到5。第0行和第0列全部初始化为0，这对应“没有物品可选”和“背包容量为0”两种情况。

先填第1行，也就是只考虑第1件物品，重量2，价值12。

• j=0：放不下，dp[1][0]=0。
• j=1：放不下，dp[1][1]=0。
• j=2：容量够了，max(dp[0][2]=0, dp[0][0]+12=12)，取12。
• j=3：max(dp[0][3]=0, dp[0][1]+12=12)，取12。
• j=4：同理取12。
• j=5：同理取12。

所以第1行是：[0, 0, 12, 12, 12, 12]。

接着填第2行，相当于加入第2件物品，重量1，价值10。

• j=0：放不下，0。
• j=1：max(dp[1][1]=0, dp[1][0]+10=10)，取10。
• j=2：max(dp[1][2]=12, dp[1][1]+10=10)，取12。这里有个关键点，一定要用上一行的dp[1][1]而不是本行刚算出来的值，同一件物品不能重复选。
• j=3：max(dp[1][3]=12, dp[1][2]+10=22)，取22。
• j=4：max(dp[1][4]=12, dp[1][3]+10=22)，取22。
• j=5：max(dp[1][5]=12, dp[1][4]+10=22)，取22。

第2行是：[0, 10, 12, 22, 22, 22]。

填第3行，加入第3件物品，重量3，价值20。

• j=0：0。
• j=1：j < w[3]，放不下，取dp[2][1]=10。
• j=2：放不下，取dp[2][2]=12。
• j=3：max(dp[2][3]=22, dp[2][0]+20=20)，取22。注意这里选了第3件反而比不选少，因为第2件物品太具性价比了。
• j=4：max(dp[2][4]=22, dp[2][1]+20=30)，取30。
• j=5：max(dp[2][5]=22, dp[2][2]+20=32)，取32。

第3行是：[0, 10, 12, 22, 30, 32]。

填第4行，加入第4件物品，重量2，价值15。

• j=0：0。
• j=1：放不下，取dp[3][1]=10。
• j=2：max(dp[3][2]=12, dp[3][0]+15=15)，取15。
• j=3：max(dp[3][3]=22, dp[3][1]+15=25)，取25。
• j=4：max(dp[3][4]=30, dp[3][2]+15=27)，取30。
• j=5：max(dp[3][5]=32, dp[3][3]+15=37)，取37。

第4行是：[0, 10, 15, 25, 30, 37]。

最终答案就是dp[4][5]=37。

我常用的填表模版可以写成这样：

n = 4 W = 5 weight = [0, 2, 1, 3, 2] value = [0, 12, 10, 20, 15] 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 >= weight[i]: dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) else: dp[i][j] = dp[i-1][j] print(dp[n][W])

对于这个例子，dp[4][5]=37，对应的最优组合是物品1、物品2和物品4，总重量2+1+2=5，总价值12+10+15=37。还有一组物品3+物品4，总重量5，价值35，比37小，所以不是最优。你自己在草稿纸上把这张表填一遍，比我在这里讲一百句话都有用。

4. 一维数组优化：滚动数组为什么必须逆序更新

二维dp表虽然直观，但空间开销不小。当n和W都很大的时候，一个(n+1)行(W+1)列的二维数组可能会占用大量内存，在一些内存受限的环境里甚至会直接爆掉。而且仔细看转移方程就会发现，dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-w[i]]，也就是说，新的一行只跟紧挨着的上一行有关系，跟更早的行没有任何关系。既然如此，为什么要保留整张二维表呢？完全可以只用一个一维数组，在每一轮迭代中不断覆盖更新。

这就是滚动数组的思想，也是面试中进阶提问的常客。它的核心代码长这样：

dp = [0] * (W + 1) for i in range(1, n + 1): for j in range(W, weight[i] - 1, -1): dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) print(dp[W])

用前面那个例子手动模拟一维数组的变化过程。初始dp全部为0：

处理第1件物品（w=2，v=12），从j=5往j=2倒着更新：

• dp[5]=max(0, 0+12)=12
• dp[4]=max(0, 0+12)=12
• dp[3]=max(0, 0+12)=12
• dp[2]=max(0, 0+12)=12

更新后dp=[0,0,12,12,12,12]。

处理第2件物品（w=1，v=10），从j=5往j=1倒着更新：

• dp[5]=max(12, dp[4]+10=22)=22
• dp[4]=max(12, dp[3]+10=22)=22
• dp[3]=max(12, dp[2]+10=22)=22
• dp[2]=max(12, dp[1]+10=10)=12
• dp[1]=max(0, dp[0]+10=10)=10

更新后dp=[0,10,12,22,22,22]。

处理第3件物品（w=3，v=20），从j=5往j=3倒着更新：

• dp[5]=max(22, dp[2]+20=32)=32
• dp[4]=max(22, dp[1]+20=30)=30
• dp[3]=max(22, dp[0]+20=20)=22

更新后dp=[0,10,12,22,30,32]。

处理第4件物品（w=2，v=15），从j=5往j=2倒着更新：

• dp[5]=max(32, dp[3]+15=37)=37
• dp[4]=max(30, dp[2]+15=27)=30
• dp[3]=max(22, dp[1]+15=25)=25
• dp[2]=max(12, dp[0]+15=15)=15

最终dp=[0,10,15,25,30,37]，答案dp[5]=37。和二维表结果完全一致。

很多初学者会问：为什么一维数组要逆序遍历j，而不能正着遍历？这个问题是所有0-1背包讲解里的重头戏，我用自己的话解释一遍。

核心原因在于：一维数组在更新dp[j]的时候，必须确保用到的dp[j-weight[i]]还是上一轮（也就是没放第i件物品之前）的值。如果j从小到大正序遍历，那么在算dp[j]之前，dp[j-weight[i]]可能已经被本轮更新过了，它代表的是“已经放入了第i件物品”的状态。这样一来，同一个物品就可能被放进背包多次，0-1背包就变成了完全背包，事情就乱套了。

可以这样直观理解：正序遍历的时候，dp[j-weight[i]]是“我刚刚用这个物品更新过”的值，后面再拿这个值去更新dp[j]，等于把这个物品又用了一次。而逆序遍历时，j-weight[i]一定小于j，在从大到小的遍历顺序下，这个较小的下标还没被本轮更新过，所以它仍然是上一轮的状态，这和我们用二维表时dp[i-1][j-weight[i]]的逻辑完全对齐。

我自己在刚开始写代码时也犯过这个错，把内层循环写成从小到大，结果算出来的答案明显偏大。后来用一个小例子去推，才发现问题就出在“正序会导致重复选取”上。记住一句话：0-1背包内层循环逆序，完全背包内层循环正序，这是两类问题代码上最直观的区别。

空间复杂度从O(nW)降到了O(W)，这是一个非常显著的优化。在大规模数据下，这个优化往往是程序能不能跑起来的关键。

5. 回溯求解具体方案：从dp表里把“选了谁”挖出来

有时候题目不只要最大价值，还要你输出具体选了哪些物品。这时候光有一维滚动数组就不够了，因为它压缩掉了一整维的信息，仅仅保留每一轮更新后的最大值，无法再还原决策路径。想要回溯，必须使用二维dp表，因为每一格的转移来源都记录在那个格子里。

回溯的基本规则很简单：从dp[n][W]开始倒着向前推。检查dp[i][j]和dp[i-1][j]是否相等。如果相等，说明第i件物品没被选中，因为不选它也能达到同样的价值，那就继续看dp[i-1][j]。如果不相等，说明第i件物品被选中了，那就把第i件物品记下来，然后背包容量减去w[i]，即j变成j-w[i]，继续看dp[i-1][j-w[i]]。

为什么这个逻辑成立？回看状态转移方程，dp[i][j]的值要么来自dp[i-1][j]（不选），要么来自dp[i-1][j-w[i]]+v[i]（选）。如果两个值恰好相等，那说明选和不选效果一样，题目如果有特殊要求（比如输出字典序最小的方案），需要额外处理这种相等的情况；如果不相等，根据最大值到底来自哪个方向，就能判定第i件物品是否被选中。

用前面那个实例来完整走一遍回溯过程：

• 起点dp[4][5]=37，dp[3][5]=32，37不等于32，说明第4件物品被选中。记录物品4，容量变为5-2=3。
• 看dp[3][3]=22，dp[2][3]=22，两者相等，说明第3件物品没被选中。继续往前。
• 看dp[2][3]=22，dp[1][3]=12，不相等，说明第2件物品被选中。记录物品2，容量变为3-1=2。
• 看dp[1][2]=12，dp[0][2]=0，不相等，说明第1件物品被选中。记录物品1，容量变为2-2=0。

回溯结束，得到选中的物品编号是1、2、4，总价值12+10+15=37，总重量正好5，和前面填表的结论一致。

如果题目要求输出选中的物品重量和价值，回溯完再用编号去查原始数据就行。如果在回溯时遇到dp[i][j]等于dp[i-1][j]但是dp[i-1][j]也等于dp[i-1][j-w[i]]+v[i]的情况，那说明存在多个最优方案，具体选哪个取决于题目要求。这时候只需要在相等时默认走“不选”分支，就能得到一个合法方案。

6. 初始化陷阱与常见变体：不恰好装满与恰好装满

0-1背包最经典的问法是“在不超过背包容量的前提下求最大价值”，此时dp数组全部初始化成0没有任何问题，因为什么都不装、价值为0，本身就是一个合法方案。但题目稍微改一个字，变成“恰好装满背包时能获得的最大价值”，整个初始化逻辑就要换掉。

这个“恰好装满”的坑，在期末考试和面试里都特别常见。很多人把代码背熟了，换个说法就不会了。恰好装满的含义是，最终选出来的物品总重量必须严格等于背包容量W，多余的容量哪怕还能塞进一件物品的一小部分，也不算数。对应到状态定义，dp[i][j]表示“从前i件物品中选若干件，恰好装满容量为j的背包时，能获得的最大价值”。如果根本不存在任何一种方案能恰好装出容量j，这个状态就是无解的，需要用一个特殊值来标记。

一般用负无穷来表示“无解”，编程时可以用一个足够小的负数，比如负的10的9次方。初始化的规则是：dp[0][0]=0，其余dp[0][j]全部设为负无穷。含义是：只用0件物品时，容量为0的背包恰好被装满，价值是0；容量大于0的背包，没有任何物品可选，永远不可能恰好装满，所以是无解。

转移方程本身不用变，但如果从无解状态转移过去，得到的结果仍然是负无穷，这样最终答案dp[n][W]如果不是负无穷，就说明存在恰好装满的方案，否则说明无解。放一个具体的例子说明：

假设背包容量W=4，有3件物品：

物品1：重量2，价值3 物品2：重量2，价值4 物品3：重量3，价值5

不超过容量的普通0-1背包，最优值是7（物品1+2总重4）或5（物品3重量3）。恰好装满容量4时，最优值仍然是7，因为物品1+2的总重正好是4。如果这时加入一件重量1、价值2的物品，情况就不一样了：普通背包可以考虑物品1+2+4？重量5超了；物品1+2总重4价值7，或者物品3+4总重4价值7。恰好装满容量4的最优解也是7。

但如果物品里没有总重正好等于4的组合，比如物品只有重量3、价值5这一件，那么普通背包的最优值是5（容量4装了重量3），而恰好装满时答案是无解，因为没有任何组合能正好凑出重量4。

再往深走一步，还有一类“求最小价值/最小成本”的背包变形。比如把价值v[i]换成“成本”，问恰好装满容量为W的最小总成本。这时候转移方程要改成min，初始化也变成dp[0][0]=0，其余dp[0][j]=正无穷，理由和“最大价值恰好装满”对称，只不过无解标记换成正无穷。

关于“恰好装满”，还有一个很经典的推论就是：普通背包中，如果所有物品重量都大于W，答案是0（什么都不装），这是合法方案；但在恰好装满的设定下，答案是“无解”或者“不存在合法方案”，这两个答案的含义完全不同。审题不清就把这两种情况搞混，是这类题丢分的最常见原因。

7. 从考试到实战：易错点、Python实现细节与后续迁移

0-1背包的动态规划解法讲到这里，核心内容已经全部覆盖了。但这个题目在考试和面试里出现的频率实在太高，我把平时实操中容易踩的坑和可以迁移的思维再集中整理一遍。

第一个高频易错点是下标问题。很多教材和博文的代码里，物品编号都是从1开始的，weight[0]和value[0]通常浪费不用，这样dp[i]对应第i件物品，代码读起来很顺。也有一些代码从0开始下标，那转移方程就要变成dp[i][j]和dp[i-1][j-w[i]]，需要把weight[i-1]对应到第i件物品。我个人强烈建议实现时统一用从1开始的下标，能省不少脑力，也不容易写错边界。

第二个易错点是Python里range的边界。逆序更新的写法是：

for j in range(W, weight[i] - 1, -1): dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

这里的range()是左闭右开区间，所以要写成weight[i]-1，才能保证j能取到weight[i]这个值。我见过不少同学在这里写错成weight[i]，导致容量刚好等于物品重量的那一格永远没被更新，答案偏小。这个小细节，遇到一次就会记住一辈子。

第三个易错点是输入数据的处理。如果从文件或标准输入读数据，题目通常第一行给n和W，接下来n行每行两个整数代表重量和价值。如果物品顺序跟题目描述不一致，记得先按题目要求排好序，再进入dp流程。特别是当题目有特殊输出要求（比如输出字典序最小的方案）时，排序必须在dp之前完成，否则回溯出来的方案可能出现偏差。

第四个易错点是“贪心方案”的干扰。有的同学看到重量小、价值高的物品，很容易想到先按单位重量价值排序，然后贪心选，但0-1背包是不能用贪心的。为什么？因为物品不可分割，贪心只考虑局部最优，不一定能得到全局最优。举例：W=10，物品A重量6价值12，物品B重量5价值10，物品C重量5价值10。按单位价值，A最优，先选A剩下4装不下别的，总价值12；实际上选B和C总价值20，是更好的方案。这个例子我每届都会给学生讲，但每次还是有同学在合卷时犯同样的错误。

从0-1背包往外延伸，它其实是整个背包问题家族的基础，也是动态规划思想的经典范本。搞懂了0-1背包，后面遇到完全背包、多重背包、分组背包，思路是相通的。

完全背包里每件物品可以选无限次，代码上只需要把内层循环改成正序，其他都不用动。理解这个变化的钥匙就在于一维滚动数组的更新顺序，这也是我把“逆序更新”单独拿出来讲一整节的原因。多重背包是每件物品有有限个数量，常见做法是二进制拆分，把若干个相同物品打包成不同的物品组，然后转换成0-1背包来解。分组背包把物品分到若干组，每组最多选一件，状态转移时要加一层枚举组内物品的循环。

背包问题还能和很多其他考点结合。求方案数时，转移方程里的max改成累加，初始化时dp[0]=1；求最小价值时，max改成min，初始化用正无穷；求具体方案时，用二维表回溯；求字典序最小方案时，物品要先排序，回溯时优先选择编号小的物品。

我在实际做算法题和带新人的时候，最大的体会是：不要试图记住每一种背包问题的代码模板，只要抓住“状态定义”“转移方程”“初始化”“遍历顺序”这四个分析维度，遇到问题先想清楚这四件事，大部分题目都能自己推出来。0-1背包之所以被当作经典中的经典，就是因为它把这四个维度的每一种变化都体现得很充分。

如果你正在准备《算法设计与分析》的期末考试或者找实习的算法面试，我建议你拿一张A4纸，把今天这个4物品5容量的例子重新手算一遍，从二维表到一维滚动数组，再到回溯方案，每一步都不要跳过。这种“手算一遍胜过看十遍”的事情，可能是我在算法学习上分享的最有价值的经验了。等你能不假思索地把这些步骤写出来，你的动态规划基础就已经非常扎实了。