动态规划背包问题全解析：从01背包到多重背包的优化与细节

写这篇文章之前，先问一个问题：为什么背包问题被称为动态规划入门的“分水岭”？因为代码往往短到只有两三行for循环，背下来很容易，可一旦题目稍微变形——“恰好装满”“求方案数”“输出具体方案”……立刻翻车。这个现象我见得太多了。

很多人学背包问题，上来就背转移方程，结果是背一道忘一道。真正决定你能不能拿下这块内容的核心，不是公式，是搞懂公式是怎么“长”出来的。这篇我打算用一篇完整的长文，把动态规划（DP）里的背包问题从头到尾捋一遍，包括01背包、完全背包、多重背包，以及空间优化背后的“倒序”原理，最后再讲讲初始化、方案数和回溯这类容易被忽略的细节。无论你是刚接触DP，还是刷题时在背包上卡过几次，这篇文章应该都能让你少走不少弯路。

1. 先把“动态规划”四个字翻译成人话：状态、转移、最优子结构

想理解背包问题，先得把“动态规划”这层窗户纸捅破。很多教材一上来就是“最优子结构”“重叠子问题”这些术语，直接劝退。其实动态规划没有那么玄，它本质上就是三件事：定义状态、写出转移、确定边界。

1.1 动态规划不是“套路”，是一套思维流程

我给第一次接触DP的同学打过一个比方：想象你是个预算有限的自助餐食客，面前摆着一排菜品，每道菜有价格（代价）和饱腹度（价值）。你的任务是花固定的钱，吃到最大饱腹度。最笨的办法是把所有组合全列出来——可菜品一旦变多，2的N次方种组合会让你当场去世。

动态规划的思路是另一种玩法：我不看“全组合”，我只关心一件事——“花X块钱时，最多能吃到多少饱腹度”。我先算花1块、2块、3块……一点点推上去，花X块的最优解，永远是从“花更少钱的最优解”加上“新吃的一道菜”推出来的。这就是状态转移。

在这个比方里，“花X块钱时能吃到的最大饱腹度”就是状态。你的计算过程就是状态转移方程。你不需要关心具体吃的是哪几道菜，只关心“这个预算下的最优值”——这就是DP和暴力的本质区别：DP放弃穷举方案，只存最优答案，并让这个答案能通过递推被构造出来。

1.2 为什么暴力枚举不行，DP却行

要回答这个问题，得先看暴力为什么爆炸。假设有20件物品，每件都有“拿/不拿”两种选择，总共有2的20次方大约100万种情况，看起来还能忍。但物品数量来到50时，2的50次方已经是个天文数字；算法题里动辄看到n=100甚至n=1000的背包数据范围，暴力枚举直接不可能。

DP能用是因为背包问题满足两个特征：

• 最优子结构：前i件物品、容量j的最优解，可以由前i-1件物品、某个更小容量的最优解推导出来；
• 重叠子问题：不同选择路径最终会回到同一个“前i件、容量j”的子问题上，与其每次重新算，不如存下来。

这两个条件成立，DP才有效。这也是为什么DP不是万能的——不满足最优子结构的问题，硬套DP反而会错。

2. 01背包：从朴素二维DP到完整代码的一次性搞懂

背包问题有很多变种，但01背包是根，也是每个学DP的人躲不掉的第一个关卡。它说的场景很朴素：有n件物品，每件重量w[i]、价值v[i]，背包容量V，每件物品只能选一次，问能装下的最大价值是多少。

2.1 问题定义与暴力解法的天花板

先把问题用数学语言定义清楚：已知n、V、数组w[1..n]、v[1..n]，要求选出若干件物品，使总重量不超过V，且总价值最大。因为每件物品状态只有“取”或“不取”，所以叫01背包。

暴力解法就是枚举所有的“取/不取”组合：每个物品2种选择，总计2的n次方种。n=20时勉强能跑，n=100时直接爆炸。这也是为什么必须引入DP。

2.2 状态设计：f[i][j] 的语义到底是谁定的

DP最关键的环节不是代码，是状态定义。状态定义决定了你的整个DP能不能递推下去。

