零基础数据结构与算法——第五章：高级算法-动态规划经典-背包问题
5.1.3 动态规划经典-背包问题
背包问题是动态规划中的经典问题，也是理解动态规划思想的绝佳例子。
问题描述：
有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。
生活例子：
想象你是一名登山者，准备一次登山旅行。你有一个容量有限的背包，和许多可能带上的物品（食物、水、装备等）。每件物品都有自己的重量和价值（对登山的帮助程度）。你需要决定带哪些物品，使得在背包容量限制下，总价值最大。
0-1背包问题
问题特点：每件物品只能用一次（要么放入背包，要么不放）。
问题分析：
-
定义状态：dp[i][j]表示考虑前i件物品，背包容量为j时能获得的最大价值。
-
状态转移方程：对于第i件物品，有两种选择：
- 不放入背包：dp[i][j] = dp[i-1][j]
- 放入背包（如果容量允许）：dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1]
取两者的最大值。
-
初始条件：dp[0][j] = 0（没有物品时，价值为0）
动态规划解法：
public static int knapsack01(int[] weights, int[] values, int capacity) { int n = weights.length; // 创建dp数组，dp[i][j]表示考虑前i件物品，背包容量为j时能获得的最大价值 int[][] dp = new int[n + 1][capacity + 1]; // 填充dp数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= capacity; j++) { if (weights[i - 1] <= j) { // 可以放入背包，取放入或不放入的最大值 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]); } else { // 不能放入背包 dp[i][j] = dp[i - 1][j]; } } } return dp[n][capacity]; // 返回最终结果}图解过程：
假设有3件物品，重量分别为[2, 3, 4]，价值分别为[3, 4, 5]，背包容量为5。
- 初始化dp数组：所有dp[0][j]和dp[i][0]都为0
- i=1, j=1: 物品0重量为2 > 1，不能放入，dp[1][1] = dp[0][1] = 0
- i=1, j=2: 物品0重量为2 = 2，可以放入，dp[1][2] = max(dp[0][2], dp[0][0] + 3) = max(0, 0 + 3) = 3
- 依此类推…
最终dp数组：
0 1 2 3 4 5 (容量)0 0 0 0 0 0 01 0 0 3 3 3 3 (考虑物品0)2 0 0 3 4 4 7 (考虑物品0,1)3 0 0 3 4 5 7 (考虑物品0,1,2)结果是7，表示最大价值为7。
空间优化：
我们可以将二维dp数组优化为一维，因为每个状态只依赖于上一行的状态：
public static int knapsack01Optimized(int[] weights, int[] values, int capacity) { int n = weights.length; int[] dp = new int[capacity + 1]; for (int i = 0; i < n; i++) { // 注意这里要从后往前遍历，避免物品被重复使用 for (int j = capacity; j >= weights[i]; j--) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); } } return dp[capacity];}完全背包问题
问题特点：每件物品可以用无限次（只要背包容量允许）。
问题分析：
与0-1背包问题类似，但状态转移方程有所不同：
- 对于第i件物品，可以选择放0次、1次、2次…直到背包容量不允许
动态规划解法：
public static int knapsackComplete(int[] weights, int[] values, int capacity) { int n = weights.length; // 创建dp数组，dp[j]表示背包容量为j时能获得的最大价值 int[] dp = new int[capacity + 1]; // 填充dp数组 for (int i = 0; i < n; i++) { // 注意这里要从前往后遍历，允许物品被重复使用 for (int j = weights[i]; j <= capacity; j++) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); } } return dp[capacity]; // 返回最终结果}图解过程：
假设有2件物品，重量分别为[2, 3]，价值分别为[3, 4]，背包容量为5。
- 初始化dp数组：所有dp[j]都为0
- i=0 (物品0):
- j=2: dp[2] = max(dp[2], dp[0] + 3) = max(0, 0 + 3) = 3
- j=3: dp[3] = max(dp[3], dp[1] + 3) = max(0, 0 + 3) = 3
- j=4: dp[4] = max(dp[4], dp[2] + 3) = max(0, 3 + 3) = 6
- j=5: dp[5] = max(dp[5], dp[3] + 3) = max(0, 3 + 3) = 6
- i=1 (物品1):
- j=3: dp[3] = max(dp[3], dp[0] + 4) = max(3, 0 + 4) = 4
- j=4: dp[4] = max(dp[4], dp[1] + 4) = max(6, 0 + 4) = 6
- j=5: dp[5] = max(dp[5], dp[2] + 4) = max(6, 3 + 4) = 7
最终dp数组：[0, 0, 3, 4, 6, 7]，结果是7，表示最大价值为7。
背包问题的变种：
- 多重背包问题：每种物品有特定的数量限制
- 分组背包问题：物品分为多个组，每组最多选一个物品
- 二维背包问题：背包有两种容量限制（如重量和体积）
应用场景：
背包问题在资源分配、投资决策、物流规划等地方有广泛应用。理解背包问题对于掌握动态规划思想至关重要。
编辑距离
问题描述：
给定两个单词word1和word2，计算将word1转换成word2所使用的最少操作数。你可以对一个单词进行三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
例如，将\"horse\"转换为\"ros\"的最少操作数是3：
- 将’h’替换为’r’：horse -> rorse
- 删除’r’：rorse -> rose
- 删除’e’：rose -> ros
生活例子：
想象你在使用文字处理软件，需要将一篇文章中的某个单词修改为另一个单词。编辑距离就是你需要进行的最少键盘操作次数。这在拼写检查、DNA序列比对、语音识别等地方有广泛应用。
问题分析：
这是一个典型的动态规划问题。我们需要定义状态和状态转移方程：
-
定义状态：dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最少操作数。
-
状态转移方程：
- 如果word1[i-1] == word2[j-1]（当前字符相同），则dp[i][j] = dp[i-1][j-1]（不需要额外操作）
- 否则，dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])，分别对应替换、删除和插入操作
-
初始条件：
- dp[i][0] = i（将word1的前i个字符全部删除）
- dp[0][j] = j（插入word2的前j个字符）
动态规划解法：
public static int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); // dp[i][j]表示word1的前i个字符转换到word2的前j个字符需要的最少操作数 int[][] dp = new int[m + 1][n + 1]; // 初始化边界条件 for (int i = 0; i <= m; i++) { dp[i][0] = i; // 将word1的前i个字符全部删除 } for (int j = 0; j <= n; j++) { dp[0][j] = j; // 插入word2的前j个字符 } // 填充dp数组 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { // 当前字符相同，不需要操作 dp[i][j] = dp[i - 1][j - 1]; } else { // 当前字符不同，取三种操作的最小值 dp[i][j] = 1 + Math.min( dp[i - 1][j - 1], // 替换操作 Math.min( dp[i - 1][j], // 删除操作 dp[i][j - 1] // 插入操作 ) ); } } } return dp[m][n]; // 返回最终结果}图解过程：
以word1 = “horse”，word2 = \"ros\"为例：
- 初始化dp数组：
\"\" r o s\"\" 0 1 2 3h 1 ? ? ?o 2 ? ? ?r 3 ? ? ?s 4 ? ? ?e 5 ? ? ?-
填充dp数组：
- dp[1][1]：\'h’和’r’不同，取min(dp[0][0]+1, dp[0][1]+1, dp[1][0]+1) = min(1, 2, 2) = 1
- dp[1][2]：\'h’和’o’不同，取min(dp[0][1]+1, dp[0][2]+1, dp[1][1]+1) = min(2, 3, 2) = 2
- 依此类推…
-
最终dp数组：
\"\" r o s\"\" 0 1 2 3h 1 1 2 3o 2 2 1 2r 3 2 2 2s 4 3 3 2e 5 4 4 3- 结果是dp[5][3] = 3，表示最少需要3次操作。
操作路径追踪：
我们可以通过回溯dp数组来找出具体的操作步骤：
- 从dp[5][3]开始，比较’e’和’s’：不同，查看dp[4][2]、dp[4][3]和dp[5][2]中的最小值
- dp[4][3] = 2是最小值，表示删除’e’（从word1的末尾删除）
- 从dp[4][3]开始，比较’s’和’s’：相同，移动到dp[3][2]
- 从dp[3][2]开始，比较’r’和’o’：不同，查看最小值
- dp[2][1] = 2是最小值，表示删除’r’
- 从dp[2][1]开始，比较’o’和’r’：不同，查看最小值
- dp[1][0] = 1是最小值，表示替换’h’为’r’
因此，操作步骤是：替换’h’为’r’，删除’r’，删除’e’。
性能分析：
- 时间复杂度：O(m*n)，其中m和n分别是两个字符串的长度
- 空间复杂度：O(m*n)，需要一个m+1行n+1列的dp数组
应用场景：
- 拼写检查：找出与错误单词最相似的正确单词
- DNA序列比对：计算两个DNA序列的相似度
- 语音识别：评估识别结果与实际文本的差异
- 机器翻译：评估翻译质量
- 文本相似度分析：判断两段文本的相似程度
