1. 开始之前：背包问题到底在求什么

1.1 一个很多人没意识到的建模动作

背包问题最让我惊讶的地方，是它几乎覆盖了所有"资源有限、选择无限"的现实场景。比如你有一个容量10的背包，面前有5个物品，每个物品有自己的重量和价值，目标是在不超过背包容量的前提下挑出总价值最大的组合。这听起来像是一个朴素的组合优化问题，可一旦物品数量上到几十上百，枚举所有组合就彻底不现实了，2的100次方这个数字，任何计算机都扛不住。

所以动态规划背包问题的第一步不是写代码，而是把一个实际需求翻译成一个标准的数学模型。你手里有什么资源——背包容量；你有哪些决策——每个物品选还是不选；你追求什么——总价值最大。这三句话写清楚了，后面的代码才会有方向。我见过很多人一上来就套模板，结果题目一变就懵，问题就出在建模这一步跳过得太快。

在C++里做背包，通常会把物品重量存到数组w[]，价值存到数组v[]，然后用dp[i][j]表示"在前i个物品中做选择，且总重量不超过j时，能获得的最大价值"。这个定义不是凭空来的，它包含了两个维度：一是处理到哪件物品了，二是当前还剩多少容量。后面的所有优化、所有变体，都是从这两个维度展开的。

1.2 为什么说状态定义是这道题的分水岭

很多新手对dp的恐惧，其实是对状态定义的不适应。简单说，状态就是"我已经决定了前i个物品怎么选，当前我的背包占用为j，此时我的收益是多少"。这个定义在数学上叫子结构，它要求我们从一个小规模问题出发，通过递推得到大规模问题的答案。

你可能会问，为什么不是"当前重量恰好等于j"？这里面有一个很关键的约定：不超过j通常更好用，因为我们可以从dp[i][j] = dp[i-1][j]继承一个"不选当前物品"的状态。如果定义成恰好等于j，那么这个继承动作就非常别扭，因为前i-1个物品凑出来的重量不一定是j。这也是为什么后面讨论"恰好装满"时需要单独处理初始化的原因。

状态定义决定了转移方程。对于0-1背包，每件物品有两种决策：不选，那么dp[i][j]继承dp[i-1][j]；选，那么需要先把容量j减去当前物品重量w[i]，再加上价值v[i]，即dp[i-1][j-w[i]] + v[i]。两者取最大，就得到了当前状态。这个过程就是"状态的推演"，它的每一步都只依赖前i-1个物品的结果，不依赖后面的物品——这就是动态规划里常说的无后效性。

1.3 贪心失效的直观演示

有一种思路是单位重量价值最大优先，即贪心。用图景来说就是：一个容量为10的背包，三件物品分别是(重量6，价值6)、(重量5，价值5)、(重量5，价值5)。如果按单位价值一样来挑，先拿第一件，剩余容量4，什么都装不下，总价值6。可正确答案是拿后两件，总价值10。这种反例足以说明，局部最优拼不出全局最优。

动态规划为什么能解决这个问题？因为它不是一次性决定选哪些，而是把整个决策过程拆成一步步的子问题，并且用一张二维表把这些子问题的答案全部存下来。每个状态都保存了"在这个决策阶段、这个容量限制下的最优收益"，最终dp[n][C]（n个物品都决策完，容量限制为C）就是全局最优。

这一节的核心结论是：遇到组合优化的题目，先尝试用"决策阶段+资源限制"两个维度描述状态，如果状态能从小范围递推到全范围，那么动态规划大概率就是那把钥匙。背包问题是这类思想的入门钥匙，而C++的高效数组和显式循环，刚好适合把整个过程清晰落地。

2. 0-1背包：从二维dp表到滚动数组，代码是怎么一步步变短的

2.1 最朴素的二维写法（先能跑通）

