我从很早就注意到一个现象不少人学动态规划01背包能写得很顺一到完全背包就卡壳。代码看着就是那两三行的差别可就是绕不过那个弯。后来我琢磨明白了完全背包不是01背包的小改动它是状态定义层面的一次升级。这篇文章我就用最直白的方式把完全背包问题从状态定义、递推方程到空间压缩、边界初始化再到变体识别把整个链路给你捋清楚。适合的读者刚学完01背包、想彻底搞懂完全背包的同学刷LeetCode动态规划题总在零钱兑换单词拆分这类题上栽跟头的人以及准备面试或竞赛、想把背包模型吃透的人。我会把每个为什么这么写都讲透而不是只给你一个模板代码。1. 完全背包的无限次到底改变了什么1.1 先看一个最容易被忽视的基本盘背包问题里01背包说的是有N件物品每件物品重量w[i]、价值v[i]每个物品最多选一次放进容量为V的背包求能装下的最大价值。完全背包改了一个条件每个物品可以选无限次。这个无限次三个字听起来就是多了一个循环的事实际上它把整个决策模型都改了。举个例子。背包容量10只有一件物品重量3价值5。01背包的世界里答案就是5你只能选一次。完全背包的世界里你可以选3次装9的重量总价值15还剩下1的容量空着也没办法。同一个数据两种模型答案差了3倍。这就是无限次带来的质变而不是量变。1.2 为什么01背包的代码直接改循环会炸网上很多入门教程会告诉你完全背包就是把01背包的内层循环反过来写。这话对但没讲为什么。我先给你看一个常见的错误改法。有人觉得既然完全背包的物品能选无限次那就把01背包的选或不选扩展成选0次、选1次、选2次……选到装不下为止。于是写了个三重循环for (int i 1; i N; i) { for (int j V; j w[i]; j--) { for (int k 1; k * w[i] j; k) { dp[j] max(dp[j], dp[j - k * w[i]] k * v[i]); } } }这个写法能跑出正确答案但它的时间复杂度是O(NV*V/w[i])遇到容量稍微大一点的数据就直接超时。更关键的是这个三重循环掩盖了完全背包真正的结构。你其实不需要枚举选了几件因为选几件这件事可以通过状态的层层递推自动完成。怎么做到的看下一节的状态转移方程。2. 状态转移方程选或不选你只需要两个决策2.1 从朴素方程到递推优化先回到二维状态定义。设dp[i][j]表示考虑前i种物品背包容量为j时能获得的最大价值。面对第i种物品时因为可以选无限次从选几件的角度写状态转移是dp[i][j] max(k从0到j/w[i]) ( dp[i-1][j - kw[i]] kv[i] )这个方程逻辑上绝对正确但要枚举k复杂度太高。现在做一步关键化简。把选k件拆成两步来看第i种物品选0件那状态就是dp[i-1][j]。第i种物品至少选1件那我先拿一件放进背包剩下的容量j-w[i]还可以继续考虑第i种物品因为它还能再选于是状态是dp[i][j-w[i]] v[i]。所以真正的完全背包递推方程是dp[i][j] max( dp[i-1][j], dp[i][j-w[i]] v[i] )注意看第二个选项的下标是dp[i]不是dp[i-1]。这就是完全背包和01背包最本质的差别。01背包里选了当前物品后剩下的容量只能考虑前i-1种物品所以是dp[i-1][j-w[i]]。完全背包里选了当前物品后剩下的容量还能继续选当前物品所以是dp[i][j-w[i]]。这一步理解透了正序循环、逆序循环的问题就迎刃而解了。2.2 用一个生活案例把方程钉死说个贴近生活的例子。你去自助餐厅同一种食物你可以拿很多趟。01背包等于餐厅规定每道菜最多拿一次拿完这盘这道菜就在你面前划掉了。完全背包等于餐厅不限制你拿完一盘回座位吃完还能再去拿同一道菜。那你在设计今天这顿怎么吃最值的策略时面对一盘红烧肉你可以选择不拿那当前饱腹值就是dp[i-1][j]。你也可以选择拿一盘拿完之后你获得价值v[i]但你的胃容量少了w[i]。关键是你还在这个餐厅面对的还是红烧肉这道菜你还可以决定要不要再去拿所以接下来看的是dp[i][j-w[i]]。是不是一下子就通了拿完之后我还能继续拿同一道菜这就是dp[i]而不是dp[i-1]的含义。3. 一维数组优化正序循环的真正原因3.1 滚动数组背后的就地更新逻辑二维转一维靠的是滚动数组——每次生成新一行的时候旧数据可以被安全覆盖因为我们不需要它了。01背包一维化时容量j要倒序遍历原因是dp[j-w[i]]如果正序更新过它就已经包含了当前物品的信息再拿去算dp[j]就等于当前物品被用了两次。但01背包的物品只能用一次所以必须倒序保证dp[j-w[i]]还是上一轮前i-1件物品的旧值。完全背包正好相反我们希望dp[j-w[i]]已经包含当前物品的信息因为当前物品本来就允许用多次。所以容量j正序遍历让dp[j-w[i]]先更新后续的dp[j]才能拿到已经拿过当前物品的状态。一句话版本01背包倒序是为了不重复取物品完全背包正序是为了能重复取物品。3.2 最简代码C和Python的对照实现C一维完全背包#include iostream #include algorithm using namespace std; const int MAXN 1005; int w[MAXN], v[MAXN]; long long dp[100005]; int main() { int N, V; cin N V; for (int i 1; i N; i) { cin w[i] v[i]; } for (int i 1; i N; i) { for (int j w[i]; j V; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } cout dp[V] endl; return 0; }Python实现def complete_knapsack(n, capacity, weights, values): dp [0] * (capacity 1) for i in range(n): for j in range(weights[i], capacity 1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]这里我特意用了long long因为价值累加次数变多之后很容易爆int。很多人刷题时忽略了这个问题小数据没事数据一大就是WA答案错误排查半天才反应过来是数据类型。用二进制联想记的话01和完全内层循环方向正好相反别记反了。记反的结果就是答案偏小因为你把可重复算成了不可重复。4. 两个工程级优化预处理筛选与二进制拆分4.1 性价比预处理先甩掉绝对废物物品完全背包里物品不限制数量所以可以做一个01背包想做但意义不大的预筛按性价比价值/重量排序后如果一个物品重量更大、价值还更低那它完全就是废物可以直接丢掉。举个例子。物品A重量5价值10物品B重量4价值9。B的性价比高于A。如果背包容量允许任何时候选A能做到的事用两个B或B的组合可以做得更好至少不会更差。反过来物品A重量5价值12物品B重量4价值8。这时候B虽然性价比略低但它重量小在剩4容量时能补一刀不能扔。工程上可以这样筛性价比降序排序后扫描一遍如果发现某物品重量比前面的物品大、价值反而比前面的小就可以删除如果重量也大、价值也大保留下来设为新的比较基准。这个优化在物品数量大N上万的时候效果极为明显经常能把DP的物品维度砍掉五六成。竞赛里如果数据给得刁钻这一步往往就是AC和TLE的区别。4.2 二进制拆分把无限次变成log次有时候完全背包会和多重背包混在一道题里。比如物品A最多选3件物品B最多选5件物品C无限选。这时候统一转成01背包最省事把每件物品按数量拆成1、2、4、8……个为单位的新物品每个单位当作独立的01背包物品。这样拆完理论上物品数最多变成N*log(最大数量)复杂度可控。对于无限选的物品可以设一个上限比如背包容量上限对应的最大件数再按二进制拆。实际做题时二进制拆分的典型场景是多重背包但完全背包遇到同种物品有上限的变体时这个思路同样适用。不过要提醒一句如果题目没有数量上限、纯粹完全背包那就别二进制拆分了直接正序DPO(NV)的时间复杂度就是最优的。4.3 什么时候用单调队列优化完全背包还有一档进阶优化单调队列优化能把时间复杂度从O(NV)降到O(NV)但常数更小其实不是。单调队列优化的真正价值在于处理多重背包——每个物品有明确数量上限的问题。但就完全背包本身而言它没有数量上限正序DP已经利用了这个特性单调队列优化没法再降时间复杂度只是常数值上可能好看一点。所以实际工程里我几乎不用它这里提出来是想告诉你别被网上高级优化的名头吓到完全背包的基础写法已经是兼容最优复杂度的写法了。5. 边界条件初始化差一行答案差一个宇宙5.1 最多能装和恰好装满是两种不同的问题这是刷题最容易踩的坑。问题问背包能装下的最大价值是多少初始化全部dp[j]0。含义是容量为j的背包我一件都不装价值也是0这是合法状态。问题问恰好装满背包时的最大价值是多少初始化dp[0]0其余dp[j]负无穷。含义是容量为j的背包初始状态下没有任何组合能恰好装满只有容量0是合法的起始状态。代码差异就一行// 最多能装 for (int j 0; j V; j) dp[j] 0; // 恰好装满 dp[0] 0; const int NEG_INF -0x3f3f3f3f; for (int j 1; j V; j) dp[j] NEG_INF;负无穷的选取很讲究。我习惯用-0x3f3f3f3f而不是INT_MIN因为INT_MIN加上一个正数会溢出变成正数状态更新直接全乱。用-0x3f3f3f3f可以保证加上价值后不会溢出同时又足够小只有真正的合法组合才能覆盖它。LeetCode 322零钱兑换就是恰好装满的变体问的是最少硬币数。如果初始化按最多能装来写你永远得不出正确答案因为初始状态的0会污染所有组合。5.2 求方案数时的边界细节有的题目问的不是最大价值而是有多少种组合方式正好凑出容量V。这时候状态定义就变了dp[j]表示凑成容量j的方案总数。递推公式是dp[j] dp[j - w[i]]初始dp[0] 1。这里要注意组合和排列的区别。LeetCode 518零钱兑换II统计的是组合数不同顺序算同一种。这种写法外层物品、内层容量正序循环就能保证每个物品之间是类别的维度。如果题目要求排列数比如爬楼梯问题就要外层容量、内层物品这也是动态规划题里最容易混淆的两个循环维度。判断口诀组合数外层循环物品排列数外层循环容量。这句话我反复在各种博客和代码注释里写因为每次面试都有候选人栽在这上面。6. 变体识别一眼看穿这是完全背包的套路6.1 五种高频变体与对应方程LeetCode上至少有十几道题看起来包装得五花八门底子都是完全背包。我列一个对照表方便你复习题目/场景伪装方式DP维度转移思路零钱兑换最少硬币数dp[j]最小硬币数min(dp[j], dp[j-w]1)零钱兑换II组合方案数dp[j]方案数dp[j] dp[j-w]完全平方数最少完全平方数凑ndp[j]最小个数min(dp[j], dp[j-i*i]1)单词拆分能否由单词表拼接dp[j]布尔值dp[j]整数拆分拆成若干正整数乘积最大dp[j]最大乘积max(dp[j], dp[j-k]*k)仔细看这些题核心特征都一样某种元素的消耗硬币金额、平方数大小、单词长度某种目标值总金额、总数并且元素可以重复使用。6.2 一个通用识别框架拿到一道题我用三步判断它是不是完全背包第一步题目有没有可重复使用/无限次使用/不限制次数的描述。有进入第二步。第二步能不能抽象出物品重量和物品价值。比如零钱兑换里硬币面值就是重量1就是价值单词拆分里单词长度就是重量是否拼成就是价值。第三步确认状态维度。一维够不够还是要二维比如同时限制重量和体积。如果同时限制两个容器条件那就是二维费用背包状态改为dp[j][k]两个容量都正序循环。这三个步骤走下来基本不会看走眼。6.3 最容易翻车的两个实际场景场景一物品重量为0。完全背包里如果存在w[i]0且v[i]0的物品正序循环会陷入死循环j永远不增加。实际题目里很少给这种垃圾数据但如果你写通用模板最好加个特判。场景二输入数据不是按重量排序的而你用了贪心预处理。贪心预筛的前提是物品可无限选但如果题目实际是每个物品最多选指定次数你的预筛就可能误杀物品。所以预筛只推荐在题目明确是纯完全背包时使用。7. 从裸题到综合题我的实战排错经验7.1 一个真实踩坑记录去年我在LeetCode上刷零钱兑换的时候第一版代码是这样写的class Solution { public: int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, INT_MAX); dp[0] 0; for (int coin : coins) { for (int j coin; j amount; j) { dp[j] min(dp[j], dp[j - coin] 1); } } return dp[amount] INT_MAX ? -1 : dp[amount]; } };结果在用例coins[2], amount3时返回-1正确在coins[1,2,5], amount11时返回3正确在coins[2], amount1时返回-1也正确。一切正常直到我把初始化改成了dp[0]0, dp[j]INT_MAX并且用dp[j-coin]1计算时有一个词面量很大的测试用例爆了。查了半天原来是INT_MAX 1直接溢出了变成负数一下子min()逻辑全乱。从那以后凡是用到最小值的DP我初始化一律用一个大但不会溢出的值比如0x3f3f3f3f。这是个很小的细节但能省掉大量调试时间。7.2 竞赛里完全背包的三种考法竞赛题尤其是NOI系列和蓝桥杯省赛里完全背包有三种考法第一种裸题送分。直接给N和V物品重量价值列出来让你算最大价值。这种题纯粹考基本功代码五分钟写完。第二种套壳题。比如无限量供应的原材料每种原材料有体积和重量做成成品有收益求在限定体积和重量下的最大收益这就是二维费用完全背包。状态变成dp[j][k]两层容量循环都正序。第三种完全背包数据结构优化。常见的是物品重量和价值随着选择次数变化这种动态变化模型这时候完全背包朴素写法不够用得配合单调栈、线段树或者优先队列维护候选值。这种题在省赛以上会频繁出现。遇到第三种不要慌多数时候考察的其实是你是否能意识到它和完全背包的关联真正的优化点反而比背包本身简单。7.3 一个记忆口诀我教别人的时候总结了四句话01背包选一次内层倒序防重复。完全背包选无限内层正序任你取。组合方案外层物排列方案外层容。恰好装满别忘负无穷负无穷别用INT_MIN。这四句话背下来80%的背包题都能无障碍套用。7.4 实测性能参考我拿一个标准测试粗略测过N1000V100000随机生成物品重量在1到1000之间价值在1到10000之间。纯C实现O(NV)复杂度的完全背包跑完大约在80毫秒左右。如果用了性价比预筛物品数大概能砍掉三分之一耗时降到50毫秒左右。Python版本慢一些大概在600到800毫秒之间但数据量再翻一倍就有点悬了。所以在Python里刷LeetCode完全背包题數據規模一般都没问题但参加竞赛最好用C性能余量更大。8. 下一步怎么练按难度递进刷完这四道题理论说再多不如亲手写一遍。我自己的练法是这样按梯度来的第一梯度LeetCode 322 零钱兑换。这是一道恰好装满最小值的综合题最容易暴露你对负无穷初始化的理解。写完想想如果题目改成求最多能用的硬币数代码哪里要改。第二梯度LeetCode 518 零钱兑换II。这道题考组合数和排列数的区别。写完把内外循环交换一遍看看输出变化理解一下为什么顺序不同结果就不同。第三梯度LeetCode 279 完全平方数。这道题包装成完全背包但你要自己识别出物品是平方数、容量是target。做完之后你的识别能力会有很大提升。第四梯度蓝桥杯省赛包子凑数或者LeetCode 139 单词拆分。这两道属于判定类完全背包状态不再是数字而是布尔值逻辑更绕但万变不离其宗。我个人强烈建议按这个顺序刷不要跳跃。跳跃刷题的代价是你会跳过恰好装满的坑然后在后续所有涉及最小值的题里反复栽跟头。完全背包讲到这里核心思想其实就一句话状态转移时把还能继续选自己这件事融进递推方程剩下的就是循环方向、初始化和边界条件这三个工程细节。它不像贪心那样需要灵光一现也不像图论那样依赖大量前置知识只要把状态定义吃透代码是水到渠成的事。真正拉开差距的反而是那些藏在角落里的、由多次重复选择引发的性能问题和边界细节这些恰恰是刷题经验最值钱的部分。