01背包的状态最常见的定义是：

f[i][j]：考虑前i件物品，背包容量为j时，能获得的最大价值。

为什么这样定义？因为我们需要一个维度来表示“我已经考虑到了哪件物品”，另一个维度表示“现在还剩下多少容量”。两个维度把问题的解空间切成了网格，每个格子都能从前面的格子推出来，这就是DP表。

有了这个状态，每一件物品i，面对容量j，只有两种决策：

1. 不选第i件：那么结果就是只考虑前i-1件、容量仍为j的最优解，即f[i-1][j]；
2. 选第i件：那你就腾出w[i]的容量去装它，获得v[i]的价值，剩下容量j-w[i]去装前i-1件，即f[i-1][j-w[i]] + v[i]。

取两者较大者就是f[i][j]。这里有个极其重要的细节：“选第i件”这个分支成立的前提是j >= w[i]，容量都不够，想选也选不了。

2.3 转移方程的直觉来源与代码实现

把上面的分析落成方程：

f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]), j >= w[i] f[i][j] = f[i-1][j], j < w[i]

用代码写就是：

#include <iostream> #include <algorithm> using namespace std; const int MAXN = 1005; int w[MAXN], v[MAXN]; int f[MAXN][MAXN]; 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++) { f[i][j] = f[i - 1][j]; if (j >= w[i]) { f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]); } } } cout << f[n][V] << endl; return 0; }

这个实现里，我先把“不选”的默认值填上，再跟“选”的做比较。f[i][j] = f[i-1][j]这一步保证了j < w[i]时也能正常继承上一轮的结果，不需要额外写if-else。

边界条件不需要显式初始化，全局变量默认为0。f[0][j] = 0表示一件物品都不选时价值为0，这是递推的起点。

到这里，01背包的朴素版已经通了。简单画个状态表，你会发现每一行的f[i][j]只依赖上一行的f[i-1][...]——这个观察，直接导向了空间优化的切入点。

3. 空间优化：滚动数组和一维倒序，为什么顺序会害死人

写过几道背包题之后，你大概率见过这种“压缩版”写法：

for (int i = 1; i <= n; i++) { for (int j = V; j >= w[i]; j--) { f[j] = max(f[j], f[j - w[i]] + v[i]); } }

网上几乎所有的题解都会写“内层循环要倒序”，但很少有人说清楚为什么。这个坑我当年踩得很疼——曾经把倒序改成顺序，结果答案错得莫名其妙，折腾了一下午。

3.1 二维数组有什么不好

用二维数组，空间复杂度是O(n*V)。如果n=1000、V=100000，那就是1亿个int，对应约400MB内存，很多题目直接爆内存。但观察状态转移会发现，f[i][j]只依赖f[i-1][j]和f[i-1][j-w[i]]，也就是只依赖上一行。再往前的结果早已没有用处。

于是我们完全可以只保留一行数组，在枚举物品i时，用这一行表示“已经处理完前i-1件物品的DP值”，然后不断原地更新，把它变成“处理完前i件物品的DP值”。这就是滚动数组。

3.2 内层循环必须倒序的解释

一维化之后，核心问题变成了：遍历容量j时，必须从V往w[i]方向倒着走，不能正着走。

为什么？因为正序遍历时，f[j-w[i]]可能已经被本轮的更新覆盖了。假设当前正在处理第i件物品，正序从j=w[i]开始更新，先更新了f[w[i]]，等到后面更新f[2*w[i]]时，你需要的“上一轮（第i-1件）”的f[w[i]]已经变成了“本轮（第i件）”的值。也就是说，你相当于把同一件物品装了两次——这在01背包里是禁止的。

倒序遍历则不同。从j=V往小走，每次更新f[j]时，f[j-w[i]]是尚未被本轮更新的位置，里面存的仍然是上一轮的值，用这个值更新就不会重复取当前物品。

这个原理用一个简单例子验证最直观。假设只有一件物品，重量2、价值3，背包容量5。正序跑一遍：