我建议所有人在理解阶段先写最朴素的二维版本，不要直接背一维优化版。原因很简单：二维版本的行列含义和状态转移一一对应，出错时还能把dp表打出来逐行排查。下面这段代码就是0-1背包的基准版。

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, C; cin >> n >> C; vector<int> w(n + 1), v(n + 1); for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; // dp[i][j]: 前i个物品中选，总重量不超过j的最大价值 vector<vector<int>> dp(n + 1, vector<int>(C + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 0; j <= C; j++) { // 不选第i个物品 dp[i][j] = dp[i - 1][j]; // 选第i个物品，前提是容量足够 if (j >= w[i]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]); } } } cout << dp[n][C] << endl; return 0; }

注意这里的循环j是从0到C，每次都先继承"不选"的结果，再比较"选"的结果。这样的写法逻辑最直观，运行效率也足够应付多数题目（n=1000时约百万次操作）。但代价是多开了一个二维数组，内存复杂度是n乘C。

2.2 省掉一个维度的勇气从哪来

二维dp表每一行的更新只依赖上一行，而且只依赖当前列j和左边的列j-w[i]。这意味着第i行写完以后，第i-1行就再也用不到了。那我们可不可以只用一个一维数组，让它在原地更新？

答案是：可以，但更新方向有讲究。一维状态dp[j]的含义变成"当前已经处理完前i件物品时，容量不超过j的最大价值"。内层循环从C向j递减到w[i]，这样在计算dp[j]时，dp[j-w[i]]还没有被本轮更新覆盖，它仍然是上一轮（处理i-1件物品）的结果，这正是我们想要的。

从二维压到一维，本质上是用"更新时机"代替"行号"。如果你从前往后更新，dp[j-w[i]]已经被本轮更新过，代表的是"考虑了当前物品后"的状态，那么当前物品就可能被反复选入背包，0-1背包就悄悄变成了完全背包。这也是很多人在接触"完全背包"时突然理解循环顺序的原因。

2.3 为什么逆序遍历这么反直觉却必须这么做

逆序遍历让很多人困惑：同样是更新一个数组，为什么反过来就对了？我们用一个小例子说明。假设只有一个物品，重量2，价值3，容量C=3，一维数组初始全0。

正序遍历：j从0到3。当j=2时，dp[2]会更新为dp[0]+3=3；当j=3时，dp[3]会更新为dp[1]+3=3。到这里看似没错。但如果在同一个物品下继续看，j循环只有一轮，看起来正序也没问题？

问题出在第2个物品到来时：正序会让第2个物品更新用到的dp[j-w[j]]可能已经被第2个物品改动过。更直接的例子是：两个相同物品，重量2、价值3，容量4。正序在j=4时，dp[4] = dp[2]+3，而dp[2]在同一轮已经变成3，所以dp[4]变成了6，相当于选了两次同一种物品。逆序则保证dp[2]在dp[4]更新时仍旧是上一轮的值0，所以dp[4]=3，只有一个物品被选中。

一句话总结：逆序是为了让每个物品最多被选一次。代码中从C到w[i]递减循环，天然实现了这个效果。理解这一点后，你会觉得背模板一点也不虚。

2.4 你最终会留在编辑器里的0-1背包模板

