最近带一个学弟刷动态规划专题碰到一个特别有意思的现象把01背包的代码贴出来容量循环从倒序改成正序代码就变成了完全背包问题的解法——也就是每种物品可以用无限次的那种。很多初次接触背包问题的人看到这里都会愣一下然后开始怀疑是不是我漏了什么边界条件。实际上这个“正序到底改了什么”背后藏着的正是动态规划里最核心的“阶段”概念。这篇接着算法奇妙屋系列往下写第二十三期专门把完全背包问题从头到尾讲透状态怎么定义、转移方程怎么推导、一维优化为什么这样写以及刷题和实际应用中会遇到的各类变种和坑点。无论你是刚开始学算法的本科生还是准备面试刷题、想巩固动态规划基础的工程师这篇应该都能给你一点新东西。1. 从“金币凑金额”讲清楚完全背包在解决什么在正式写代码之前先把问题本身聊明白。很多人背包学不进去就是因为跳过了“问题建模”这一步直接冲进转移方程里。1.1 问题定义与符号约定完全背包问题的经典描述是这样的有 n 种物品每种物品有一个重量 w[i] 和一个价值 v[i]每种物品的数量不限任意取用。现在给一个容量为 V 的背包问在不超容量限制的前提下能装下的最大价值是多少。“每种物品数量不限”是这句描述里唯一的重点。因为这个限制完全背包和01背包的区别用一个字就能概括01背包的“0/1”是指每件物品要么取、要么不取只能出现0次或1次完全背包则是0次、1次、2次、3次……直到背包装不下为止。为方便后续讨论我先约定符号后面所有推导都基于这套记号符号含义n物品种类数V背包容量w[i]第 i 种物品的重量v[i]第 i 种物品的价值dp[j]容量为 j 时能获得的最大价值我用硬币凑金额来举个具体例子。假设有三种面额的硬币2元、3元、5元背包容量或者说要凑出的总金额是 11 元每种硬币无限量使用问最多能凑出多大总价值——这里硬币的面额就是重量硬币本身的价值这里先不区分种类先感受一下模型。实际题目里物品的价值和重量可以是任意正数但核心抽象就是每个物品占用容量、带来价值在容量有限的前提下做组合优化。1.2 和01背包的区别一个关键字的差异01背包问题的决策是“第 i 件物品拿还是不拿”这是二元选择。完全背包的决策则是“第 i 件物品拿多少件”这是一个整数规划问题。很多人会以为完全背包就是把01背包的物品复制若干份再套01背包解法但这样做的问题是你不知道到底要复制多少份。如果取 k 件k 的最大值是 floor(V / w[i])最坏情况下容量达到 1e5、重量是 1那每个物品的“最大重复次数”就是 1e5复制完直接爆炸。还有一类容易混淆的问题是多重背包第 i 种物品最多取 c[i] 件。它是完全背包和01背包的中间态——有库存限制。完全背包相当于 c[i] 等于无穷大01背包相当于 c[i] 等于1。理解了这三者的递进关系遇到题目时先问一句“能不能重复取、能取几次”基本就能确定用哪套模板。1.3 换个角度这是容量约束下的“无限资源分配”我习惯把完全背包理解成另一种问题假设货架上每种商品库存无限你的背包容量有限每种商品拿几件总价值最大化。如果物品可以分割成任意小份那直接按性价比——价值除以重量——贪心排序就能解决。但题目里物品是离散的不能只拿半件所以才需要动态规划。这也是为什么 dp[j] 可以反复从 dp[j - w[i]] 转移过来同一件物品可以在多个决策阶段中反复“被选中”这正好匹配了“无限库存”的业务假设。这个理解方式对后面理解一维数组为什么要正序遍历非常关键因为它直接解释了 dp[j-w[i]] 这个状态在那个场景下的语义——它已经包含了本轮循环中再取一件物品 i 后的最优结果。2. 状态转移方程推导先写最朴素的k循环版本现在进入核心环节。完全背包的最终转移方程只有一行但如果不知道它是怎么来的遇到变种题就很容易懵。我建议所有初学者都把最朴素的版本动手推一遍。2.1 最朴素思路枚举第 i 件物品取了几件所有背包问题的起点都是二维DP。设 dp[i][j] 表示“从前 i 种物品中选择若干件放入容量为 j 的背包能获得的最大价值”。完全背包中第 i 种物品最多能取 floor(j / w[i]) 件所以最直接的做法就是枚举 kdp[i][j] max( dp[i-1][j - k * w[i]] k * v[i] )其中 k 从 0 取到 floor(j / w[i])这个式子的含义非常直白当前容量 j 下第 i 种物品要么不取k0此时等于上一层状态 dp[i-1][j]要么取 1 件、2 件……直到容量装不下。取 k 件时占用的容量是 kw[i]价值是 kv[i]剩下 j - k*w[i] 的容量交给前 i-1 种物品去决策。这个写法在数学上完全正确但复杂度太高。每一层状态都需要枚举 k最坏情况下 k 的取值数量与 V/w[i] 成正比总复杂度 O(n * V * V/w[i])当 V 稍大时根本无法运行。不过它有一个很大的好处概念清晰。看懂了这个枚举版本你就知道 dp[i][j] 到底在算什么。我手工推演一个小例子。假设 n2, V6物品1重量2价值3物品2重量3价值5。第一轮处理物品1时dp[1][2]3, dp[1][4]6, dp[1][6]9容量为6时能装下三件物品1总价值9。第二轮处理物品2时dp[2][6] 取 max(dp[1][6]9, dp[1][3]58, dp[1][0]1010)最终答案是10也就是装两件物品2。这个推演过程可以直观地看到“取多件”的含义。2.2 关键压缩从“枚举k件”到“递推一件”现在的问题是能不能不枚举 k观察上面的式子把 k0 的情况单独拆出来剩余部分可以写成dp[i][j] max( dp[i-1][j], max_{k1}( dp[i-1][j - kw[i]] kv[i] ) )再看 max_{k1} 这一项。如果我们在容量 j-w[i] 的状态下已经做过决策即 dp[i][j-w[i]] max( dp[i-1][j-w[i]], max_{t1}( dp[i-1][j-w[i] - tw[i]] tv[i] ) )那把它加上一个 v[i] 就能得到什么dp[i][j-w[i]] v[i] max( dp[i-1][j-w[i]] v[i], max_{t1}( dp[i-1][j - (t1)*w[i]] (t1)*v[i] ) )右边恰好就是 max_{k1}( dp[i-1][j - kw[i]] kv[i] )。于是dp[i][j] max( dp[i-1][j], dp[i][j-w[i]] v[i] )这个推导非常关键值得自己完整写一遍。注意一个细节第二项用的是 dp[i][j-w[i]]而不是 dp[i-1][j-w[i]]这是完全背包和01背包转移方程最本质的差异。前者状态来源是本轮已经更新过的状态意味着可以继续选择第 i 件物品后者来源是上一轮的状态意味着第 i 件物品最多选一次。2.3 复杂度分析与代码骨架优化后的时间复杂度是 O(nV)空间复杂度是 O(nV)用滚动数组可以降到 O(V)。这个复杂度在竞赛和面试中都属于“舒适区”范围——n100V1e5运算量约 1e7C 大概零点几秒Python 如果写法不够优化可能需要一两秒但通常也能接受。二维版本的代码长这样#include bits/stdc.h using namespace std; const int N 1005; const int M 100005; int dp[N][M]; int w[N], v[N]; 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 0; j V; j) { dp[i][j] dp[i-1][j]; // 不取第 i 件 if (j w[i]) { dp[i][j] max(dp[i][j], dp[i][j-w[i]] v[i]); } } } cout dp[n][V] endl; return 0; }这里的 if (j w[i]) 判断可以改进层循环起点但二维版本里这样写逻辑更清晰新手不容易漏。3. 一维滚动数组为什么必须正序遍历手推一遍就懂了掌握了二维DP后下一步就是把空间压到一维。这一步是新手最容易卡住的地方因为同一个转移方程为什么01背包要倒序、完全背包要正序很多资料只告诉你结论不告诉你原因。3.1 先回顾01背包为什么要逆序01背包的一维代码长这样for (int i 1; i n; i) { for (int j V; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }内层容量倒序遍历是为了保证在更新 dp[j] 时它参考的 dp[j-w[i]] 还是上一轮 i-1 的状态——也就是还没处理第 i 件物品时的最优解。因为 dp[j-w[i]] 的更新顺序比 dp[j] 晚当 j 从大到小时j-w[i] 一定小于 j也就是说它还没被本轮更新过所以它还是旧值。这样每件物品只可能被取一次符合01背包的约束。反过来如果正序遍历dp[j-w[i]] 会被先更新等到更新 dp[j] 时参考到的 dp[j-w[i]] 可能已经包含了“取过第 i 件物品”的状态于是会重复取同一件物品——这恰恰就是我们想要的完全背包效果。3.2 正序的直观理解允许“反悔”再取我把这句话再展开说透一点。完全背包的一维写法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]); } }为什么这样就能无限次取因为当容量 j 从小到大递增时dp[j-w[i]] 可能在本次外层循环的早期已经被更新过。比如 j w[i] 时dp[w[i]] 被更新为 dp[0] v[i]等到 j 2w[i] 时dp[2w[i]] 会参考 dp[w[i]]而 dp[w[i]] 已经不是上一轮的旧值而是本轮已经取过一件物品 i 后的新值。这样加一次 v[i]就实现了取两件再往下 j 3*w[i] 时又加一次就实现了取三件。所以正序遍历天然支持“重复取”。这里不需要刻意背“正序还是倒序”你需要记住的是状态来源 dp[j-w[i]] 在遍历到当前 j 时如果已经被本轮更新过那它就可以“携带”当前物品的信息从而允许重复取如果还是上轮值则只能取一次。3.3 手工推演一遍dp数组的变化过程纸上推演是理解动态规划最快的方式。我再用单物品例子演一遍。假设 V6只有一种物品重量3价值5dp 数组初始全0。正序遍历更新到容量 j操作当前 dp 数组j3dp[3] max(0, dp[0]5) 5[0, 0, 0, 5, 0, 0, 0]j4dp[4] max(0, dp[1]5) 5[0, 0, 0, 5, 5, 0, 0]j5dp[5] max(0, dp[2]5) 5[0, 0, 0, 5, 5, 5, 0]j6dp[6] max(0, dp[3]5) 10[0, 0, 0, 5, 5, 5, 10]注意看 j6 这一步参考的是 dp[3]而 dp[3] 在本轮已经被更新成5所以 dp[6]10等于取了两件物品。这就是完全背包“无限次取用”在一维数组里的实现机制。对比一下如果逆序遍历更新到容量 j操作当前 dp 数组j6dp[6] max(0, dp[3]5) 5[0, 0, 0, 0, 0, 0, 5]j5dp[5] max(0, dp[2]5) 5[0, 0, 0, 0, 0, 5, 5]j4dp[4] max(0, dp[1]5) 5[0, 0, 0, 0, 5, 5, 5]j3dp[3] max(0, dp[0]5) 5[0, 0, 0, 5, 5, 5, 5]逆序时 dp[6] 参考的 dp[3] 还是初始值0所以它只能取一件这就是01背包的行为。事实上我学这个知识点时就是这样在草稿纸上画了两张表才真正想明白的。如果你现在还处于“背模板”阶段强烈建议亲手推一次这个小例子只需要两分钟记忆能持续很久。3.4 一维数组的初始化陷阱一维版本写起来简单但初始化是个大坑。处理“最大价值且可以装不满”问题dp[0..V] 全部初始化为0即可。因为任何容量下都不选任何物品剩余容量空着也是合法状态。处理“恰好装满”问题dp[0]0dp[1..V] 初始化为负无穷大通常用 -0x3f3f3f3f 替代。因为只有容量0是“恰好装满”的合法起点其他容量无法由“不选任何物品”凑成刚好装满。转移方程不变最后如果 dp[V] 还是负数说明无法恰好装满。这个初始化陷阱在面试中很容易被考到而且也会在一些看似“只是求最大值”的变种题中埋着稍后会细讲。4. 四类高频变种恰好装满、方案数、最小价值、二维容量完全背包最常考的并不是裸的“最大价值”而是它的几种变体。掌握变体的本质比背模板重要得多。4.1 变种一恰好装满时的最大价值题目如果要求“背包装满”而容量 V 可能无法达到那结果可能是“无解”。处理方式就是前面提到的dp[0]0dp[1..V] 初始化为 -INF转移方程照旧。假设初始化 dp 为 -0x3f3f3f3fdp[0]0那么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]); } } if (dp[V] 0) printf(无解\n); else printf(%d\n, dp[V]);这里有个很微妙的点dp[V] 如果一直是 -INF说明没有任何组合能刚好填满容量 V。但如果有物品的重量为0那 dp[V] 可能会被 dp[V] v[i] 更新成正常值不过现实中很少出现重量0的物品竞赛题也很少这么出。顺便说一句为什么用 -0x3f3f3f3f 而不是 INT_MIN因为 INT_MIN 在运算 dp[j-w[i]] v[i] 时如果 v[i] 是正数可能加法溢出变成正数导致错误的“有解”判断。-0x3f3f3f3f 这个值足够小加上正常范围内的价值也不会溢出是竞赛里约定俗成的“负无穷”。4.2 变种二计数类方案数问凑出容量 V 的方案数有多少种。这里要将 max 换成加法dp[j] 表示凑出金额/容量 j 的方案数转移方程是dp[j] dp[j - w[i]]外层循环物品种类内层正序容量。初始 dp[0]1其余为0。memset(dp, 0, sizeof(dp)); dp[0] 1; for (int i 1; i n; i) { for (int j w[i]; j V; j) { dp[j] dp[j - w[i]]; } }注意这么写得到的是组合数也就是说“先取物品1再取物品2”和“先取物品2再取物品1”只算一种方案。LeetCode 518零钱兑换II就是这类题1277 之后也有不少类似变体。如果你遇到的是“排列数”——比如爬楼梯的变体每次可以走 1 步或 2 步问多少种走法——那就需要把外循环改成容量、内循环改成物品这样才能保证顺序不同的方案被分别计数。排列的组合怎么区分记住一句话外层循环是“阶段”谁先被枚举谁就先定下来。物品在外层时物品种类的顺序被固定自然不会产出“交换顺序”的新方案容量在外层时每一步都在所有物品里重选所以不同顺序就成了不同方案。4.3 变种三最小价值/最少件数这是非常常见的一类典型题目是零钱兑换LeetCode 322给定若干面额的硬币无限量问凑成总金额 amount 所需的最少硬币数。这类问题把 max 换成 min 就行dp[j] min(dp[j], dp[j - w[i]] 1)初始化 dp[0]0其余为一个足够大的数 INF。输出时判断 dp[amount] 是否仍然等于 INF是则返回 -1。C 实现const int INF 0x3f3f3f3f; vectorint dp(amount 1, INF); dp[0] 0; for (int i 0; i coins.size(); i) { for (int j coins[i]; j amount; j) { dp[j] min(dp[j], dp[j - coins[i]] 1); } } int ans (dp[amount] INF) ? -1 : dp[amount];这里最需要注意的是最小化问题里“不超过容量”的语义通常没意义。如果你初始化 dp 全部为0dp[j] min(dp[j], dp[j-w[i]] 1) 的结果永远是0因为“不选任何物品”的代价是0比任何正数都小。所以要求“恰好凑成”时初始化必须用 INF把不合法状态拦在外面。4.4 变种四二维容量约束有些题同时给两个约束比如重量和体积、长度和宽度。这时把一维 dp 扩成两维dp[j][k] 表示重量为 j、体积为 k 时的最大价值转移方程dp[j][k] max(dp[j][k], dp[j - w[i]][k - c[i]] v[i])两个容量维度都需要正序遍历。复杂度升到 O(n * W * V)实际使用时要看数据范围是否允许。for (int i 1; i n; i) { for (int j W; j 0; j--) { // 注意这里可能是逆序取决于题目语义 for (int k V; k 0; k--) { if (j w[i] k c[i]) { dp[j][k] max(dp[j][k], dp[j - w[i]][k - c[i]] v[i]); } } } }二维容量的更新方向也要根据“物品能不能重复取”来定能重复取就正序不能重复取就逆序。原理和一维时完全一样。4.5 多重背包完全背包的“限量版弟弟”多重背包不容忽略因为它和完全背包在题目里经常一起出现。多重背包是第 i 种物品最多取 c[i] 件既不是1件也不是无限件。最朴素的办法是拆成01背包把 c[i] 件物品逐件拆开但这样复杂度会乘上 c[i] 的总和可能很大。更好的方式是二进制拆分把 c[i] 拆成 1、2、4、8……和剩余部分例如 13 拆成 1、2、4、6其中1、2、4、6可以组合出0到13的所有整数。这样每组看作一种新物品套01背包的逆序循环即可。拆分逻辑for (int i 1; i n; i) { int cnt c[i]; for (int k 1; k cnt; k 1) { // 将 k*v[i], k*w[i] 作为一个新物品加入 cnt - k; } if (cnt 0) { // 将 cnt*v[i], cnt*w[i] 作为一个新物品加入 } }一句话总结拿到题先判断“能不能重复取、能取几次”——能取无限次用完全背包能取1次用01背包取有限次用多重背包二进制拆分转01背包。这三个模型是同一个家族区别只在循环方向和拆法。5. 实战题目链路与最容易翻车的几个细节理论讲得再多不落到题目上都是空的。我按循序渐进的方式推荐几条实战链路顺便把调试时最容易被忽略的坑列出来。5.1 从入门到进阶的四道题如果从零刷完全背包我建议按这个顺序完全平方数LeetCode 279把每个平方数 1、4、9、16……当作物品重量是平方数值价值是1问凑成 n 的最少数量。这是“最少件数无限取”的双重变种拿来熟悉完全背包的 min 转移非常合适。零钱兑换LeetCode 322硬币无限量凑成 amount 的最少硬币数。比279稍微抽象一点因为硬币面额不是顺序排列的需要自己建物品列表。零钱兑换IILeetCode 518求凑成目标金额的方案数用来理解“组合数 vs 排列数”的循环顺序问题。单词拆分LeetCode 139表面上是字符串题实际上也是完全背包的思想——能否从字典中取若干个单词拼接成给定字符串。这里的“容量”是字符串前缀长度转移时不是减重量而是检查一段后缀是否是字典中的单词这是完全背包的一种进阶表现形式。刷完这四道你对完全背包的理解基本就过关了。别小看循序渐进直接去刷一堆难题反而容易打击信心。5.2 评测环境里最容易翻车的三个点我在给学弟答疑和帮人排查代码的时候发现完全背包的报错高度集中在三个点上第一循环方向反了。如果把完全背包写成了逆序结果会接近01背包即每个物品只能取一次最终答案偏小。排查方法是构造一个只有一种物品、容量是重量三倍的样例答案应该是三件物品的价值如果你算出来只有一件就是循环方向写反了。第二数组越界。内层循环如果从 w[i] 开始到 V按理说不会访问 dp[j-w[i]] 的负数下标。但有些题给了重量为0的物品此时 j-w[i] 等于 j不会越界却会形成自更新。如果数据范围允许建议把重量为0的物品单独处理或者在转移前判断一下。第三INF 选错。上面提到过用 INT_MIN 做负无穷时加上正数可能溢出变成正数导致“无解”的状态被误判为有解。C 里用 -0x3f3f3f3fPython 里用 float(-inf)Java 里用 Integer.MIN_VALUE / 2注意别直接拿 MIN_VALUE 做加法。一个重要提示写背包问题时先确定初始化状态和循环顺序再写转移方程。很多同学的代码问题不在转移方程本身而是外层循环和内层循环写的顺序不对、初始状态不对导致答案偏差。5.3 关于循环方向的临场判断技巧这里分享一个我自己用了很多年的判断方法比死记模板可靠得多。写代码之前先给自己三十秒想一想在遍历到容量 j 时转移参考的 dp[j - w[i]]到底是“上一轮物品循环留下的旧值”还是“本轮物品循环已经更新过的新值”如果是旧值 —— 说明物品 i 还没被处理过不可能重复取用应该逆序遍历。如果是新值 —— 说明物品 i 在本轮已经处理过状态里可能已经包含了一件或多件物品 i可以继续取因此正序遍历。这个方法适用于所有背包问题包括01背包、完全背包、多重背包的验证。我自己遇到没见过的变种题时也会在草稿纸上按这个逻辑推一遍基本不会再出错。6. 完全背包在现实业务和面试中的真实打法最后聊点轻松的谈谈完全背包在现实业务里到底长什么样。很多人觉得背包问题只存在于算法题里实际上它离业务并不远。6.1 硬币支付系统里的贪心失效场景最经典的场景是找零问题。比如一个系统中硬币面额有1元、5元、11元要凑出15元。贪心算法会优先选最大的11元然后补4个1元一共5枚硬币。但实际上最优解是 555只需要3枚硬币。这就是贪心在“面额不满足整除关系”时失效的经典反例。现实中某些支付系统的优惠券模板、代金券组合也经常出现类似情况券的面额不完全按整除关系设计那么下单系统在做最优抵扣计算时就需要用完全背包来兜底而不能简单地对券面额排序贪心。6.2 集装箱配载与广告投放的资源分配更接近动态规划本质的应用是资源分配类问题。假设一个集装箱车队中每辆集装箱车的容量相同每个客户的货物可以不限件数地装车问如何配载才能让整批车辆的总价值最大。这个就是典型的背包容量固定、物品种类有限但数量不限的完全背包问题。广告投放里也能见到类似模型假设你有固定预算每个投放渠道的“每次投放花费”和“预计曝光量”是固定的渠道不限投放次数问如何分配预算才能让总曝光量最大。把预算当容量、单次花费当重量、曝光量当价值这就非常自然地变成一个完全背包问题。当然真实业务的约束比模型复杂但问题建模的第一步通常是可以用背包框架去抽象。6.3 算法竞赛和面试里更常出现的形态竞赛和面试里完全背包很少会原样裸考通常会把“可重复选”这个信息藏在描述里。例如“给你一个由不同整数组成的数组 nums和一个目标整数 target请你从 nums 中找出并返回总和为 target 的元素组合的个数”“不限制使用 nums 中每个元素的次数”。像这种“不限制次数”的题基本就是在提醒你可以往完全背包方向想。面试时的正确路线是先把问题翻译成背包语言——确定容量是什么、物品是什么、重量是什么、价值是什么、每件物品能否重复使用。翻译正确了模板自然就出现了翻译不对套什么模板都是错的。关于这个系列我后面应该还会抽一期专门把“背包问题家族”做一个横向对比把01背包、完全背包、多重背包、分组背包、依赖背包全部放到一张图里梳理清楚。如果这篇对你有帮助或者你在调试时遇到其他稀奇古怪的问题欢迎在评论里留言分享我会尽量回复。