动态规划背包问题详解
一、开篇引言：为什么要学背包问题？
正式讲解前，我们先明确核心问题：为什么要学背包问题？它的价值在哪里？
- 核心定位：背包问题是动态规划（DP）的经典应用，是理解'状态定义 + 转移方程'的最佳载体。DP 的核心是'拆分复杂问题、复用子问题答案'，而背包问题场景直观——'选物品装背包，求最大价值/最优方案'，能清晰呈现'子问题重叠'与'状态转移'过程，比其他复杂 DP 问题更易入门。
- 实际价值：背包问题看似简单，实则对应多种实际需求。算法面试中，大厂常考察其变种题；工程场景里，有限预算的项目分配、有限时间的任务调度，甚至大数据物品推荐，都能用到其核心思想。
二、动态规划基础回顾
背包问题是 DP 的经典应用，我们先快速回顾 DP 核心知识点，避免后续理解断层。
- 核心思想：将复杂问题拆分为重叠子问题，通过备忘录或 DP 表记录子问题答案，避免重复计算，实现'以空间换时间'。例如，求'前 n 个物品的最大价值'，可拆分为'前 n-1 个物品的最大价值'和'第 n 个物品选或不选'的子问题，记录子问题答案即可避免重复计算。
DP 解题四步走（通用框架）：这是解决所有 DP 问题的核心模板，背包问题也不例外，务必牢记：
- 定义状态：明确 DP 表含义，知道每个位置存储的信息；
- 推导转移方程：明确子问题关系，如'选与不选第 i 个物品'的状态变化；
- 初始化 DP 表：确定边界条件，如'无物品'或'背包容量为 0'时的状态；
- 确定遍历顺序：避免'后序状态影响前序状态'，这是背包问题的易错点。
- 关键提醒：背包问题的核心是'选择'——每个物品只有两种选择：选或不选。所有状态定义、转移方程推导，都围绕'选择后的状态变化'展开，记住这一点就能抓住本质。
三、背包问题核心分类详解（重点）
背包问题有多种分类，核心差异在于'物品选择次数'和'约束条件'。我们重点讲解 3 类基础高频题型（0-1 背包、完全背包、多重背包），再简要拓展其他变种，满足考试基本需求。
3.1 0-1 背包问题（基础中的基础）
0-1 背包是所有背包问题的基础，后续变种均基于其思路推导，务必吃透。
- 问题定义：n 个物品，每个物品有重量 w[i] 和价值 v[i]，背包最大容量为 C，每个物品最多选 1 个（'0-1'由来），求装入背包的最大价值。
示例：3 个物品（物品 1：w=2，v=3；物品 2：w=3，v=4；物品 3：w=4，v=5），背包容量 C=5，最大价值为 7（选物品 1 和 2）。
状态定义：先从二维 DP 表入手（易理解），定义 dp[i][j] = 前 i 个物品放入容量 j 的背包，能获得的最大价值。关键点：
- '前 i 个物品'指第 1 到 i 个所有物品；
- '容量 j'指背包剩余容量，非总容量 C。例如 dp[2][5]，即前 2 个物品放入容量 5 的背包的最大价值。
转移方程推导：核心是'选或不选第 i 个物品'，取两者最大值：
- 不选：dp[i][j] = dp[i-1][j]（等同于前 i-1 个物品放入容量 j 的价值）；
- 选：需留出 w[i] 容量，dp[i][j] = dp[i-1][j - w[i]] + v[i]（前 i-1 个物品放入剩余容量的价值 + 当前物品价值）。
综上：j >= w[i] 时，dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])； j < w[i] 时，dp[i][j] = dp[i-1][j]。
- 初始化：核心是边界条件，确保遍历正常进行：① dp[0][j]（无物品）：无论容量 j 多大，价值均为 0；② dp[i][0]（容量为 0）：无论物品多少，价值均为 0。例如 dp[0][5] = 0，dp[3][0] = 0。
- 遍历顺序：必须'先遍历物品，再遍历容量'，且容量正序（1 到 C）。若颠倒顺序，会导致同一物品被多次选择（等同于完全背包），违背'最多选 1 个'的规则。
- 空间优化：二维 DP 空间复杂度为 O(n*C)，n 和 C 较大时占用内存多，需优化为一维 DP（滚动数组）。核心：将 dp[i][j] 压缩为 dp[j]，表示容量 j 的背包的最大价值，转移方程变为 dp[j] = max(dp[j], dp[j - w[i]] + v[i])。关键细节：容量需倒序遍历（从 C 到 w[i]），避免同一物品重复选择——正序会让 dp[j - w[i]] 包含当前物品选择，倒序则保留前 i-1 个物品的状态。