一维优化的最终代码大概长这样：

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, C; cin >> n >> C; vector<int> w(n + 1), v(n + 1); for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; vector<int> dp(C + 1, 0); for (int i = 1; i <= n; i++) { for (int j = C; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << dp[C] << endl; return 0; }

这段代码就是0-1背包的标准形态。记住两个要点：一重循环遍历物品，二重循环逆序遍历容量，转移只写一行max。很多变种都在这两个要点的排列组合上做文章。

3. 完全背包与多重背包：两个方向的变体，同一个套路

3.1 完全背包只是一行代码的事，但原理不能只记结论

完全背包和0-1背包的区别是：每种物品有无限件。你可能会想到拆成很多个相同物品，但那会让物品数量膨胀到无法接受。更好的做法是直接修改内层循环顺序——从正序遍历容量。

为什么正序就能实现无限取？回到2.3的例子里，正序遍历时dp[j-w[i]]已经包含了当前物品的信息，所以再更新dp[j]时，相当于允许物品被重复使用。这种"复用"正好对应无限件。代码只需要把内层循环改成for(int j = w[i]; j <= C; j++)。

但这里有一个容易忽略的边界：dp[j]继承的不选状态。由于是正序，同一轮里dp[j-w[i]]可能已经更新过，因此完全没有必要再显式写"不选"分支。实际上dp[j] = max(dp[j], dp[j-w[i]]+v[i])这一句在正序循环下自动完成了多次加法，也就是允许多次放入。我建议你亲手用一个小数据跑一遍二维表，把内层每个dp[j]的变化写出来，很快就能理解这个反直觉的循环顺序。

3.2 多重背包的二进制拆分，到底拆的是什么

多重背包给每种物品一个数量上限k，比如某种物品最多有10件。最朴素的思路是把10件拆成10个独立物品，做0-1背包。但k很大时（比如1e5），拆分成单个物品会让总件数爆炸。

二进制拆分是一个聪明得多的办法：把k拆成若干个数，这些数能组合成0到k之间的任意整数，但个数只有O(log k)个。拆分规则是每次取2的幂次，比如k=10，拆成1、2、4、3（因为下一个8会让总和超过10，所以最后取10-1-2-4=3）。用这些"打包"后的物品做0-1背包，复杂度从O(nkC)降到O(nlog kC)。

不少人第一次看到这里会疑惑：1、2、4、3真的能覆盖0到10吗？我们验证：0（什么都不用），1，2，3（1+2），4，5（1+4），6（2+4），7（1+2+4），8（1+3+4），9（2+3+4），10（1+2+3+4）。所有整数都能被组合出来，这就是二进制拆分的数学底子。

vector<pair<int,int>> goods; // weight, value while (k > 0) { int cnt = 1; // 当前批次数量 while (cnt * 2 - 1 <= k) cnt <<= 1; // 这里更常用写法是逐步取1,2,4... }

我给出一个稳定写法：

int num = k; int batch = 1; while (num > 0) { int take = min(batch, num); int nw = take * w; int nv = take * v; // 将这个nw/nv作为0-1背包的一个物品 num -= take; batch <<= 1; }

拆分完成后，再用标准0-1背包的逆序循环处理这些打包物品即可。

3.3 分组背包：把"每组只能选一个"翻译成状态转移

再进一步，物品被分成若干组，每组最多挑一件。这看起来和前面的都不一样，但状态转移还是一句话：枚举每一组，对组内的每个物品都尝试一次"选它"。

具体做法是在一维dp基础上，外层循环遍历组，内层先循环容量（逆序，保证每组的物品最多选一个），再循环本组内的物品。注意顺序，一定是"先容量后物品"，否则同一组的多个物品会相互影响，导致一组里选了好几件。

vector<int> dp(C + 1, 0); for each group g: for (int j = C; j >= 0; j--) { for each item in group g: if (j >= item.w) { dp[j] = max(dp[j], dp[j - item.w] + item.v); } }

为什么这样就能保证"每组最多选一个"？因为容量循环是逆序的，dp[j]更新时用到的dp[j-w]还是上一组的结果，也就是说当前组内的物品互相之间不会叠加。如果你把物品循环放在外层，容量放在内层，同一组内的不同物品会在一次容量遍历里互相更新，可能会导致一组选多件。

3.4 一张表看清三个背包的差异

实际做题时，先判断物品的使用限制，再决定用哪种循环方向，比硬记模板的适用场景可靠得多。判断依据很简单：物品能不能重复用？能就正序，不能就逆序；有限个但又不能简单当成完全背包？先二进制拆分，再按0-1背包处理。

4. 真正决定你过不过的细节：初始化、边界与带约束的变体

4.1 恰好装满和不超过容量，dp[0]之外的区别

默认背包问题求的是"不超过容量C的最大价值"，初始化全部为0是合理的，因为什么都不装就是合法的空包方案，价值0。

但如果题目改为"恰好装满容量C的最大价值"，情况就不同了。未达到"恰好装满"的状态是非法的，不能简单用0表示，否则会把非法方案混进来。标准做法是：

vector<int> dp(C + 1, -1e9); // 或 INT_MIN / 2 dp[0] = 0;

因为只有重量为0的状态是合法的起点，其他容量的"恰好值"当前都不存在，用负无穷标记为不可达。在转移时，如果dp[j - w[i]]是负无穷，那么dp[j]也不会被误更新成合法值，因为负无穷加任何价值还是负无穷（C++里不要直接用INT_MIN加正数，可能导致溢出，通常用-1e9或INT_MIN/2更稳）。

初始化之差，能直接把一题变成另一题。很多模板默认把所有dp初始化为0，遇到"恰好装满"题直接样例通过、大量数据挂掉，就是这个原因。

4.2 遇到未定义状态时，用负无穷还是-1

用-1表示不可达可以吗？可以，但你的转移就要多写一个判断：

if (dp[j - w[i]] != -1) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); }

