企业官网建设流程全解析

背包类问题在动态规划里属于绕不开的经典题型，而完全背包问题又是其中最容易“以为自己懂了、一写就错”的那一类。很多人第一次接触它时，脑子里装的是 01 背包的模板，结果把内层循环改成倒着写、正着写都试了一遍，提交上去一半通过一半超时，最后连初始化该填 0 还是填负无穷都开始怀疑人生。我自己当年也是踩过这个坑的：明明状态转移方程只差一个下标，跑出来的答案却能差出十万八千里。这篇文章就是想把完全背包问题从朴素解法到空间优化的完整推导过程掰开揉碎讲清楚，尤其是“为什么一维数组的内层循环要正着走”这个卡了无数新手的点。适合正在刷动态规划入门题、被多重循环绕晕，或者想系统整理背包九讲的在校学生和算法爱好者。

1. 问题定义与模型抽象

1.1 完全背包到底在描述什么场景

先把题目本身说清楚。完全背包问题的标准描述是这样的：有 N 种物品，每种物品都有一个体积（也叫重量、代价）w[i] 和一个价值 v[i]，并且每种物品可以取无限多次。现在给一个容量为 W 的背包，问在不超容量的前提下，能装下的最大总价值是多少。

这里的“无限多次”是关键定语。它区别于 01 背包的“每种最多取一次”，也区别于多重背包的“每种最多取 s[i] 次”。换句话说，完全背包的世界里，只要你背包还有空间，同一件东西你想塞几件就塞几件。

我习惯用一个生活化的场景来记这个模型：去自助餐厅拿菜，盘子容量有限，每样菜你都可以拿任意多份，但每种菜每一份占的格子数和带来的满足感是固定的，问怎么拿最划算。这个类比里，“盘子容量”就是背包容量 W，“菜的份数”就是物品个数，“拿走无限份”对应完全背包的核心特征。相比之下，01 背包就像限量供应的甜品，每人只能拿一份；多重背包就是“每人限拿三份”的那种规则。

从数学上看，完全背包就是这样一个整数规划问题：在约束 Σ k_i · w_i ≤ W（其中 k_i ≥ 0 为整数）下，最大化 Σ k_i · v_i。这里的 k_i 是每种物品取用的件数，可以取 0，也可以取很大。很多教材会把它写成 min 形式的“恰好装满求最小代价”，但那是变体，主体思路是一样的。

1.2 为什么不能直接用贪心解决

第一次看到这个问题的人，往往会本能地想：既然每样东西可以无限拿，那我算一下每件物品的“性价比”（单位体积的价值 v[i] / w[i]），从高到低拿不就行了？这个直觉在分数背包里是对的，因为你可以把一件物品切开来拿；但在完全背包里，物品是整件的，不能切。

举个能直接打脸贪心的反例。背包容量 W = 10，有两件物品：物品 A 体积 6、价值 8（性价比 1.33），物品 B 体积 5、价值 7（性价比 1.4）。按性价比排序会先拿 B，剩 5 再拿一件 B，总价值 14，剩余 0。但最优解其实是拿一件 A 加一件 B，体积 11 超了不行；那拿两件 B 是 14，而只拿一件 A 再加……拿不下了。换个例子：容量 10，物品 A 体积 6 价值 8，物品 B 体积 4 价值 5，物品 C 体积 3 价值 4。贪心按性价比先看 A（1.33），拿一件剩 4，再拿一件 B，总价值 13；但最优是拿两件 B 加……4+4=8 剩 2 拿不了 C，价值 10；或者 B+C+C = 4+3+3 = 10，价值 5+4+4=13，还是 13。真正让贪心翻车的例子是“性价比高但体积也很大，导致留着空间反而能装更多高性价比组合”的情况。经典反例：W=5，物品一 w=4, v=5（性价比 1.25），物品二 w=3, v=4（性价比 1.33），物品三 w=1, v=1（性价比 1）。贪心先拿物品二（1.33），剩 2 拿两个物品三，价值 4+2=6；但最优是物品一加物品三，4+1=5 体积，价值 6；换两个物品二，体积 6 超了。这个例子其实贪心也没差，所以我更愿意用这个：W=10，物品 1: w=7, v=9；物品 2: w=5, v=6；物品 3: w=3, v=3。性价比：物品1=1.29，物品2=1.2，物品3=1。贪心拿一件物品1（剩3），再拿一件物品3，总价值 12。但最优是两件物品2，体积 10，价值 12；或者一件物品1加……9+？剩3只能拿物品3=3，合计12；物品2+物品2+？=12。也平了。