• j=2：f[2] = max(0, f[0]+3) = 3
• j=3：f[3] = max(0, f[1]+3) = 3
• j=4：f[4] = max(0, f[2]+3) = 6 （这里 f[2] 已经是本轮更新的3，相当于装了两次）
• j=5：f[5] = max(0, f[3]+3) = 6

结果f[4]=6，明显错了——一件物品被算了两次。倒序遍历时，f[4]用到的是上一轮（初始化为0）的f[2]，结果就是3，正确。

所以记住这句话：01背包一维化，内层倒序，本质是在防止“本轮更新值泄露到本轮后续转移里”。

3.3 一维写法的完整代码与常见错法

#include <iostream> #include <algorithm> using namespace std; const int MAXN = 1005; const int MAXV = 100005; int w[MAXN], v[MAXN]; int f[MAXV]; 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 = V; j >= w[i]; j--) { f[j] = max(f[j], f[j - w[i]] + v[i]); } } cout << f[V] << endl; return 0; }

这段代码已经可以直接在洛谷、力扣、AcWing等平台上通过裸01背包模板题。

常见错法总结一下，踩过任何一个都可能导致WA：

• 内层循环写成正序——结果答案是错的，而且不是随机错，是偏大（因为物品被重复选了）；
• 内层循环从V到0，但忘了加j >= w[i]的判断——不写没问题，但j小于w[i]时的f[j-w[i]]会访问到数组负下标，直接越界；
• 数组开小了——f数组大小必须不低于背包容量V+1，w和v数组不低于n+1，别抱着“数据范围小”的侥幸心理，不开大一点很容易出现莫名其妙的Runtime Error。

我自己在某次比赛里就吃过数组没开大的亏。一道题看着很简单，V只有1000，n只有20，结果一跑就崩，检查了半小时才发现f开成了f[1005]而循环里访问到了f[1005]越界。这类教训，刷题多的人都有过。

4. 完全背包和多重背包：变种问题其实只改了一行

01背包弄扎实了，其他背包问题都是从它变形而来的。完全背包几乎是把01背包的一维代码倒序改成顺序，多重背包则在循环里多加一层枚举件数。

4.1 完全背包：为什么正序遍历允许“重复取”

完全背包与01背包的唯一区别：每件物品可以取无限次。问题同样是有n种物品，每种重量w[i]、价值v[i]，背包容量V，问最大价值。

状态定义不变，但转移方程变了。完全背包的朴素二维方程是：

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

注意区别：01背包选第i件后，剩余容量j-w[i]对应的状态是f[i-1][j-w[i]]，完全背包却写成了f[i][j-w[i]]。

为什么？因为完全背包允许重复取同一件物品。你选了当前这件后，下一次转移时仍然可以考虑当前这件物品，而不是只能往前看。这个“i和i-1”的一字之差，恰好就是“能不能重复取”的根本原因。

一维化时，完全背包的代码是正序遍历：

for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= V; j++) { f[j] = max(f[j], f[j - w[i]] + v[i]); } }

正序的作用是：f[j-w[i]]在计算时可能已经被本轮更新过，这意味着“当前物品在本轮已经被选过”，于是可以再选一次，无限叠加。这跟01背包倒序的理由完全对称——正序遍历允许本轮更新值向后传播，刚好满足无限取的需求。

4.2 多重背包：朴素循环与二进制拆分

多重背包加了一个限制：第i种物品最多能取c[i]件。也就是说，它介于01背包和完全背包之间。

朴素的写法是直接在01背包基础上，对每件物品枚举取几件：

for (int i = 1; i <= n; i++) { for (int j = V; j >= 0; j--) { for (int k = 0; k <= c[i] && k * w[i] <= j; k++) { f[j] = max(f[j], f[j - k * w[i]] + k * v[i]); } } }

复杂度是O(nVc)，当c[i]很大时会超时。常见优化是二进制拆分：把c[i]拆成1、2、4、8……以及最后剩余的那部分，把每个拆出来的“堆”当作一件新的物品，然后跑01背包。