用负无穷则不需要这种判断，因为负无穷+价值还是负无穷，取max时不会影响其他合法状态。代价是要时刻小心溢出。我的习惯是初始化-1e9，因为题目价值总和通常不会超过1e9，负无穷足够"无穷"。

还有一种情况是求方案数：dp[i]表示凑成重量i的方案数，初始化dp[0]=1，转移时dp[j] += dp[j - w[i]]（内层循环方向根据背包类型变化）。此时就不需要负无穷了，因为方案的0和1都是合法语义，只需要保证dp[0]=1，其余为0即可。由此可见，同一个dp数组，因为目标不同，初始化和转移是完全不同的写法。

4.3 二维费用背包：状态再多一维，逻辑不变

当每个物品不仅消耗重量，还消耗体积（或某种"容量"），背包就有两个限制条件。解决思路很简单：状态再加一维，从dp[j]变成dp[j][k]，分别表示重量不超过j且体积不超过k时的最大价值。

vector<vector<int>> dp(C + 1, vector<int>(V + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = C; j >= w[i]; j--) { for (int k = V; k >= t[i]; k--) { dp[j][k] = max(dp[j][k], dp[j - w[i]][k - t[i]] + v[i]); } } }

注意内外两维容量都要逆序，原因是同一个物品不能被同时选两次。很多时候二维费用的题目对数组大小的限制更严格，写代码前先估算NCV会不会超内存。如果明文告诉你C和V都到1000，物品n到100，那要思考一下状态能不能压缩，或者能不能优化成一维加另一维的递推关系。

二维费用本质上还是背包，只是资源维度扩展了。遇到三个限制条件时，就三维dp，但时间和内存往往会吃紧，这时要优先考虑是否可以拆条件、减少一维，或者用其他算法解决。

4.4 我排查边界bug的顺序与打印dp表的技巧

背包题报错时，先别急着重写。我的排查顺序是：

1. 检查物品数组下标从1开始还是从0开始。很多模板从1开始，读入循环也要从1到n。
2. 检查容量循环边界。0-1背包用for (int j = C; j >= w[i]; j--)，完全背包用for (int j = w[i]; j <= C; j++)，方向反了结果全错。
3. 检查dp初始化和输出状态。输出的是dp[n][C]还是dp[C]？一维版本初始化全0还是-1e9？
4. 手动造一个小数据，比如n=3，C=5，把关键状态的dp变化写出来对比。

打印dp表是最直接的调试手段。在一维版本中，每处理完一个物品后打印一次dp数组，观察每个物品是怎么"滚"进数组的。如果你看到某一轮容量j变化时，dp[j]的数值从"上一轮的值"跳成了"本轮被多次更新"，那就说明循环方向写错了。

5. 把背包题练成肌肉记忆：选题顺序与个人模板

5.1 从零到一，我建议的练习顺序

不要直接刷困难题，那样挫败感太强。我建议按下面这个顺序练：

第一步，先跑通0-1背包的朴素二维代码，输出答案，再改成滚动数组，对比结果。 第二步，做几个"裸题"——题目明说是背包，直接套模板。 第三步，做需要识别出"这是背包问题"的题，比如把一个数组分成两个和相等的子集，本质是能不能凑出总和的一半。 第四步，做完全背包和多重背包的裸题，理解循环方向差异。 第五步，做方案数、恰好装满、二维费用等变体，反复练习初始化与转移。

一个常见的学习误区是上来就背一维模板，结果只记住了代码，遇到"恰好装满"就歇菜。反过来，如果你自己推过二维转移、亲手写过一维滚动，那么任何变体你都可以从状态定义出发重新推导，而不是套模板。

