动态规划：01 背包与完全背包梳理 先从最基础的 01 背包说起：一共 N 件物品，背包总容量为 V，每件物品都只有 1 个，不能重复选取。第 i 件物品占用容量 c [i]，对应价值 w [i]，目标是在总容量不超过 V 的前提下，让装入背包的物品总价值最大。 举个经典的例子：背包上限 10kg，A 物品重 2kg 价值 1，B 重 3kg 价值 3，C 重 4kg 价值 5，E 重 8kg 价值 10。很多初学者第一反应会用贪心算法：算每件物品单位重量的性价比，优先挑性价比最高的。但在这个例子里，C 的性价比最高，可要是直接选 C，剩下 6kg 容量反而凑不出更高的总价值；反倒放弃 C，选 A、E 组合，总价值会更高。 贪心的逻辑是每一步都做局部最优选择，但局部最优拼不出全局最优。它只适用于物品可以拆分的场景，而 01 背包里的物品都是不可分割的，要么选要么不选，所以贪心得不出正确答案，必须用动态规划，从全局维度枚举所有决策，拿到整体最优解。 01 背包的二维与一维实现 二维动态规划 状态定义很直观：dp [i][v] 表示考虑前 i 件物品、背包可用容量为 v 时，能获得的最大总价值。 对第 i 件物品只有两种决策： 不选这件物品：状态直接继承前 i‑1 件的结果，也就是 dp [i‑1][v] 选这件物品：需要预留出 c [i] 的容量，对应状态是 dp [i‑1][v‑c [i]] + w [i] 由此得到状态转移方程：dp [i][v] = max (dp [i‑1][v], dp [i‑1][v‑c [i]] + w [i]) 如果当前容量 v 小于物品重量 c [i]，装不下这件物品，就直接继承上一层的结果。 实现的时候用两层循环：外层遍历每一件物品，内层从 0 到总容量 V 逐个枚举容量，判断容量是否足够后执行转移，最终 dp [N][V] 就是答案。二维写法逻辑清晰，适合新手理解状态转移的过程，但二维数组占用内存多，当 N 和 V 的规模较大时很容易内存超限，所以通常都会做空间优化。 一维空间优化 观察转移过程就能发现：计算第 i 层的状态时，只会用到第 i‑1 层的数据，不需要保存所有历史层。因此可以去掉代表物品的 i 维度，压缩成一维数组。 定义 dp [j] 表示背包容量为 j 时的最大价值，转移方程简化为：dp [j] = max (dp [j], dp [j‑c [i]] + w [i]) 这里有一个最关键的细节：一维 01 背包的容量 j 必须从大到小倒序遍历。如果 j 从小到大正序遍历，小容量的 dp 值先被更新，后面计算更大的 j 时，读到的就是刚更新完的新值，相当于同一件物品被多次选取，违背了 01 背包每件只能拿一次的规则。而倒序遍历时，计算大容量 j 的 dp [j‑c [i]] 保存的还是处理当前物品之前的旧状态，就能保证每件物品只会被选一次。 比如物品重量 2、价值 5，倒序更新时：容量 1 装不下，dp [1] 保持 0；j=2 时，dp [2] = max (0, dp [0]+5) = 5；j=3 时，dp [3] = max (0, dp [1]+5) = 5，全程这件物品只被计入一次。 日常做题更推荐用一维倒序的写法，省内存，代码也更简洁。 完全背包 完全背包的题干和 01 背包几乎一致：N 件物品，背包容量 V，每件物品占容量 c [i]、价值 w [i]。唯一的区别是：每件物品可以选取无限次，同一件物品能反复拿取。 二维状态转移 二维状态定义和 01 背包相同：dp [i][v] 代表考虑前 i 件物品、容量为 v 时的最大价值。决策同样分两种： 不选第 i 件：继承 dp [i‑1][v] 选第 i 件：因为可以重复选取，选完之后仍然可以继续选第 i 件，所以对应状态是 dp [i][v‑c [i]] + w [i]—— 注意这里是 dp [i]，而不是 01 背包里的 dp [i‑1] 转移方程：dp [i][v] = max (dp [i‑1][v], dp [i][v‑c [i]] + w [i]) 一维实现与核心区别 完全背包同样可以压缩成一维，转移方程和 01 背包的一维形式完全相同：dp [j] = max (dp [j], dp [j‑c [i]] + w [i]) 但循环顺序恰好相反：完全背包的容量 j 需要从小到大正序遍历。正序遍历时，小容量的 dp 先被更新，后面更大的 j 可以复用刚更新好的值，自然就实现了同一件物品多次选取。 举个简单例子：背包总容量 5，物品重 2、价值 5。正序遍历 j：j=2 时 dp [2]=5；j=4 时，dp [4] = max (0, dp [2]+5) = 10，相当于拿了两件该物品，达成了 “无限选取” 的效果。 总结与提醒 01 背包物品仅 1 件，一维遍历容量倒序；完全背包物品无限件，一维遍历容量正序 —— 这是两类背包代码最核心的区分点。 两类背包的代码框架高度相似，但循环顺序不同，对应的语义完全不同。后续还有很多变形，比如每件物品最多拿 k 件的多重背包，都是从这两个基础模型延伸来的。做背包题的第一步，一定先辨明类型，确认物品的选取次数，再选择对应的循环方式。