企业官网建设流程全解析

0/1背包和完全背包问题

前段时间给团队做算法内部分享，聊到动态规划，我上来先问了大家一个问题：假设你是一个背包客，面前有5件物品，每件只能拿一次，你怎么在不超过负重的前提下让总价值最大？接着我又追问：如果改成每件物品可以无限拿，比如水和干粮，策略会有什么变化？在场的几个同事犹豫了一下，答案各不相同。

这其实就是0/1背包和完全背包的核心区别。"只能拿一次"和"可以拿无数次"，两个字的差别，背后的状态转移逻辑完全不同。很多人算法题刷了不少，一遇到背包就背模板：一个倒序遍历，一个正序遍历，但问为什么，答不上来。这篇文章我就把自己从原理到代码再到踩坑的完整理解写下来，希望能帮到正在准备算法面试、或者工作中需要做资源分配方案的开发者。

1. 两种背包模型的本质差异：一个"选一次"，一个"选到饱"

1.1 0/1背包到底在描述什么场景

0/1背包的"0/1"指的就是每件物品只有两种状态：拿（1）或不拿（0），不存在"拿半个"或者"拿两个"的情况。这是最基础的背包模型，也是后面所有背包问题的地基。

举个最直观的例子：你要去露营，帐篷、睡袋、炉具、食材、水，每样东西都有重量和价值，背包容量有限。帐篷重3公斤价值800，睡袋重2公斤价值600，食材重2公斤价值500……你不可能带两个帐篷，每件物品决策一次，选或者不选，让总重量不超过负重，总价值最大。这就是0/1背包的经典决策过程。

这类问题在真实工程里也有大量影子。比如服务器资源调度：一批任务，每个任务占一定内存、产生一定收益，服务器总内存有限，每个任务最多执行一次，怎么选择任务集合让总收益最大？再比如广告投放预算分配，每个渠道有固定成本、预估转化价值，预算有限，每个渠道要么投要么不投。这些都是0/1背包的形态。

1.2 完全背包的"无限量"约束改了什么

完全背包和0/1背包的唯一区别是：每件物品可以取无限次。同样负重限制下，水、压缩饼干、急救包这种东西，你想带多少带多少，只要总重量扛得住。

别小看这个变化，它直接改变了子问题的结构。0/1背包里，处理完第i件物品后，这件物品不会再次出现；但完全背包里，处理完第i件物品后，你还可以继续选择它，因为它的数量是无限的。通俗点说：0/1背包是"每个商品限购一件"，完全背包是"自助餐随便拿，只要盘子装得下"。

这个区别体现在状态转移方程上，就差一个下标。但差一个下标，意味着两套完全不同的循环策略。很多人就是在这里开始混淆的，后面我会把方程拆开讲透。

2. 状态转移方程推导：从二维DP看清两种选择的本质

2.1 状态定义和初值设置

不管哪种背包，第一步都是定义状态。假设有n件物品，背包容量为W，第i件物品的重量是w[i]，价值是v[i]。

定义dp[i][j]为：考虑前i件物品，在容量为j的背包中能获得的最大价值。这个定义对0/1背包和完全背包都通用。

有了状态定义，接下来就是初值。当i=0时，一件物品都不考虑，不管容量多大，能获得的价值都是0。当j=0时，容量为0，什么也装不下，价值也是0。所以dp[0][j] = 0对任意j成立，dp[i][0] = 0对任意i成立。

建议第一次学背包的人，别急着跳去一维写法，先老老实实把二维DP表格手推一遍。我用一个具体例子：容量W = 10，三件物品分别是（重量3，价值4）、（重量4，价值5）、（重量5，价值6）。手推一遍0/1背包的完整表格，你会发现每个格子都对应一个"选/不选"的决策过程，这种手感对后面理解一维优化至关重要。

2.2 0/1背包的决策逻辑：只能从前一轮"继承"

0/1背包处理第i件物品时，面临两个选择：

• 不选第i件物品：那dp[i][j]继承"前i-1件物品在容量j下的最优解"，即dp[i-1][j]。
• 选第i件物品：前提是j大于等于w[i]，此时需要腾出w[i]的容量给第i件物品，前i-1件物品只能用剩下的j-w[i]容量，所以价值是dp[i-1][j-w[i]] + v[i]。

两者取最大值：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中j >= w[i]。

注意看，方程右侧两个来源都来自i-1这一行，也就是说，第i件物品的决策只依赖前i-1件物品的结果，不会回头再考虑自己。因为0/1背包的物品只能选一次，一旦决策完第i件物品，它就从候选列表里消失了。这就是为什么0/1背包的状态转移要用"上一行"的数据。

