动态规划背包问题详解
一、开篇引言:为什么要学背包问题?
正式讲解前,我们先明确核心问题:为什么要学背包问题?它的价值在哪里?
- 核心定位:背包问题是动态规划(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 个物品的状态。


