动态规划背包问题详解：从入门到实战

基础例题：LeetCode 416. 分割等和子集（简化版）：给定非空数组，判断能否分割为两个和相等的子集。本质是 0-1 背包：背包容量为数组总和的一半，每个元素为'物品'，重量和价值均为元素本身，判断能否装满背包。下面是核心代码：

#include <vector>
#include <algorithm>
using namespace std;

bool f(vector<int>& nums) {
    int total = 0;
    for (int num : nums) total += num;
    if (total % 2 != 0) return false;
    int target = total / 2;
    vector<int> dp(target + 1, 0); // 一维 DP，容量为 target
    for (int num : nums) { // 遍历物品（数组元素）
        for (int j = target; j >= num; j--) { // 倒序遍历容量
            dp[j] = max(dp[j], dp[j - num] + num);
        }
    }
    return dp[target] == target;
}

3.2 完全背包问题（高频考点）

完全背包是 0-1 背包的变种，高频程度不亚于前者，核心差异仅 1 个，抓住即可快速掌握。

• 问题定义：与 0-1 背包唯一区别——每个物品可无限次选择，其他条件一致（n 个物品、w[i]、v[i]、背包容量 C，求最大价值）。示例同上，完全背包中可重复选物品，但受容量限制，最大价值仍为 7。
• 核心差异：遍历顺序。0-1 背包倒序遍历容量避免重复选择，完全背包正序遍历容量允许重复选择——正序时，dp[j - w[i]] 已包含当前物品选择，相当于'再次选该物品'，符合'无限选'规则。
• 状态定义与转移方程：沿用一维 DP，dp[j] 表示容量 j 的背包最大价值，转移方程与 0-1 背包一致，仅遍历顺序不同（容量正序）。
• 空间优化：无需额外优化，一维 DP 即可满足。与 0-1 背包相比，无需刻意避免重复选择，正序遍历即可兼顾空间优化和'无限选'需求。
• 基础例题：凑硬币（简化版）：给定无限枚硬币，求凑成总金额的最大价值（面额即价值）。示例：硬币 [1,2,5]，总金额 11，最大价值为 11。核心 C++ 代码（对比 0-1 背包）：

#include <vector>
#include <algorithm>
using namespace std;

int maxValue(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 0); // 完全背包，硬币可重复选
    for (int coin : coins) { // 遍历物品（硬币）
        for (int j = coin; j <= amount; j++) { // 正序遍历容量（核心区别）
            dp[j] = max(dp[j], dp[j - coin] + coin);
        }
    }
    return dp[amount];
}

3.3 多重背包问题（拓展考点）

多重背包介于 0-1 背包（选 1 次）和完全背包（选无限次）之间，每个物品有有限选择次数，面试频率虽低，但需掌握基础解法和优化思路。

• 问题定义：每个物品有 k[i] 个，其他条件与 0-1 背包一致（n 个物品、w[i]、v[i]、背包容量 C，求最大价值）。示例：物品 1（w=2，v=3，k=2）、物品 2（w=3，v=4，k=1），背包容量 5，最大价值为 7（选 1 个物品 1 和 1 个物品 2）。
• 基础解法：转化为 0-1 背包。将 k[i] 个物品拆分为 k[i] 个独立物品（每个仅选 1 次），即可套用 0-1 背包思路。该方法简单，但 k[i] 较大时（如 1000），物品数量剧增，效率低下。
• 优化解法：二进制拆分法（核心）。将 k[i] 拆分为 2 的幂次之和（如 k=5 拆为 1+2+2，k=7 拆为 1+2+4），每个拆分后的'组合物品'仅选 1 次，可覆盖 0-k[i] 的所有选择情况，将物品数量从 k[i] 缩减至 log2(k[i])，大幅提升效率。
• 例题：同上示例，二进制拆分后，物品 1 拆为 2 个独立物品，物品 2 拆为 1 个独立物品，转化为 0-1 背包，遍历得最大价值 7。k 较小时差异不明显，k=1000 时，拆分后仅 10 个物品，效率提升显著。

3.4 其他常见背包变种（简要拓展）

除核心 3 类，面试中还会遇到变种，简要讲解核心思路，重点掌握迁移能力，无需深入推导。

• 二维背包：物品有两个约束（如重量 + 体积），背包有最大重量 C 和体积 V，求最大价值。核心：状态定义扩展为 dp[j][k]（容量 j、体积 k 的最大价值），转移方程仍分'选或不选'，多一个约束条件。
• 分组背包：物品分若干组，每组仅选 1 个。核心：遍历顺序调整为'先组、再容量、最后组内物品'，转移方程在'选组内物品'和'不选该组'间取最大值。
• 求方案数/具体方案：在最大价值基础上增加统计逻辑。求方案数可新增 count 数组，记录容量 j 时的最大价值方案数；求具体方案可新增 path 数组，回溯记录选择的物品。