老实说，纯贪心在完全背包上失败的经典构造是：W=10，物品 A w=6 v=7，物品 B w=5 v=6，物品 C w=4 v=5。性价比 A=1.167, B=1.2, C=1.25。贪心按 C 先拿，拿两件 C：体积 8 价值 10，剩 2 拿不了，总价值 10；但最优是 A+C = 体积 10 价值 12。看，贪心输了。这说明局部性价比最优不等于全局最优，必须用动态规划穷举所有组合。

注意：贪心只能在“物品可以任意分割”的分数背包里保证最优，整件选取的场景一律要用动态规划。

1.3 状态设计与维度选择

动态规划的第一步永远是定义状态。完全背包最自然的状态设计是二维的：

• dp[i][j]表示只考虑前 i 种物品，当背包容量为 j 时能获得的最大价值。

为什么是这两个维度？因为决策过程是按“物品种类”一步步推进的，每种物品我们要决定“拿几件”；而约束是“背包容量”。二维状态恰好把“决策到哪一步”和“还剩多少资源”这两个信息都记录下来，避免了后续决策依赖前面具体选择了什么。这就是动态规划里常说的“无后效性”——一旦确定了前 i 种物品在容量 j 下的最优结果，后面的决策只跟这个结果有关，不需要知道前面具体怎么拿的。

对比一下 01 背包的状态设计，其实一模一样，区别只发生在转移时的下标细节上。这也是很多人迷惑的地方：状态定义完全一样，代码却差一个循环方向，答案就完全不同。

初始化要怎么填？如果题目要求恰好装满，那dp[0][j]（容量 j 但没有任何物品可选）里只有dp[0][0] = 0是合法的，其余dp[0][j]都要设成负无穷，表示“不可能恰好装满”；如果题目不要求装满（大多数模板题都是这种），那么dp[0][j]全部设成 0 即可，因为空背包本身就是一种合法状态，价值为 0。这个初始化差异是新手最容易忽视的细节，我会在后面的排查章节专门讲。

2. 从朴素解到一维优化的完整推导

2.1 二维朴素解法的转移方程

先写出最直白的二维转移方程。对于dp[i][j]，我们面对第 i 种物品，可以决定取 0 件、1 件、2 件……直到装不下为止。但不需要真的去枚举“取几件”，因为动态规划可以用一个巧妙的转移把枚举过程省掉：

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

这个方程的含义要拆开看：

• dp[i-1][j]表示第 i 种物品一件都不拿，那么结果就等于只考虑前 i-1 种物品、容量 j 的最优值。
• dp[i][j - w[i]] + v[i]表示至少拿一件第 i 种物品。注意这里用的是dp[i][j - w[i]]而不是dp[i-1][j - w[i]]——这正是完全背包的灵魂所在。因为取走一件第 i 种物品后，剩下的容量里仍然可以继续取第 i 种物品，所以还停留在“前 i 种物品”这个阶段，而不是退回“前 i-1 种”。

这个细节一对比就非常清楚。01 背包的方程是dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])，因为每件物品只能拿一次，拿完就必须退回上一层。完全背包把第二个下标里的i-1改成了i，仅此一字之差，就实现了“无限取”的能力。

