零钱兑换、买菜找零、凑面额、物品无限拿——这些题面背后站着的其实是同一个模型完全背包。很多人第一次接触完全背包问题是在刷题网站上被“每件物品可以取无限次”这句话绊了一下然后照着题解敲出两行循环AC 了但心里并不清楚为什么偏偏要正序遍历容量也不清楚那个“优化过程”里每一步到底砍掉了什么。我自己当年也是这么过来的三层循环看一眼就懵二维数组推了两小时一维滚动数组抄下来能跑但不敢改一个字符。所以这篇就把完全背包从最笨的写法一路推到工程上真正好用的写法每一步都讲清楚“为什么这么改”中间穿插我在刷题和写业务代码时踩过的坑。不管你是刚学动态规划的新手还是已经把模板背熟但想搞明白循环方向语义的人顺着看下来应该都有收获。完全背包问题的优化过程本质上是一次“去掉重复枚举”的思维训练而不是背两行代码。1. 把题目翻译成人话完全背包到底在求什么1.1 从一个找零钱的场景切入先从最生活化的场景说起。你手里有三种面额的硬币1 元、3 元、4 元每种的数量都管够现在要凑出 6 元最少用几枚第一反应可能是贪心先拿最大的 4 元剩下 2 元用两枚 1 元一共 3 枚。但如果你多看一眼就会发现3 元加 3 元只需要 2 枚答案比贪心还少一枚。贪心在这里翻车的原因很简单面额之间不构成整除关系时“先拿大的”并不保证剩下的部分能被最优地填满。4 元拿走之后剩下的 2 元只能用两个 1 元填而放弃 4 元改用两个 3 元反而更省。这个反例说明了一件事要拿到真正的最优解必须把“每种面额用几枚”的所有组合都考虑一遍。面额少的时候可以暴力枚举一旦面额种类变多、目标金额变大枚举量就会爆炸。这时候就需要一种能复用子问题结果的算法把重复计算的部分缓存下来——这正是动态规划登场的地方也是完全背包问题的起点。提示很多人对完全背包的第一印象是“背包”两个字以为必须和“容量、价值”挂钩。实际上凡是“无限次取用、凑目标值、求最优”的问题都是它的马甲别被字面吓住。1.2 “无限”这两个字带来的连锁反应完全背包和 01 背包的唯一区别就是每件物品可以取任意多次。听起来只是改了半句话但它引发的连锁反应贯穿了状态定义、转移方程、循环方向、初始化方式甚至影响到能不能做空间压缩。在 01 背包里第 i 件物品只有“拿”和“不拿”两种决策状态转移天然是二选一。而完全背包里第 i 件物品有“拿 0 件、拿 1 件、拿 2 件……”无穷多种决策如果老老实实把每种件数都枚举一遍就多出一层循环复杂度直接从 O(nV) 涨到 O(nV²) 量级。更关键的是这个差别会渗透到空间压缩环节。01 背包压缩成一维数组之后容量必须倒序遍历完全背包恰好相反容量必须正序遍历。这个方向差异是初学者最容易写错、也最容易被面试官追问的点第 4 章会用一个手推表格把它彻底讲透。1.3 完全背包的识别清单我整理了一份识别清单遇到新题先对照一下命中大部分特征的基本就是完全背包或者它的变体每种“物品”面额、道具、步长、字符串片段可以取用的次数不受限制。有一个明确的目标量容量、金额、长度、分数。要求的是某个最优值最大价值、最少数量或者方案总数或者“能不能凑出来”的可行性。约束规模通常在容量几千到几万、物品几百到几千这个量级正好卡在需要 O(nV) 才能过。常见变形包括零钱兑换最少硬币数、零钱兑换 II组合方案数、组合总和 IV排列方案数、爬楼梯的进阶版每次可以走 1 到 k 级、以及“用无限个给定数字能凑出的最小不可表示数”这类偏数学的题。它们的状态定义大同小异区别只在初始化、转移方向取 max 还是 min以及计数的去重方式上后面会逐个拆开讲。2. 朴素解法先把状态方程写对再谈优化2.1 状态定义为什么是“前 i 种物品”动态规划的第一步永远是定状态而状态定义的核心诉求是“无后效性”一旦状态确定后面的决策就不再依赖它是怎么来的。对于完全背包标准定义是dp[i][j] 表示只考虑前 i 种物品在容量不超过 j 的前提下能获得的最大总价值。把“前 i 种”当作阶段好处是每次决策只围绕第 i 种物品展开前 i-1 种的所有结果已经打包好放在 dp[i-1][*] 里不用再去关心具体拿过哪些。这个“按物品种类划分阶段”的思路是背包类问题的通用骨架后面无论怎么优化都不会变。另一种常见定义是“容量恰好为 j”两者在求最大值时结果可以互相转换但初始化方式不同。新手最容易在这里犯浑用“不超过 j”的定义却写了“恰好装满”的初始化或者反过来导致答案偏大或偏小。我在 6.2 节专门用一张表把两种定义的初值对照列清楚这里先记住“不超过 j”的版本初值全部为 0 就够了。2.2 三层循环的暴力版本有了状态定义最直白的转移就是把“第 i 种物品拿几件”枚举出来// 朴素版dp[i][j] 前 i 种物品、容量不超过 j 的最大价值 // w[i] 为体积v[i] 为价值V 为总容量 int dp[N][V 1]; memset(dp, 0, sizeof(dp)); for (int i 1; i n; i) for (int j 0; j V; j) for (int k 0; k * w[i] j; k) dp[i][j] max(dp[i][j], dp[i - 1][j - k * w[i]] k * v[i]);这段代码逻辑是通的枚举第 i 种物品拿 k 件剩下的容量 j - k*w[i] 完全交给前 i-1 种物品处理。但它慢得离谱我们来算一下账。对第 i 种物品内层 k 的循环次数是 j / w[i] 1。把所有 i 和 j 加起来总操作次数大约是当所有物品体积都是 1 时最坏情况Σᵢ Σⱼ (j 1) ≈ n·V²/2也就是 O(nV²)。一般情况是 O(nV V²·Σ(1/wᵢ))介于 O(nV) 和 O(nV²) 之间。取 n 100、V 1000最坏情况下要跑五千万次左右勉强能过一旦 V 涨到 10⁴直接起飞。所以优化的目标很明确干掉那层枚举件数的 k 循环。2.3 边界和初始化先钉死在动手优化之前把边界钉死。用“不超过 j”的定义时dp[0][j] 表示“一件物品都不考虑、容量不超过 j”的最大价值显然是 0所以整张表初始化为 0 就完事。容量 j 从 0 开始遍历是为了覆盖“容量小于任何物品体积”的情况这时候循环体自然不执行dp[i][j] 直接继承 dp[i-1][j]。如果用“容量恰好为 j”的定义dp[0][0] 0而 dp[0][j] (j 0) 应该是负无穷表示“一件不拿却要恰好装满容量 j”是做不到的。求最小值问题比如最少硬币数则反过来dp[0] 0其他位置设成正无穷。注意负无穷不要直接用 INT_MIN因为后续要参与加法运算INT_MIN 加一个正数会溢出成很大的正数结果直接错乱。竞赛和工程里通用的做法是取 0x3f3f3f3f约 10⁹它足够大、两两相加不溢出还能用 memset 一次性填满。3. 第一刀优化干掉枚举件数的那层循环3.1 关键观察后面的项吃掉了前面的项优化的突破口在于观察转移方程里那些“长得像”的项。把 dp[i][j] 按 k 展开写出来dp[i][j] max( dp[i-1][j], dp[i-1][j-w] v, dp[i-1][j-2w] 2v, dp[i-1][j-3w] 3v, ... )再把 dp[i][j-w] 按同样的方式展开dp[i][j-w] max( dp[i-1][j-w], dp[i-1][j-2w] v, dp[i-1][j-3w] 2v, ... )现在仔细对比。如果把第二个式子的每一项都加上 v就得到dp[i][j-w] v max( dp[i-1][j-w] v, dp[i-1][j-2w] 2v, dp[i-1][j-3w] 3v, ... )你会发现这串东西和第一个式子里从第二项开始的部分完全重合。也就是说第一个式子里 k ≥ 1 的全部情况已经被 dp[i][j-w] v 一个式子概括了。于是转移方程瞬间瘦身成两行dp[i][j] max( dp[i-1][j], dp[i][j-w] v )当 j ≥ w这就是完全背包最核心的转移方程。复杂度从 O(nV²) 直接降到 O(nV)因为每个状态只做两次比较。3.2 一个字符的差别两种完全不同的模型这里有一个必须刻进肌肉记忆的细节加号前面是 dp[i][j-w] 还是 dp[i-1][j-w]。写成 dp[i][j-w] v含义是“在已经考虑过第 i 种物品、容量 j-w 的方案上再塞一件第 i 种物品”。因为那一层已经允许拿第 i 种了所以可以反复叠加这正是“无限件”的来源。写成 dp[i-1][j-w] v含义是“在完全不考虑第 i 种物品的方案上塞一件第 i 种物品”塞完之后第 i 种就不能再出现第二次了于是退化成 01 背包。我见过不少人把这两个写法当成“等价变形”结果在 01 背包和完全背包之间反复横跳死都找不到错。其实记住一句话就行下标里出现 i 而不是 i-1代表“本件物品已经考虑过允许重复”。// 优化后二维版本 for (int i 1; i n; i) for (int j 0; j V; j) { dp[i][j] dp[i - 1][j]; if (j w[i]) dp[i][j] max(dp[i][j], dp[i][j - w[i]] v[i]); }3.3 手推一遍确认它真的对光看公式容易骗自己我习惯拿个小例子手推一遍。设有一种物品体积 2、价值 3总容量 5用上面的二维写法走一遍状态计算过程结果dp[1][0]继承 dp[0][0] 00dp[1][1]继承 dp[0][1] 0j 2 不转移0dp[1][2]max(dp[0][2], dp[1][0] 3) max(0, 3)3dp[1][3]max(dp[0][3], dp[1][1] 3) max(0, 3)3dp[1][4]max(dp[0][4], dp[1][2] 3) max(0, 6)6dp[1][5]max(dp[0][5], dp[1][3] 3) max(0, 6)6结果 6正好是拿两件体积 4、价值 6的方案符合“容量不超过 5 时的最优解”。注意 dp[1][4] 用到了 dp[1][2] 的值而 dp[1][2] 已经是“拿过一件之后”的结果所以这里实实在在地叠了第二件无限次取用的效果体现出来了。实操心得手推表不要嫌麻烦挑最简单的一组数据推三五格你对转移方程的信任度会完全不一样。我调试背包类题目时第一步永远是把样例的前几行打印出来肉眼核对转移路径。4. 第二刀优化把二维表压成一维数组4.1 观察依赖关系找到可以原地覆盖的理由二维版本里dp[i][j] 只依赖两个值同列的上一行 dp[i-1][j]以及本行左侧的 dp[i][j-w]。这意味着如果我只保留一维数组 dp[j]并在计算 dp[j] 时保证 dp[j-w] 已经被更新成“本行”的值就能原地覆盖不需要保留整张二维表。关键就在于遍历顺序。如果 j 从 0 到 V 正序遍历那么当计算到 dp[j] 时dp[j-w]下标更小早就被这一轮更新完了它携带的正是第 i 种物品可以被重复取用的信息。这正好是我们想要的语义。于是空间复杂度从 O(nV) 降到 O(V)代码也精简到短短两行// 一维版本正序遍历容量 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]);4.2 正序与倒序的手推对照“完全背包正序、01 背包倒序”这句话很多人背得滚瓜烂熟但未必知道为什么。用上面那组数据体积 2、价值 3、容量 5把两种顺序都跑一遍差距一目了然。正序遍历完全背包j计算过程dp[j]0,1j 2跳过02max(0, dp[0] 3)33max(0, dp[1] 3)34max(0, dp[2] 3) max(0, 6)65max(0, dp[3] 3) max(0, 6)6倒序遍历01 背包语义j计算过程dp[j]5max(0, dp[3] 3)34max(0, dp[2] 3)33max(0, dp[1] 3)32max(0, dp[0] 3)3正序拿到 6两件倒序拿到 3一件。原因就在 dp[j-w] 的来源倒序遍历时容量小的格子还没被本轮更新读取到的还是上一轮未考虑第 i 种物品的旧值因此每件最多用一次。一句话概括正序读的是本行能重复拿倒序读的是上一行只能拿一次。把这句话和代码绑在一起记比死记“正序倒序”靠谱得多。注意改成正序之后循环下界可以直接从 w[i] 开始因为 j w[i] 时转移式子根本不成立下标会变负。如果你习惯从 0 开始遍历记得加上 j w[i] 的判断但别把下标写成负数那是未定义行为不是“返回 0”。4.3 一维写法里几个容易混的等价形式实战中我见过几种写法它们语义相同但风格不同挑一个顺手的一直用就行混用容易出错for (j w[i]; j V; j) dp[j] max(dp[j], dp[j-w[i]] v[i]);最简洁推荐。for (j 0; j V; j) if (j w[i]) dp[j] max(dp[j], dp[j-w[i]] v[i]);多一次判断可读性好一点性能上没差别。把 max 换成 min、把初值改成 0x3f3f3f3f就变成“最少件数”模型循环结构完全不动。还有一个细节一维压缩之后外层物品循环和内层容量循环的先后顺序是有讲究的而且这个讲究在“求方案数”的场景下会直接决定答案对不对第 6 章会专门讲这个陷阱。5. 第三刀常数级优化与特殊场景的处理5.1 能扔就扔无效物品剪枝与容量压缩O(nV) 已经是一维正序的最佳数量级但常数还有压缩空间尤其是 V 特别大、物品特别杂的时候体积超过 V 的物品直接丢弃它一辈子都放不进去留着只会浪费一圈循环。同体积物品只留价值最大的如果两件物品体积相同价值低的那件在任何最优解里都不会被选中可以用价值高的完全替代它直接删掉能减少物品数。支配关系淘汰如果物品 a 的体积是物品 b 的体积的整数倍 k而 a 的价值还不如 b 的 k 倍那 a 就是被 b 支配的可以扔掉。举个例子体积 4、价值 5 的物品对比体积 2、价值 3 的物品两件 2 顶一件 4价值 6 5所以前者永远不该出现。按体积的最大公约数缩放如果所有物品体积的最大公约数是 g那么任何方案的总容量一定是 g 的倍数容量不是 g 倍数的状态永远不可能被凑出来。把 V 除以 g、每个 w[i] 除以 g规模能直接缩小 g 倍。这个技巧在 V 很大、体积又都是偶数或 5 的倍数时特别好用。// 缩放示例g 为所有物品体积的最大公约数 int g w[1]; for (int i 2; i n; i) g std::gcd(g, w[i]); if (g 1) { V / g; for (int i 1; i n; i) w[i] / g; }5.2 完全背包不需要二进制拆分别再搞混网上讲优化经常把“二进制拆分”和“单调队列优化”摆在完全背包旁边导致不少人以为完全背包也要拆。这里必须澄清二进制拆分是给多重背包用的完全背包不能拆也没必要拆。二进制拆分的逻辑是某件物品最多拿 c 件那就把它拆成 1、2、4、8……以及最后一个余数共 O(log c) 组每组当成一个 01 物品用 01 背包的倒序循环跑。这样做能把三重循环压成 O(V·Σlog c)。但完全背包的件数限制是无穷你没法把无穷拆成有限组所以这条路走不通。那完全背包为什么也不需要额外手段因为它的一维正序写法已经是 O(nV) 了每个状态 O(1) 转移没有“枚举件数”的残余。你真正需要单调队列的场合是多重背包每件限 c 件那种 dp[i][j] max_{0≤k≤c} (dp[i-1][j-kw] kv)因为限制条件破坏了“用本行结果替换”的等价性只能另寻出路。模型件数限制常用优化复杂度01 背包每件 1 次一维倒序O(nV)完全背包无限次一维正序无需拆分O(nV)多重背包每件 c 次二进制拆分O(V·Σlog c)多重背包每件 c 次单调队列O(nV)5.3 按余数分类看滑动窗口的视角如果你对多重背包的单调队列优化也感兴趣这里给一个统一的理解框架它同样能解释完全背包的转移为什么这么“便宜”。把 dp[i][j] 的转移写成对同类余数的形式。取 j r t·wr 是 j 对 w 取模的余数t 是倍数那么dp[i][r t·w] max_{0 ≤ s ≤ t} ( dp[i-1][r s·w] - s·v ) t·v这个式子的意思是对固定的余数 r我们实际上是在一个长度为 t1 的滑动窗口里取最大值窗口里的第 s 个元素是 dp[i-1][rs·w] - s·v。完全背包的窗口右端一路延伸到 0件数不限所以最新的那个值可以直接复用退化成一个 O(1) 的递推而多重背包的窗口长度被限制在 c1必须用单调队列维护才能做到 O(1) 摊还。这个视角的价值在于它把“为什么完全背包能压到一维正序、多重背包却要上单调队列”这件事讲圆了——限制条件不同窗口形态就不同。理解了这一层你再看那些用同余类分组的题心里就有图了。实操心得单调队列优化的代码很长我在比赛里从来不默写而是先把朴素三重循环的写法写出来对拍确认正确之后再替换成队列版本。能靠 O(nV) 解决的场景绝不主动上单调队列给自己添堵。6. 计数与可行性变体里的高频坑6.1 组合数还是排列数循环顺序决定一切同样是求方案数循环嵌套顺序不同得到的是完全不同的两种计数外层物品、内层容量正序得到的是组合数顺序不同的选取被视作同一种方案。外层容量、内层物品得到的是排列数同一个组合的不同排列会被重复计数。拿面额 [1, 2]、目标金额 3 举例。组合视角下只有两种111 和 12排列视角下有三种111、12、21。差别的来源是物品放在外层时一件物品被处理完之后就不会再回头被“换到前面去”所以 (1,2) 和 (2,1) 只会产生第一种形态而容量放在外层时每个容量位置都会重新扫一遍所有物品先后顺序被区分了。// 组合数外层物品内层容量正序 long long dp[V 1] {1}; // dp[0] 1 for (int i 1; i n; i) for (int j w[i]; j V; j) dp[j] dp[j - w[i]]; // 排列数外层容量内层物品 long long dp[V 1] {1}; for (int j 1; j V; j) for (int i 1; i n; i) if (j w[i]) dp[j] dp[j - w[i]];注意方案数很容易爆 int目标容量上千、物品几十种的时候结果可能是指数级必须用 long long必要时还得取模。我吃过一次不取模的亏数据规模不大就溢出成负数了排查了半天。6.2 恰好装满与不要求装满的初值对照这是初学者翻车率最高的地方之一直接上表问题类型状态定义dp[0] 初值其他位置初值取值方式最大价值不限装满容量不超过 j00max最大价值恰好装满容量恰好为 j0-0x3f3f3f3fmax最少件数恰好装满容量恰好为 j00x3f3f3f3fmin方案数恰好装满容量恰好为 j10加法核心原则只有一条初值代表“什么都不取”时的合法状态。什么都不取时容量为 0这是唯一合法的起点其余容量在“恰好”语义下都是不可达的所以用无穷大或无穷小标记而在“不超过”语义下容量为 j 也可以什么都不取价值是 0所以全填 0。设计到“恰好”语义时最后如果 dp[V] 仍然是那个无穷值说明目标无法凑出代码里要显式处理这种情况不要直接把无穷值当答案输出。6.3 常见问题速查表我把这些年见过的报错和症状整理成一张表卡住的时候按症状反查比一行行看代码快得多症状最可能的原因修复方式结果是单件方案的最优值容量写成了倒序退化成 01 背包完全背包改成 j 从 w[i] 到 V 正序答案偏大恰好装满的问题用了全 0 初值除 dp[0] 外填 -0x3f3f3f3f答案偏小或出现莫名其妙的负数用 INT_MIN 做无穷小参与加法溢出换成 -0x3f3f3f3f方案数比预期多外层容量内层物品把排列当成了组合交换循环物品放到外层运行超时还留着枚举件数的 k 循环用 dp[i][j-w]v 替换三重循环数组越界崩溃内层从 0 开始但没判断 j w[i]下界改成 w[i]或补上 if 判断结果对但很慢物品没去重、没剪枝删掉体积大于 V 的物品同体积留最优7. 从零写一遍四个可直接抄的模板7.1 四个模板代码把前面所有内容收口给你四段能直接复制去用的代码每个模板只改了初始化和取最值的方式循环骨架完全一致。模板一最大价值不限装满int dp[V 1] {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]); // 答案dp[V]模板二最少件数恰好装满const int INF 0x3f3f3f3f; vectorint dp(V 1, INF); dp[0] 0; for (int i 1; i n; i) for (int j w[i]; j V; j) if (dp[j - w[i]] ! INF) dp[j] min(dp[j], dp[j - w[i]] 1); // 答案dp[V] INF ? -1 : dp[V]模板三组合方案数恰好装满const int MOD 1000000007; vectorlong long dp(V 1, 0); dp[0] 1; for (int i 1; i n; i) for (int j w[i]; j V; j) dp[j] (dp[j] dp[j - w[i]]) % MOD; // 答案dp[V]模板四可行性判断vectorchar dp(V 1, 0); dp[0] 1; for (int i 1; i n; i) for (int j w[i]; j V; j) dp[j] dp[j] || dp[j - w[i]]; // 答案dp[V] 为真表示可凑出7.2 用一个小例子验证四个模板拿面额 [1, 3, 4]、目标 6 来跑一遍对照手算结果模板手算答案说明最大价值把面额当价值6容量不超过 6面额 411 或 33 都是 6最少件数233组合方案数3111111、1113、33可行性真能凑出手算和代码一致说明转移逻辑是通的。这套对照法我在写新题时经常用先用纸笔算出小规模答案再让代码跑同样的输入两边对不上就说明某处状态定义有偏差。7.3 对拍验证与调试习惯如果题目复杂到难以手算就写一份暴力搜索做对拍。暴力的写法很朴素递归枚举每种物品拿几件把所有可行组合搜一遍取最优规模设小一点容量不超过 20、物品种类不超过 4然后随机生成几百组数据让两个程序跑同一份输入并比对输出。一旦发现分歧把那组数据单独拿出来手推通常三五分钟就能定位到是循环方向还是初始化的问题。另外我强烈建议在调试时打印一行中间状态。一维数组的缺点是看不到历史所以当答案不对时我习惯先打印出每个物品处理完之后整张 dp 数组的样子逐轮对比一眼就能看出是哪一轮开始偏的。这个习惯帮我省下的时间远超打印语句本身的成本。我在实际刷题和写业务代码时最大的体会是完全背包真正难的地方从来不是写代码而是想清楚“重复取用”这层语义在数组里的表现形式。你不需要背正序和倒序只需要问自己一句——我现在读到的 dp[j-w]它代表的是“这件物品还能再拿一次”的状态还是“这件物品已经用完了”的状态答案清楚了循环方向自然就写对了。至于那些进阶优化等把 O(nV) 的正序写法写到闭着眼睛都不出错再去碰滑动窗口和同余类分组也不迟。