举个例子，某件物品能取10次。传统枚举要循环10次，二进制拆分则拆成1、2、4、3（10 = 1+2+4+3）。这四堆物品，你任意取其中p堆，就能拼出0到10之间任意一个取用数量。证明特别简单：1、2、4、3可以组合出0到10的所有整数。这样，10次枚举被压缩成了4件物品，整体复杂度从O(nVc)降到O(nVlog c)。

二进制拆分的实现也很直接，可以一边拆一边做01背包转移：

for (int i = 1; i <= n; i++) { int c; cin >> w[i] >> v[i] >> c; int k = 1; while (c > 0) { int take = min(k, c); for (int j = V; j >= take * w[i]; j--) { f[j] = max(f[j], f[j - take * w[i]] + take * v[i]); } c -= take; k <<= 1; } }

这里每次取take件当前物品，打包成一“堆”新物品，重量take*w[i]、价值take*v[i]，然后按01背包倒序转移。循环结束后，所有“堆”都处理完，等价于考虑了0到原c之间所有可行的选择。

多重背包还有一个单调队列优化，能把复杂度压到O(n*V)，但那个对数学功底要求高，面试和笔试中真正遇到的人也少。先把二进制拆分用熟练，足够应对绝大多数场景。

4.3 三种背包问题的关键差异对照

这张表建议保存下来，做题时先判断物品能取几次，再决定内层循环方向。方向错了，答案必错。

5. 初始化、恰好装满与方案数：看似小改动，暗藏大坑

很多背包题不会直接问“最大价值”，而是会加各种附加条件。最常见的三个坎：“恰好装满”、“求方案数”、“输出具体选择方案”。这三个坎，每个都能拦住一大批人。

5.1 负无穷初始化的意义

01背包模板里，f数组初始化全0，表示“无论容量多大，我都可以什么都不装，价值为0”。这种初始化隐含的语义是：只要重量不超过容量，就是合法的。

但题目如果要求“恰好装满背包”，那么“不装”在容量不为0时是非法的。这时初始化就需要变成：

const int INF = 0x3f3f3f3f; memset(f, -0x3f, sizeof(f)); // 设置为负无穷 f[0] = 0;

为什么负无穷可以办到？因为转移方程里用的是max，凡是不可达的状态，初始值都是负无穷，在max比较时永远不会被选中。只有从f[0]=0出发、一步步“拼”出来的合法状态才会有实际数值。

举个具体例子：背包容量为5，第1件物品重量2价值3，第2件物品重量3价值4。要求恰好装满时，f[5]应该等于7（2+3）。但如果有三件物品，重量分别为4、5、6，容量为5，那么f[5]只能来自重量为5的那件物品，如果它不存在，f[5]会保持负无穷。在这种初始化下，最终结果如果仍是负无穷，说明没有合法方案能恰好装满。

一个常被忽略的细节：用-0x3f3f3f3f而不是INT_MIN做负无穷，是因为INT_MIN加上正数可能溢出成负数，而-0x3f3f3f3f约等于-1e9，加几次v[i]也不会溢出。同理，求最小值时初始化用0x3f3f3f3f，也是一个道理。

5.2 求方案数时状态转移方程的另一种理解

如果题目不是求最大价值，而是问“装满背包有多少种方案”，那么DP数组的语义就从“最大价值”变成了“方案数量”。

以01背包求方案数为例：

f[0] = 1; for (int i = 1; i <= n; i++) { for (int j = V; j >= w[i]; j--) { f[j] = f[j] + f[j - w[i]]; } }

这里的转移逻辑是：f[j]表示凑出容量j的方案数。不选第i件时方案数是原来的f[j]；选第i件时方案数是f[j-w[i]]，二者相加就是总数。

完全背包求方案数，只要把内层循环改成正序：

f[0] = 1; for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= V; j++) { f[j] = f[j] + f[j - w[i]]; } }

这里要注意一个语义细节：如果题目要求“组合数”（不同顺序视为同一种方案，例如1+2和2+1算一种），上面这种先遍历物品、再遍历容量的写法是正确的，因为每种物品是在固定顺序下被加入的，天然杜绝了“重复排列”的问题。如果题目要求的是“排列数”（1+2和2+1算两种），则要内外层循环交换顺序，先遍历容量再遍历物品。