很多教程喜欢用“枚举 k 件”的写法，即dp[i][j] = max(dp[i-1][j - k·w[i]] + k·v[i])，k 从 0 枚举到 j/w[i]。这个写法正确但效率低，枚举 k 会多一层循环。而上面那个dp[i][j-w[i]] + v[i]的写法之所以等价，是因为它把“再拿一件”的动作无限次地递归了下去，本质上已经把枚举折叠进状态转移里了。

2.2 空间优化：为什么要压成一维

二维数组dp[N][W]在 N 和 W 都不大时没问题，但实战中 N 和 W 常常达到 10^3 甚至 10^4 量级，二维数组会直接超内存。这时候就要做滚动数组优化。

观察转移方程dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])，你会发现：计算第 i 行时，只依赖第 i-1 行的dp[i-1][j]和第 i 行左侧的dp[i][j-w[i]]。这说明我们没必要保留整个二维表，用一个一维数组dp[j]就够了，只要保证计算顺序能拿到正确的旧值和新值。

关键问题来了：这个一维数组的内层循环该正着走还是倒着走？

答案是完全背包必须正序（从小到大）遍历容量 j。原因是这样的：当我们用一维数组dp[j]更新时，dp[j] = max(dp[j], dp[j - w[i]] + v[i])，右边的dp[j - w[i]]是容量更小的位置。如果 j 从小到大遍历，那么在计算dp[j]时，dp[j - w[i]]已经在本次 i 的循环中被更新过了，它记录的是“已经考虑过第 i 种物品”的值——这恰好对应完全背包需要的dp[i][j-w[i]]。反过来如果倒序遍历，dp[j-w[i]]还是上一轮 i-1 的旧值，那就变成了 01 背包的语义。

这就解释了那个困扰无数人的现象：01 背包倒序，完全背包正序，一维代码里唯一的区别就是循环方向。我第一次搞懂这一点的时候，瞬间觉得背包问题通透了不少。你可以自己拿个小例子手推一遍：容量 5，物品体积 2、价值 3，正序遍历时dp[2]先被更新为 3，然后dp[4]用到dp[2]=3，得到 6，等价于拿了两件；倒序遍历时dp[4]用到的是旧的dp[2]=0，得到 3，只拿一件。手推一遍，胜过看十遍公式。

2.3 一维代码的正确模板

把上面推导落地成代码。C++ 版本如下：

int completeKnapsack(int W, vector<int>& w, vector<int>& v) { int n = w.size(); vector<int> dp(W + 1, 0); // 不要求装满，全部初始化为 0 for (int i = 0; i < n; i++) { for (int j = w[i]; j <= W; j++) { // 正序遍历，这是与 01 背包的唯一区别 dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } return dp[W]; }

Python 版本更直观：

def complete_knapsack(W, w, v): dp = [0] * (W + 1) for i in range(len(w)): for j in range(w[i], W + 1): # 正序 dp[j] = max(dp[j], dp[j - w[i]] + v[i]) return dp[W]

这段代码的时间复杂度是 O(N·W)，空间复杂度 O(W)。对比二维版本的 O(N·W) 空间，压缩得非常彻底。

提示：如果你把内层循环写成for (int j = W; j >= w[i]; j--)，就变成了 01 背包。一定要记住这个方向差异，笔试面试被追问的时候大概率会考。

3. 手推实例与优化细节拆解

3.1 用一个小案例把过程跑一遍

光看公式容易飘，我们用一个具体例子走一遍。背包容量 W = 8，物品有三种：

按照dp[j] = max(dp[j], dp[j-w]+v)的顺序逐个物品更新。初始化 dp 数组全 0，下标 0 到 8。

处理物品 1（w=2, v=3），j 从 2 遍历到 8：

• 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) = 6
• j=5: dp[5] = max(0, dp[3]+3) = 6
• j=6: dp[6] = max(0, dp[4]+3) = 9
• j=7: dp[7] = max(0, dp[5]+3) = 9
• j=8: dp[8] = max(0, dp[6]+3) = 12

可以看到 dp[8]=12，等价于拿了四件物品 1，正好填满，价值 12。