2.3 完全背包的决策逻辑：允许"原地自更新"

完全背包第i件物品的状态转移方程是：

dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])，其中j >= w[i]。

对比一下就能发现，唯一区别在第二项：0/1背包用的是dp[i-1][j-w[i]]，完全背包用的是dp[i][j-w[i]]。

多了一个"i"而不是"i-1"，含义完全不同。dp[i][j-w[i]]表示的是：已经考虑过第i件物品之后，在容量j-w[i]下的最优解。也就是说，选完一件第i件物品后，容量还够，你可以继续选第二件、第三件，因为状态里记录的已经是"允许重复选"的结果。

用一个场景帮助你记忆：如果当前是0/1背包，你拿了一件帐篷，下一轮决策时帐篷就不再出现在选项里了；如果是完全背包，你拿了一瓶水，下一轮还可以继续拿水，因为水是无限量供应的。

这个i和i-1的差异，是最核心的区别，也是后面遍历顺序差异的总根源。理解了它，你就不需要死记"谁正序谁倒序"这类口诀了。

3. 一维滚动数组与遍历顺序：最容易翻车的关键细节

3.1 从二维降到一维：空间优化的原理

二维DP的空间复杂度是O(nW)，当W很大（比如10^6级别）时，二维数组直接爆内存。好在每行只依赖上一行的数据，可以用一个一维数组滚动更新，把空间复杂度降到O(W)。

一维数组dp[j]的含义是：容量为j的背包在当前已处理的物品条件下能获得的最大价值。每处理一件物品，就原地更新数组。

但降维之后，遍历顺序就成了生死攸关的问题。顺序写错，答案必错，这是初学者踩得最惨的坑。

3.2 0/1背包必须倒序遍历容量，原因只有一个

先看代码。0/1背包一维写法：

vector<int> dp(W + 1, 0); for (int i = 1; i <= n; i++) { for (int j = W; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }

内层循环为什么要从大到小？假设容量循环是正序：

for (int j = w[i]; j <= W; j++) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); }

当j从小往大走时，dp[j - w[i]]已经被本轮循环更新过了。这个更新的值可能已经包含了"选第i件物品"的结果。于是当你计算dp[j]时，如果不小心又用到了这个值，就相当于第i件物品被选了两次——这在0/1背包里是绝对不允许的。

举个例子：物品重量2，价值3，W=5，正序遍历时：

• j=2：dp[2] = max(dp[2], dp[0]+3) = 3，此时dp[2]已经被更新为包含这个物品。
• j=4：dp[4] = max(dp[4], dp[2]+3) = 6，但这里的dp[2]已经被本轮更新为3了，于是dp[4]变成了6，相当于这件物品被选了两次。

倒序遍历则完全避免了这个问题。因为j从大到小，dp[j-w[i]]对应的容量更小，在上一轮循环中还没有被更新，它保存的是"前i-1件物品"的旧值，正好满足0/1背包"每件最多选一次"的约束。

注意：二维写法里0/1背包的容量正序倒序都可以，因为dp[i][j-w[i]]和dp[i-1][j-w[i]]是不同行，天然隔离。但一维写法必须倒序，这是空间压缩的代价。

3.3 完全背包必须正序遍历容量，原因同样只有一个

vector<int> dp(W + 1, 0); for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= W; j++) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }

完全背包内层循环必须从w[i]正序遍历到W。原因正好相反：我们希望dp[j - w[i]]是"已经被本轮更新过的值"，这样它才包含"继续选取第i件物品"的可能。正序遍历时，容量小的j先被更新，容量大的j在计算时可以直接复用新的dp[j-w[i]]，从而实现无限取用。

还是物品重量2价值3的例子，W=5：

• j=2：dp[2] = 3，选了一次。
• j=4：dp[4] = max(dp[4], dp[2]+3) = 6，但这里的dp[2]是刚才更新过的3，代表可以再选一次，于是两件物品的总价值6被计算出来了。
• j=5：dp[5] = max(dp[5], dp[3]+3) = ...，dp[3]假设为3，结果就是6，表示重量5背包能装两件多一点的物品，实际能装两件（重量4）分。

验证一下：容量5，物品重量2价值3，理论上最多放2件，总重量4，总价值6。完全背包正序遍历得到的dp[5]=6，与预期完全一致。

3.4 二维写法其实没有顺序问题，但要小心空间

二维写法里，0/1背包和完全背包的容量遍历顺序不会影响正确性，因为用的是不同的行。但实践中如果你用二维数组去写完全背包，状态转移写错成i-1就又会退回成0/1背包的语义，调试起来反而更容易乱。