这类题在算法竞赛里非常常见，题目会包装成“凑零钱”“爬楼梯”“数字组合”等形式。本质上考察的就是你能否识别出“这是背包问题”，并正确选择遍历顺序。

5.3 回溯输出具体方案

求完最大价值，题目有时会追加一问：输出选的具体是哪几件物品。做法是在DP过程中记录“决策”，DP结束后再倒推回去。

常见做法是用一个二维数组choice[i][j]记录：处理到前i件物品、容量为j时，第i件物品是否被选取。回溯时从f[n][V]出发：

• 如果选了第i件，j减去w[i]，记下物品i；
• 如果没有选，j不变；
• i递减，直到i=1或j=0。

如果是二维DP，可以不用额外记录，直接通过f值判断：如果f[i][j] == f[i-1][j-w[i]] + v[i]，说明第i件是被选中的；否则没选。前提是每件物品的价值严格大于0。如果有物品价值为0，两个分支可能得出相同数值，就需要额外的choice数组来判断了。

来回溯的代码片段：

int i = n, j = V; while (i >= 1) { if (j >= w[i] && f[i][j] == f[i - 1][j - w[i]] + v[i]) { cout << "选第" << i << "件物品" << endl; j -= w[i]; } i--; }

这个回溯其实还有一个“逆向思维”的妙用：从f[n][V]倒着走，每一步都问“这个值是从哪个状态转移过来的”，一个个往前推，就能还原整条选择路径。

6. 调试技巧与刷题路线：老实的经验总结

内容到此，核心算法都讲完了。但“看懂”和“会做”之间还隔着一条大沟，这条沟需要用调试和刷题来填。最后分享点实际经验。

6.1 三个实用调试手段

第一个手段是中间打表。把f数组按轮次打印出来。比如处理完第i件物品后，打印整个f数组，肉眼观察数据变化。我曾经用这个办法彻底理解了“倒序”和“正序”的区别——看一遍实际数据，比看十遍解释都管用。具体操作是在循环体里临时加一行：

// 调试用，打印当前轮次结束后的一维数组 for (int j = 0; j <= V; j++) { cout << f[j] << " "; } cout << endl;

第二个手段是写暴力对拍。对于小数据范围，暴力枚举所有组合求正确答案，然后跟DP结果对比。自己写个brute()函数，随机生成n=10、V=50的小数据，跑几百组，有差异就定位。这个方法尤其适合验证“我是不是又把方向写反了”这类低级但致命的错误。

第三个手段是用极端数据测试边界。比如n=1、V=0、物品重量大于背包容量这类边界情况。很多WA都是边界条件没处理好，提前自测能帮你避免赛后懊恼。

6.2 由浅入深的练习顺序

如果看完这篇文章想上手练，我建议按这个顺序来：

1. 裸01背包：比如洛谷P1048采药，先跑通模板；
2. 裸完全背包：洛谷P1616疯狂的采药；
3. 多重背包模板题：洛谷P1776宝物筛选，练二进制拆分；
4. 带变式的背包：问恰好装满、求方案数、二维费用（同时限制重量和体积）、分组背包（每组只能选一件）、依赖背包（选主件才能选附件）。

练的时候记住一个原则：**每道题先想清楚是什么背包类型，再动笔写代码。**很多人做不出来不是不会写代码，而是没有识别出题目在考背包问题。判断标志很简单：题面里出现“n种物品”“容量/预算为V”“每种物品最多取几次”“求最大价值/方案数”这些关键词，大概率就是背包的壳。

再往后就是动态规划的更广阔天地了——区间DP、状态压缩DP、树形DP。但那些都不是零基础该着急的事。背包问题学扎实，你对“状态设计”这四个字的理解会上一个台阶，之后学任何DP都会有底气。我在实际教学中观察到，能把背包问题讲清楚的人，动态规划的基本功通常都很扎实；反过来说，背包问题稀里糊涂的人，后面学再多DP技巧也总觉得根基不稳。

所以，别嫌它“简单”，静下心把状态、转移、边界、优化这几件事彻底搞清楚，这一关一过，你会发现整个动态规划的入门才算真正完成。