完全背包问题（从暴力到一维，逐层剖析优化本质）

1. 从“无限拿”的困惑说起完全背包问题到底是什么大家好我是老张一个在算法和工程里摸爬滚打了十来年的老码农。今天咱们不聊那些高大上的AI模型就聊一个非常经典、面试必考、而且新手最容易懵的算法问题——完全背包问题。很多朋友第一次接触背包问题都是从“01背包”开始的每个物品要么拿1要么不拿0。这很符合直觉就像你出门旅行一个充电宝要么带上要么不带总不能带半个。但完全背包问题就“不讲武德”了它的规则是每种物品只要你的背包还装得下想拿多少件就拿多少件无限供应。这听起来是不是有点像游戏里的金币只要你有背包空间就能一直往里塞。或者想象一下你是一个采购员去批发市场进货。某种商品比如矿泉水单价固定你的货车容量有限但你可以决定拉多少箱只要不超载就行。你的目标就是用有限的货车容量装下总价值最高的货物组合。这就是完全背包问题的核心场景。它比01背包多了一层“无限”的可能性也正是这层可能性让它的解法从最直观的暴力枚举到一步步优化成一维数组的动态规划充满了巧思。今天我就带大家从最笨但最易懂的方法开始一步步拆解看看我们是如何把时间复杂度从“恐怖”降到“优雅”的。我会用大量的生活类比和代码示例保证即使你是算法小白也能彻底搞懂其优化本质。2. 暴力美学最直观的三层循环解法当我们第一次遇到“无限拿”这个问题时大脑最直接的思路是什么枚举。把每一种可能的拿法都试一遍然后找出最好的那个。这就是我们优化之路的起点也是理解后续所有优化的基石。2.1 状态定义与暴力思路我们先把问题格式化。假设有N种物品背包总容量是V。第i种物品的体积是v[i]价值是w[i]。我们要用一个数组f来记录“最优解”。f[i][j]这个状态表示只考虑前i种物品在背包容量恰好为j的情况下能获得的最大价值。注意这个“恰好”它让我们的思路更清晰。那么对于第i种物品在面对容量j的背包时我们有多少种选择由于可以拿无限件只要单件体积不超过剩余容量我们就可以拿0件、1件、2件……直到拿不下为止。所以最暴力的方法就呼之欲出了三重循环。第一层循环i枚举当前考虑到的物品种类从第1种考虑到第N种。第二层循环j枚举当前的背包容量从0一直考虑到总容量V。第三层循环k枚举对于第i种物品我们到底拿几件。k从0开始直到k * v[i] j拿的总体积超过容量为止。对于每一个(i, j, k)的组合我们计算一下如果不拿第i种物品即k0最优价值就是f[i-1][j]即只考虑前i-1种物品时的结果如果拿k件第i种物品那么需要先给这k件物品腾出k * v[i]的空间剩下的j - k*v[i]的容量用来放前i-1种物品最优价值就是f[i-1][j - k*v[i]] k * w[i]。我们的目标就是找出所有k的取值中最大的那个价值。2.2 代码实现与复杂度分析让我们把上面的思路翻译成代码。这是最原始的版本虽然效率低但逻辑无比清晰。#include iostream using namespace std; const int N 1010; int f[N][N]; // f[i][j]前i种物品容量j下的最大价值 int v[N]; // 体积 int w[N]; // 价值 int main() { int n, m; // n是物品种数m是背包容量 cin n m; for (int i 1; i n; i) cin v[i] w[i]; // 核心三重循环暴力枚举 for (int i 1; i n; i) { // 枚举物品种类 for (int j 0; j m; j) { // 枚举背包容量 for (int k 0; k * v[i] j; k) { // 枚举第i种物品拿几件 // 状态转移在“不拿”和“拿k件”之间选最大值 f[i][j] max(f[i][j], f[i-1][j - k * v[i]] k * w[i]); } } } cout f[n][m] endl; return 0; }我们来算算这笔“时间账”。三重循环最坏情况下物品种数n和背包容量m同阶假设都为N那么k的循环次数大致是j / v[i]平均下来可以认为是N次。所以总的时间复杂度是O(N³)。如果N是1000那么计算量就是10亿级别这在算法竞赛或者实际工程中是完全不可接受的。空间上我们使用了一个二维数组复杂度是 O(N²)。虽然这个暴力解法很慢但它像一面镜子清晰地照出了问题的所有细节。接下来我们的所有优化都是在它的基础上通过观察规律、消除冗余计算来进行的。记住这个最原始的状态转移方程它是我们优化之路的出发点。3. 第一次优化干掉一层循环从三维到二维看到 O(N³) 的复杂度我们本能地就想能不能砍掉一层循环尤其是最里面那层枚举k的循环看起来就很有重复计算的嫌疑。我们的目标是把时间复杂度降到 O(N²)。这需要一点数学观察和推导。3.1 关键的数学洞察让我们把目光聚焦到状态转移方程上。对于状态f[i][j]我们暴力枚举了所有可能的kf[i][j] max( f[i-1][j], f[i-1][j-v[i]] w[i], f[i-1][j-2*v[i]] 2*w[i], ... )现在我们思考一个稍微小一点容量的状态f[i][j - v[i]]。它代表考虑前i种物品但背包容量少v[i]时的最优解。它的状态转移方程是什么呢f[i][j - v[i]] max( f[i-1][j-v[i]], f[i-1][j-2*v[i]] w[i], f[i-1][j-3*v[i]] 2*w[i], ... )看出来了吗请你仔细对比上面两个式子。f[i][j]从第二项开始f[i-1][j-v[i]] w[i],f[i-1][j-2*v[i]] 2*w[i], ...如果把f[i][j - v[i]]这个最大值加上一个w[i]会得到什么f[i][j - v[i]] w[i] max( f[i-1][j-v[i]] w[i], f[i-1][j-2*v[i]] 2*w[i], f[i-1][j-3*v[i]] 3*w[i], ... )这个结果恰好就是f[i][j]状态转移方程中除了第一项f[i-1][j]之外的所有项的最大值这是一个非常重要的发现。它意味着我们为了求f[i][j]不需要傻傻地去枚举所有k然后比较f[i-1][j - k*v[i]] k*w[i]。我们只需要比较两项不拿第 i 件物品f[i-1][j]至少拿一件第 i 件物品f[i][j - v[i]] w[i]这里f[i][j - v[i]]已经隐含了“在容量j-v[i]下对前i种物品做出最优决策可能拿了0件也可能拿了多件 i”的信息。给它加上w[i]就等价于“在之前最优决策的基础上再拿一件 i”。3.2 优化后的状态转移与代码于是我们的状态转移方程得到了极大的简化如果 j v[i] f[i][j] f[i-1][j] // 容量不够肯定拿不了 如果 j v[i] f[i][j] max(f[i-1][j], f[i][j - v[i]] w[i])注意第二个式子我们比较的是f[i-1][j]和f[i][j - v[i]] w[i]。这里和01背包的核心区别出现了01背包比较的是f[i-1][j]和f[i-1][j-v[i]] w[i]。完全背包用的是f[i][j - v[i]]这代表在计算本行i的数据时已经可以使用本行之前计算过的结果j-v[i]这正是“物品无限取用”特性的体现。基于这个新的方程我们可以写出优化掉k循环的代码#include iostream using namespace std; const int N 1010; int f[N][N]; // 二维DP数组 int v[N], w[N]; int main() { int n, m; cin n m; for (int i 1; i n; i) cin v[i] w[i]; for (int i 1; i n; i) { for (int j 0; j m; j) { // 先继承“不选”的情况 f[i][j] f[i-1][j]; // 如果容量够再考虑“选”的情况并与“不选”比较 if (j v[i]) { f[i][j] max(f[i][j], f[i][j - v[i]] w[i]); } } } cout f[n][m] endl; return 0; }这段代码只有两层循环时间复杂度成功降到了O(N²)。空间复杂度仍是 O(N²)。这是一个巨大的进步。我们通过数学上的等价变形发现了枚举过程中的大量重复比较并用一个已经计算过的状态f[i][j-v[i]]完美地概括了它们。这种“用已计算状态表达新状态”的思想是动态规划优化的精髓。4. 终极优化空间压缩从二维到一维现在我们有了一个时间上高效的 O(N²) 算法。但在一些内存紧张或者数据规模极大的场景下O(N²) 的空间开销比如N10000时需要 100M 的int数组仍然可能成为瓶颈。我们还能不能更进一步把空间也优化掉呢答案是可以的而且优化后的代码会异常简洁。4.1 滚动数组与遍历顺序的奥秘仔细观察优化后的二维DP代码你会发现在计算f[i][j]时它只依赖于两部分数据上一行的f[i-1][j]。本行的f[i][j - v[i]]。这个依赖关系给了我们一个强烈的提示我们或许不需要存储整个二维表格只需要一个一维数组f[j]来滚动更新。f[j]在计算过程中最终代表的就是考虑完所有物品后容量j的最大价值。但这里有一个至关重要的细节遍历顺序。在01背包的空间优化中我们要求第二层循环容量j必须**从大到小逆序**遍历。这是为了防止同一件物品被重复计算。因为01背包中每个物品只能选一次逆序保证了在更新f[j]时用到的f[j - v[i]]是上一轮i-1的状态没有被本轮更新过。然而完全背包恰恰相反我们需要的就是可以重复选择。在状态方程f[i][j] max(f[i-1][j], f[i][j - v[i]] w[i])中我们依赖的正是本行的f[i][j - v[i]]。翻译成一维数组就意味着在更新f[j]时我们希望用到的f[j - v[i]]是已经在本轮被更新过的状态。如何实现很简单把第二层循环的遍历顺序改成从小到大正序。4.2 一维DP代码与原理验证让我们看看最终极的一维DP代码它简洁得令人惊讶#include iostream using namespace std; const int N 1010; int f[N]; // 一维DP数组f[j]表示容量j下的最大价值 int v[N], w[N]; int main() { int n, m; cin n m; for (int i 1; i n; i) cin v[i] w[i]; for (int i 1; i n; i) { // 枚举物品 for (int j v[i]; j m; j) { // 枚举容量正序 // 状态转移此时f[j]和f[j-v[i]]都是“考虑过第i件物品”的状态 f[j] max(f[j], f[j - v[i]] w[i]); } } cout f[m] endl; return 0; }我们来手动模拟一下为什么正序遍历就实现了完全背包。假设物品体积v3价值w4背包容量m6。初始化f[0]0, f[1..6]0。处理这个物品时 (i1)j3:f[3] max(f[3], f[0]4) max(0, 4) 4。这代表拿1件。j4:f[4] max(f[4], f[1]4) max(0, 4) 4。j5:f[5] max(f[5], f[2]4) max(0, 4) 4。j6:关键来了f[6] max(f[6], f[3]4) max(0, 44) 8。注意这里的f[3]是4是刚刚在本轮j3时更新过的值。所以f[6] f[3] w实际上等价于f[i][6] f[i][3] w也就是“在已经拿过一件本物品的基础上再拿一件”这正对应了拿2件物品的情况。通过正序遍历我们让f[j - v[i]]总是能访问到本轮更新后的、包含了“可能已选取当前物品”的最优解从而自然实现了物品的无限次选取。空间复杂度降至O(N)这是一个非常漂亮的优化。5. 总结对比与实战要点走完从暴力三重循环到一维DP的整个旅程让我们最后再梳理一下这每一步到底优化了什么以及我们在实际编码和面试中应该注意什么。5.1 优化路径全景回顾我们可以用一个表格来清晰对比这几种方法方法状态定义核心状态转移方程循环设计时间复杂度空间复杂度核心思想暴力枚举f[i][j]max over k( f[i-1][j-k*v]k*w )三重循环O(N³)O(N²)枚举所有可能直观但冗余二维DPf[i][j]f[i][j]max(f[i-1][j], f[i][j-v]w)二重循环O(N²)O(N²)利用f[i][j-v]概括所有“至少拿一件”的情况一维DPf[j]f[j]max(f[j], f[j-v]w)二重循环j正序O(N²)O(N)滚动数组正序更新以实现物品无限取这个优化链条体现了算法设计中一个非常重要的思想通过分析问题本身的性质这里是物品无限取找到状态之间的内在联系从而用更高效的计算替代低效的枚举。从三维到二维我们通过数学推导消除了对k的显式枚举从二维到一维我们通过改变更新顺序在保证正确性的前提下压缩了空间。5.2 常见误区与记忆技巧在实战中特别是面试或竞赛时关于完全背包我见过最多的错误就是和01背包混淆。这里给大家分享一个我用了很多年的记忆和理解技巧“01背包逆序完全背包正序”。为什么01背包逆序因为它依赖的是f[i-1][j-v]是“旧”状态。一维化后为了保证在计算f[j]时f[j-v]还是“上一件物品”的状态必须从后往前算避免污染。为什么完全背包正序因为它依赖的是f[i][j-v]是“新”状态。一维化后我们希望f[j-v]是“已经考虑过当前物品”的状态所以要从前往后算让它先被更新。如果你一下子记不住推导过程就死死记住这个结论。在写代码时先问自己这是01背包每种物品一个还是完全背包每种物品无限然后相应地决定内层循环的顺序。另外一维DP的写法虽然简洁但初学者容易忽略边界条件。注意我们的内层循环是从j v[i]开始的因为当j v[i]时物品根本放不进去状态f[j]直接继承上一轮或者说当前就是“不选”的状态不需要更新。代码中max(f[j], f[j - v[i]] w[i])的第一个f[j]其实就隐含了“不选”的决策。理解完全背包的优化过程不仅仅是掌握了一个经典算法更是锻炼了我们“优化动态规划”的肌肉记忆。下次当你遇到其他类似可以“无限取用”或者具有某种叠加性质的问题时不妨想想能不能也通过寻找状态间的等式关系来优化掉一层循环能不能通过调整更新顺序来压缩空间这种举一反三的能力才是我们学习算法最宝贵的收获。