处理物品 2（w=3, v=4），j 从 3 到 8：

• j=3: dp[3] = max(3, dp[0]+4) = 4
• j=4: dp[4] = max(6, dp[1]+4) = 6
• j=5: dp[5] = max(6, dp[2]+4) = 7（dp[2]=3，拿一件物品2加一件物品1）
• j=6: dp[6] = max(9, dp[3]+4) = 9（dp[3]=4，4+4=8，不如 9）
• j=7: dp[7] = max(9, dp[4]+4) = 10（dp[4]=6，6+4=10）
• j=8: dp[8] = max(12, dp[5]+4) = 12

处理物品 3（w=4, v=5），j 从 4 到 8：

• j=4: dp[4] = max(6, dp[0]+5) = 6
• j=5: dp[5] = max(7, dp[1]+5) = 7
• j=6: dp[6] = max(9, dp[2]+5) = 9（dp[2]=3，3+5=8，不如 9）
• j=7: dp[7] = max(10, dp[3]+5) = 10
• j=8: dp[8] = max(12, dp[4]+5) = 12（6+5=11，不如 12）

最终答案是 dp[8] = 12。这个例子恰好说明：贪心地只拿性价比最高的物品 1（性价比 1.5）确实拿到了最优，但如果换一组数据，贪心就会失效。手推的价值在于你能亲眼看到dp[j-w]用的是同行的新值，这就是无限取的体现。

3.2 恰好装满与不要求装满的初始化差异

这是完全背包里最容易被忽略、又极其容易出错的点。两种题型在代码上的区别只在于初始化：

不要求装满（求最大价值，容量可以有剩余）：dp 数组全部初始化为 0。因为“什么都没装”是一种合法状态，价值为 0，而且余下的容量空着也允许。

恰好装满（容量必须用尽）：dp[0] = 0，dp[1..W] = -∞（或一个足够小的负数）。为什么？因为容量 0 恰好装满的合法状态价值是 0；而容量大于 0 却没有任何物品时，是“不可能装满”的非法状态，用负无穷标记。这样在转移时，如果dp[j-w[i]]是负无穷，加上 v[i] 仍然是一个极大负数，不会被误选为答案。

我见过太多人在“恰好装满”的题上把 dp 全初始化成 0，结果求出来的答案对应“没装满但价值虚高”的错误方案。记住这个口诀：求最大值且不装满用 0，恰好装满用负无穷；如果求最小值，则恰好装满用正无穷，不装满也用 0（但最小值问题少见）。

3.3 枚举“取几件”的写法为什么更慢

前面提过朴素写法dp[i][j] = max(dp[i-1][j-k·w[i]] + k·v[i])，k 从 0 到 j/w[i]。这个写法时间复杂度是 O(N·W·(W/w))，最坏情况下近似 O(N·W²)，在 W 较大时直接爆炸。而优化后的写法把枚举折叠掉，降到 O(N·W)。这是完全背包优化过程里最核心的一次跃迁。

为什么可以折叠？因为“取 k 件”这个动作可以拆成“先取 1 件，剩下容量再考虑还要不要取”，而“剩下容量再考虑”这件事已经被dp[i][j-w[i]]这个状态描述过了。这就是动态规划最喜欢用的子问题重叠——把一个大决策拆成一连串相同结构的子决策，每个子决策只做一次。

心得：很多背包变体（比如带数量限制的多重背包）之所以难，就是因为不能直接这样折叠，需要引入二进制拆分或单调队列优化。完全背包恰好是可以优雅折叠的那一类。

4. 常见坑点与排查速查表

4.1 内层循环方向写反导致答案偏小

这是完全背包最高频的错误，没有之一。症状是：明明每件物品可以拿无数次，跑出来的结果却总比正确答案小，而且小得“像是每件只拿了一次”。原因就是把内层循环写成了倒序，语义退化成了 01 背包。