四、背包问题解题技巧与避坑指南

掌握核心分类后，总结解题技巧和常见坑点，帮大家避开误区、提升效率，应对面试更从容。

核心技巧：快速判断背包类型，记住两个维度：

1. 选择次数：选 1 次（0-1）、无限次（完全）、有限次（多重）；
2. 约束条件：单个（普通）、多个（二维/多维）、分组（分组背包）。定位类型后，直接套用对应思路。

常见坑点：

1. 遍历顺序错误（最易错）：0-1 背包'物品正序、容量倒序'，完全背包'物品正序、容量正序'，颠倒会导致结果错误；
2. 初始化错误：忘记初始化 dp[0][j] 或 dp[i][0]，导致遍历异常；
3. 转移方程漏边界：未判断 j >= w[i] 就套用方程，导致数组越界；
4. 多重背包拆分错误：二进制拆分的幂次和需等于 k[i]，否则遗漏选择。

解题模板（通用）：

1. 确定背包类型；
2. 定义状态（一维/二维）；
3. 推导转移方程；
4. 初始化 DP 表；
5. 确定遍历顺序；
6. 计算结果，必要时回溯方案。新手可直接套用。

调试技巧：出错时，打印 DP 表分析子问题答案。如 0-1 背包打印 dp[j] 变化，重复选择多为遍历顺序错误，结果偏小可能是初始化或转移方程漏边界。

五、实战演练：经典真题解析

理论需结合实战巩固，以下简要解析 3 道 LeetCode 经典真题，对应核心背包类型，帮大家掌握思路转化。

1. 0-1 背包真题：P1048 采药（经典入门题）。题意：采药时间有限（对应背包容量），每种药材有采集时间（重量）和价值，每种药材只能采一次，求最大可获得价值。

   • 解题思路：直接套用 0-1 背包模板，
     • 状态定义：dp[j] 表示采集时间为 j 时的最大价值；
     • 转移方程：dp[j] = max(dp[j], dp[j - time[i]] + val[i])；
     • 遍历顺序：物品正序、时间倒序；

2. 完全背包真题：P1616 疯狂的采药（经典拓展题）。题意：与 P1048 采药唯一区别——每种药材可无限次采集（无数量限制），求有限时间内的最大价值。

   • 解题思路：套用完全背包模板，核心差异为遍历顺序（时间正序），
     • 状态定义：dp[j] 含义同 P1048；
     • 转移方程不变，遍历顺序调整为时间正序，允许重复采集；

3. 多重背包真题：P1776 宝物筛选（经典优化题）。题意：每种宝物有重量、价值和数量限制（k[i] 个），背包有最大容量，求最大价值。

   • 解题思路：采用二进制拆分法优化，将每种宝物的 k[i] 个拆分为 2 的幂次组合，转化为 0-1 背包求解，
     • 拆分逻辑：将 k 拆分为 1、2、4...剩余值，覆盖 0-k 的所有选择；
     • 核心步骤：拆分宝物→遍历拆分后的物品→倒序遍历容量；

解题总结：三道真题精准对应三类核心背包问题，P1048 练 0-1 背包基础，P1616 练完全背包遍历顺序差异，P1776 练多重背包二进制优化，核心均是'套用模板 + 适配题干'。

六、进阶拓展与总结

至此，我们已掌握背包问题核心知识点和实战技巧，下面总结核心要点，并拓展进阶方向，帮大家应对更复杂的面试题。

• 核心本质：背包问题是'资源分配问题'，核心是'选择'与'状态记录'——用有限资源（背包容量），选择最优物品组合，实现收益最大化（或其他目标）。
• 进阶方向：① 混合背包：多种类型物品结合，分类型处理，套用对应遍历顺序；② 三维背包：三个约束条件，状态定义扩展为三维，思路同二维背包；③ 空间极致优化：针对特定场景（如物品重量大、容量小）优化滚动数组。
• 学习建议：新手从 0-1 背包入手，先懂二维 DP，再理解空间优化，逐步学习完全、多重背包。多练真题，重点理解'状态定义'，而非死记公式，遇到疑问可打印 DP 表分析子问题。
• 总结：背包问题是 DP 入门钥匙，掌握其思路可迁移到子序列、路径等其他 DP 问题。核心逻辑不难，抓住'拆分问题、记录状态、复用答案'，避开坑点，就能轻松应对面试中的背包相关题目。