我的建议是：直接学一维写法，一开始就把遍历顺序的原理搞清楚。因为面试官特别喜欢追问"为什么0/1背包要倒序"，你如果能从"防止重复选取"和"利用旧值/新值"的角度答清楚，这一关就稳了。

4. 从代码模板到实际调试：三个高频错误复盘

说完了核心原理，讲几个我见到的真实错误。每次带新人刷题，总有人在这几个点上翻车，而且报错方式还不一样，有的直接答案错误，有的内存溢出，有的一看就是初始化搞错了。

4.1 错误一：0/1背包内层循环写成了正序

症状：结果偏大，而且物品数量少、容量大时错得特别离谱，因为重复取了高价值物品。

排查思路：先在纸上跑一个小例子验证，比如上面那个重量2价值3的例子，如果正序循环j=2到5，会发现dp[4]=6，明显超过了"最多选一次"的合理值。这个错误在面试手写代码时非常常见，写顺手了容易把j--打成j++。

4.2 错误二：完全背包内层循环写成了倒序

症状：答案和0/1背包一样，完全退化了。因为倒序更新导致dp[j-w[i]]永远取不到本轮的新值，无限取用被禁掉了。

这类问题用一个小测试就能发现：物品只有一件，重量2价值3，容量W=10，完全背包正确结果是15（可以拿5件），如果倒序遍历，结果就是3（只能拿一次）。差距非常明显。

4.3 错误三：容量遍历范围写错

很多人在for循环里把j的起点写成1，或者忘记了j >= w[i]的判断条件，导致dp[j-w[i]]下标越界，或者出现负下标。

// 错误写法：没有处理j < w[i]的情况 for (int j = W; j >= 1; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); // 当j < w[i]时，dp[j-w[i]]是负数索引 }

正确做法：循环起点就是w[i]，要么用for (int j = W; j >= w[i]; j--)，要么在循环体内加if (j >= w[i])。别小看这个细节，在C++里负下标不会崩溃但会产生脏数据，在Python里直接IndexError，一调一个准。

4.4 初始化问题：是"恰好装满"还是"不超过容量"

刷题时最常见的一个坑是题意到底是"恰好装满"还是"不超过容量"。

• 求"不超过容量W"的最大价值：dp数组全初始化为0，因为容量没被用完也算合法情况。
• 求"恰好装满W"的最大价值：dp[0]=0，其余dp[j]初始化为负无穷（比如-1e9），因为除了容量0，其他容量没有任何合法方案能恰好装满，只能慢慢推导出来。

这个差异在实际题目中经常出现，尤其是零钱兑换类题目。比如"用若干硬币凑出金额W，每种硬币可以用多次，求最少硬币数"，这是一个完全背包求最小值且恰好装满的变体，初始化就是dp[0]=0，其余dp[j]=INF。如果初始化成0，答案就全乱了，因为在计算min的时候0永远是最小的，所有状态都会停留在0。

我见过有人把这种题用"不超过容量"的模板写，结果每一组测试都能过"示例"，一提交全WA。血泪教训：拿到题目第一件事就是确认容量语义。

5. 经典变体与真实场景映射：背包问题不只是刷题工具

5.1 变体一：方案数统计

有些题不问最大价值，问有多少种方案凑满容量。这类题的状态转移方程从"max"变成"累加"。

0/1背包方案数：

dp[j] += dp[j - w[i]]; // j倒序遍历

完全背包方案数：

dp[j] += dp[j - w[i]]; // j正序遍历

比如LeetCode的零钱兑换II，就是完全背包求方案数。这类题的初始化通常是dp[0]=1，表示凑出0元的方案数是1（不选任何硬币），其余为0。

5.2 变体二：二维费用背包

有的场景限制条件不止一个，比如"重量不超过W且体积不超过V"或者"内存不超过X且CPU占用不超过Y"。这种题目需要把状态数组扩成二维：