排查方法很简单：随便构造一个物品体积能被容量整除的用例，比如 W=10、物品 w=2、v=3，正确答案应该是 dp[10]=15（五件）。如果你跑出来是 3，基本就锁定是循环方向问题。看一眼for (int j = W; j >= w[i]; j--)这行，把它改成for (int j = w[i]; j <= W; j++)就行。

4.2 二维转移写成 dp[i-1][j-w] 导致退化

另一个隐蔽的坑：在二维写法里，把dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])写成了dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。这同样是退化成了 01 背包的转移。区别只在下标里的 i 和 i-1，肉眼极难发现，但语义完全不同。记住：完全背包取完一件还留在本层，所以是dp[i][...]；01 背包取完退回上一层，所以是dp[i-1][...]。

4.3 初始化不当导致的“恰好装满”错误

症状是恰好装满的题里答案偏大，或者根本给不出正确的最大值。检查两点：一是 dp[0] 有没有设成 0；二是 dp[1..W] 有没有设成负无穷。如果用的是INT_MIN，还要小心加 v[i] 时溢出，最好用一个足够小但不至于溢出的值，比如-1e9。

4.4 常见问题速查表

4.5 几个能提速的常数级优化

虽然完全背包已经是 O(N·W)，但在数据量大的时候还能再抠一点：

去掉“体积大且价值低”的冗余物品。如果存在物品 a 和物品 b，满足 w[a] ≥ w[b] 且 v[a] ≤ v[b]，那么物品 a 永远不会出现在最优解里（因为拿一件 a 不如拿一件 b，还省空间，而 b 可以无限拿）。预处理时可以 O(N²) 筛一遍。

合并同体积物品，同体积只保留价值最大的那件。

按体积排序后处理，能在局部提升缓存命中率，虽然理论复杂度不变，但实测在小数据上有百分之十几的提速。

这些优化不是必须的，但如果你在刷那种卡常数的大数据题，值得加上。

5. 从完全背包延伸到多重背包的思路

理解了完全背包的“正序遍历”和“子问题折叠”，多重背包（每种物品最多取 s[i] 次）就有了自然的过渡路径。多重背包不能直接套完全背包的模板，因为数量有了上限，当剩余件数用完后就不能再取了。

最朴素的思路是把第 i 种物品当成 s[i] 个独立的 01 背包物品，逐个用倒序遍历处理，复杂度是 O(W·Σs[i])，s[i] 大时会超时。改进版是二进制拆分：把 s[i] 拆成 1、2、4、8……这些 2 的幂次，最后不足的部分单独作为一块。这样每件物品被拆成 O(log s[i]) 个 01 背包物品，复杂度降到 O(W·Σlog s[i])，非常实用。

还有一个更高级的单调队列优化，把多重背包压到 O(N·W)，但推导复杂，属于竞赛进阶内容。我这里提它的目的是让你看到：完全背包是背包体系里承上启下的一环——它上承 01 背包的“选或不选”，下启多重背包的“数量限制”。把完全背包的正序原理吃透，多重背包的二进制拆分会顺很多。

不同的场景对应不同的变体，简单的对照如下：

这张表把我当年啃背包九讲时记得最头疼的三个方向问题一次性摆平了。如果你能默写出来，说明背包的基础框架已经立住了。

我个人在实际写题和给学弟讲题的过程中最大的体会是：完全背包的“一维正序”这个点，光看文字说明很难真正内化，必须自己拿张纸把 dp 数组一步步填出来，看着dp[j-w]从旧值变成新值的那一刻，你才会真的记住。踩过几次“倒序写反了、答案凭空少一半”的坑之后，这个方向就再也忘不掉了。另外一个建议是，别一上来就背模板，先把二维的朴素转移写对，再自己动手压一维，压缩过程中卡在哪一步，那个点就是你没真正理解的地方，针对性补一下就通透了。至于后续想继续深入的话，可以从带着“物品至少取一次”限制的变体入手，或者去研究多重背包的单调队列写法，都是很自然的下一步。