5.2 一套可复用的C++模板与改参点

下面是我平时写背包题前心里默念的通用结构，可以应对绝大多数背包变化：

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int INF_NEG = -1e9; int main() { int n, C; cin >> n >> C; vector<int> w(n), v(n); for (int i = 0; i < n; i++) { cin >> w[i] >> v[i]; } // 按需选择初始化 vector<int> dp(C + 1, 0); // 不超过容量 // vector<int> dp(C + 1, INF_NEG); // 恰好装满 // dp[0] = 0; for (int i = 0; i < n; i++) { if (0-1背包) { for (int j = C; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } else if (完全背包) { for (int j = w[i]; j <= C; j++) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } } cout << dp[C] << endl; return 0; }

对于多重背包，先做二进制拆分，再走0-1背包分支。对于分组背包，把内层换成"先容量后组内物品"。这套模板的三个改参点就是：初始化方式、容量循环方向、物品组内遍历顺序。记住这三个点，遇到变体时你只需要思考"它属于哪种"。

5.3 常见的"伪最优解"与避免背模板翻车

我见过最多的问题不是不会写代码，而是"模板对了但题意理解偏了"。比如题目要求"总重量恰好等于C"，你用了全0初始化，结果通过率惨不忍睹。再比如"每种物品可以无限取但你把它当成0-1背包来做"，正序和逆序一字之差，答案天壤之别。

另一个容易翻车的地方是用int存dp值。如果物品价值和都超过20亿，int会溢出。这时要用long long，并把负无穷初始化改为-1e18。同样的，方案数题目经常要求对某个大质数取模，如果忘记模，数据一大就全错。

还有一个小细节：读入物品时w或v可能为0。如果重量为0且价值为正，那么在不超过容量的情况下，0重量的物品可以无限叠加价值，dp的最大值可能超出一般直觉。分析这类题时，要单独考虑重量0的物品对答案的贡献，防止思维盲区。

6. 背包问题带给我的不止是一类题：对状态机思维的延伸

6.1 从背包到完全背包，本质是循环顺序的变化

真正练到后期，你会发现背包家族的所有题目都可以用"状态定义 + 阶段循环 + 容量方向"统一起来。0-1和完全背包的区别，只是内层循环从逆序变正序；多重背包只是先加工数据再套0-1；分组背包只是把决策枚举放在容量循环内。这种统一性让我对动态规划的理解上了一个台阶：很多题不是新题，而是旧题换了限制条件。

我印象最深的是，某次做一个"最长子序列"变体题时，我试图把每个字符当成一个物品，把匹配长度当成容量，发现和背包问题有着完全相似的"选择或不选择"模型。那一刻我才意识到，背包训练的真正价值，是培养我把问题拆成"阶段、状态、决策"三件套的思维方式。拥有这种思维后，看到类似"划分数组""子集和"的问题，第一反应就是试着用dp建模。

6.2 为什么求方案数/最优解时初始化要一级一级审

最后分享一个我自己踩过的坑：求方案数时，如果物品重量有0的情况，dp[0] = 1会出问题。比如两件物品重量都是0，那么凑成重量0的方案数应该是4种（都不选、选第一个、选第二个、两个都选），但如果只是形式上令dp[0]=1，然后正常转移，就能得到这个结果吗？通常不行，因为0重量物品不会更新dp数组中的其他格子，导致很多方案没有计数。

处理方式是单独统计所有重量为0的物品，设它们的数量为zeroCnt，那么凑成任意重量j的初始方案数要乘以2的zeroCnt次方（因为每个0重物品可选可不选），然后再处理正重量物品。这个坑不亲自踩一次，很难想到。

经过这几轮练习，我现在看背包题的感觉，就像看一张熟悉的地图：先定位物品数量限制，再决定循环方向；先看是求最优值还是求方案数，再决定初始化和转移。每一步都不是靠背，而是靠对状态转移本身的理解。也希望这篇文章能帮你把这张地图真正画进脑子里，下次遇到背包题时不再是"套模板"，而是"我在推导这个状态该怎么转移"。