vector<vector<int>> dp(W1 + 1, vector<int>(W2 + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = W1; j >= cost1[i]; j--) { // 0/1背包倒序 for (int k = W2; k >= cost2[i]; k--) { // 第二维同样倒序 dp[j][k] = max(dp[j][k], dp[j - cost1[i]][k - cost2[i]] + v[i]); } } }

这类问题在服务器资源编排里很常见，比如每个容器需要同时申请CPU和内存，一台物理机两种资源都有限，选哪些容器实例最划算。我在给一个模拟项目做容器调度优化时就遇到过类似模型。

5.3 真实场景：从"刷题"到"工程"

很多人觉得背包问题是纯面试题，实际工作用不上。我的看法是：背包问题的价值不在于题目本身，而在于让你建立"约束条件下做组合优化"的思维框架。

举几个实际见过的案例：

• 广告投放：某活动预算有限，多个渠道各有固定成本和预期转化，每个渠道最多投一次（0/1背包）或可重复投放（完全背包），选哪几个渠道组合ROI最高。
• 物流装箱：货车载重有限，多种货物各自有重量和纯利润，每种货物数量有限（多重背包）或无限（完全背包），怎么搭配单趟运输利润最大。
• 人力排班：项目多个，每个项目需要一定工时、带来一定收益，团队总工时有限，怎么选项目组合。

这些问题的规模可能不是几十几百，而是成千上万，但动态规划的框架完全复用。理解了0/1背包和完全背包的底层逻辑，你遇到这些工程问题时会本能地思考：状态是什么？约束是什么？变量是有限次还是无限次？这些想清楚了，代码只是时间问题。

5.4 性能优化的一个实用技巧

当n很大、W也很大时，朴素背包的O(nW)会超时超内存。工业上常用的一种优化是单调队列优化，主要针对多重背包。对于完全背包，有一个基于"性价比"的剪枝思路：把物品按单位价值排序，用性价比最高的物品作为最优解的上界估计，提前终止搜索。虽然不改变最坏复杂度，但实际工程里能明显提速。

不过，这些属于进阶优化。建议先把基础版本写对、写透，再考虑上优化手段，不要一开始就陷进优化细节里。

6. 背包问题调试的实操方法论：一个快速验证框架

最后一个部分，分享我调试背包问题时的标准操作流程。这套流程帮我省了大量时间，尤其是面试现场或者赶项目时。

6.1 写代码前，先用表格手推一轮

不管题目看起来多简单，我都会在草稿纸上画一个二维表格，容量从0到W，然后填三行。填完表格再写代码，写出来的逻辑会清晰得多，而且你手推的结果可以直接拿来测代码。

比如W=6，物品有（重量2，价值3）、（重量3，价值4）、（重量4，价值5），0/1背包的表格推一遍，你自然会知道dp[6]应该是多少。代码写完跑一次，答案对不上就先回头查表格，看是哪一格出了问题，再定位是初始化还是循环方向。

6.2 构造小规模测试用例，验证边界

调试背包问题时，我习惯用三个固定用例：

• 用例1：单件物品，容量恰好等于重量，验证dp[W] = v。
• 用例2：单件物品，容量远大于重量，验证0/1结果是v，完全背包结果是v乘以(W/w)的整数部分。
• 用例3：多件物品中有一件重量为0，验证循环是否会出现死循环。

特别是重量为0的物品，很多人没留意。如果物品重量为0，内层循环如果写成for (int j = 0; j <= W; j++)，在完全背包里会不断叠加，甚至陷入死循环。这类边界条件在题目里不一定出现，但测试用例一定要覆盖。

6.3 "先对拍再提交"的实战习惯

面试时不能联网跑判题机，所以我一般准备一套自己写的暴力递归版本作为对拍基准。小规模数据下暴力递归和背包DP的结果必然一致，如果在随机生成的20组数据里都能对上，代码基本就没问题。

这套习惯也适用于工作里的算法模型验证。任何优化算法上线前，都先跑一个朴素版本做基准对比，保证优化方向正确，这是工程师最基本的谨慎。

6.4 识别"看起来是背包但又不是背包"的题目

除了真正的背包题，面试中还有一些"伪背包"，比如"划分数组为两个和相等的子集"，本质是0/1背包求是否存在子集和为总和的一半；再比如"最长上升子序列"也可以看成一种奇怪的背包，但解法完全不同。学会识别题目的真实模型，比背更多模板重要得多。

我在实际指导新人时经常强调：拿到题目先问自己三个问题——这个问题的"容量"是什么？"物品"是什么？"物品是否可以重复取用"？这三个答案写下来，模型基本就定了。

说回开头那个背包客问题。如果是露营三天，帐篷睡袋只能各带一件，这是0/1背包；如果要带饮水和干粮，数量不限，这是完全背包。两种模型，一套动态规划框架，关键在于区分"有限次"和"无限次"的语义，并据此选择遍历方向。

我个人在实际做题和带项目中最大的体会是：背包问题的遍历顺序不是需要背的口诀，而是状态转移方程的自然推论。每当你模糊的时候，回到二维表格里，手动算几格，所有疑问都会消失。希望这篇文章能帮你把这两个基础模型彻底吃透。