2025-11-17-关于动态规划(背包问题为例)

动态规划的适用条件#

• 最优子结构：原问题的最优解可由子问题的最优解组合得出。
• 重叠子问题：子问题在递归求解中会被多次计算。

实现方式#

• 自底向上（表格填充）：使用循环从小型子问题开始填充 DP 表格，直至原问题（常见于背包问题）。
• 自顶向下（记忆化递归）：递归求解并使用备忘录存储已计算子问题结果。

问题分析#

• 子问题：考虑前 i 个物品和容量为 j 的背包的最大价值。
• 状态定义：dp[i][j] 表示前 i 个物品在容量 j 下的最大价值。
• 状态转移方程：
  • 不取第 i 个物品：dp[i][j] = dp[i-1][j]
  • 取第 i 个物品（若 j ≥ w_i）：dp[i][j] = dp[i-1][j - w_i] + v_i
  • dp[i][j] = max(以上两种情况)
• 边界：dp[0][j] = 0（无物品），dp[i][0] = 0（容量为 0）

示例#

假设物品：重量 [1, 3, 4]，价值[15, 20, 30]，背包容量 W = 4。 DP 表格填充过程如下所示：

初始状态（i=0，无物品）#

1
容量 w:   0    1    2    3    4
2
物品 i
3
0        [0]  [0]  [0]  [0]  [0]

考虑第 1 个物品（重量 1，价值 15）#

• 对于 w < 1：无法放入，只能取上一行值（0）。
• 对于 w ≥ 1：max(不放入: 0, 放入: 0 + 15) = 15。

1
容量 w:   0    1    2    3    4
2
物品 i
3
0        [0]  [0]  [0]  [0]  [0]
4
1        [0] [15] [15] [15] [15]

考虑第 2 个物品（重量 3，价值 20）#

• 对于每个 w：
  • 如果 w < 3：无法放入，取上一行值。
  • 如果 w ≥ 3：max(不放入: dp[1][w], 放入: dp[1][w-3] + 20)。

计算示例：

• w=3：max(15, 15 + 20) = 35
• w=4：max(15, 15 + 20) = 35

1
容量 w:   0    1    2    3    4
2
物品 i
3
0        [0]  [0]  [0]  [0]  [0]
4
1        [0] [15] [15] [15] [15]
5
2        [0] [15] [15] [35] [35]

考虑第 3 个物品（重量 4，价值 30）#

• 对于每个 w：
  • 如果 w < 4：无法放入，取上一行值。
  • 如果 w ≥ 4：max(不放入: dp[2][w], 放入: dp[2][w-4] + 30)。

计算示例：

• w=4：max(35, 0 + 30) = 35（不放入更好）

1
容量 w:   0    1    2    3    4
2
物品 i
3
0        [0]  [0]  [0]  [0]  [0]
4
1        [0] [15] [15] [15] [15]
5
2        [0] [15] [15] [35] [35]
6
3        [0] [15] [15] [35] [35]

最终结果：dp[3][4] = 35（选择第 1 和第 2 个物品：重量 1+3=4，价值 15+20=35）。

一维 DP 优化过程简要文本模拟#

一维数组从后向前更新（避免覆盖）：

初始 dp: [0, 0, 0, 0, 0]（容量 0 到 4）

第 1 个物品后： [0, 15, 15, 15, 15]

第 2 个物品后： [0, 15, 15, 35, 35]

第 3 个物品后： [0, 15, 15, 35, 35]

复杂度分析#

• 时间复杂度：O(n × capacity)
• 空间复杂度：二维 O(n × capacity)，一维 O(capacity)

伪代码（自底向上）#

1
dp = 二维数组 (n+1) x (W+1)，初始化为 0
2

3
for i = 1 to n:
4
    for j = 1 to W:
5
        if w[i-1] > j:
6
            dp[i][j] = dp[i-1][j]
7
        else:
8
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1])
9

10
返回 dp[n][W]

时间复杂度 O(nW)，空间复杂度 O(nW)（可优化至 O(W) 使用一维数组）

动态规划通过系统地记录子问题解，避免了暴力递归的冗余计算，在组合优化、序列问题等领域广泛应用。理解背包问题有助于掌握 DP 的状态设计与转移核心。

动态规划状态定义与转移#

• 状态：dp[i][w] 表示考虑前 i 个物品（索引 0 到 i-1），背包容量为 w 时的最大价值。
• 转移方程：
  • 如果不放入第 i 个物品：dp[i][w] = dp[i-1][w]
  • 如果放入第 i 个物品（前提 w ≥ weights[i-1]）：dp[i][w] = dp[i-1][w - weights[i-1]] + values[i-1]
  • dp[i][w] = Math.max(不放入, 放入)
• 初始条件：dp[0][w] = 0（无物品），dp[i][0] = 0（容量为 0）。
• 结果：dp[n][capacity]

TypeScript 实现#

以下提供两种实现：标准二维 DP 和空间优化的一维 DP（推荐，后者空间复杂度 O(capacity)）

1
function knapsack01(weights: number[], values: number[], capacity: number): number {
2
    const n = weights.length;
3
    // 创建 (n+1) x (capacity+1) 的二维数组，初始化为 0
4
    const dp: number[][] = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
5

6
    for (let i = 1; i <= n; i++) {
7
        for (let w = 1; w <= capacity; w++) {
8
            if (weights[i - 1] > w) {
9
                // 重量超出，无法放入
10
                dp[i][w] = dp[i - 1][w];
11
            } else {
12
                // 取最大值
13
                dp[i][w] = Math.max(
14
                    dp[i - 1][w],                              // 不放入
15
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]  // 放入
16
                );
17
            }
18
        }
19
    }
20

21
    return dp[n][capacity];
22
}

1
function knapsack01Optimized(weights: number[], values: number[], capacity: number): number {
2
    const n = weights.length;
3
    // 一维数组，dp[w] 表示容量 w 时的最大价值
4
    const dp: number[] = Array(capacity + 1).fill(0);
5

6
    for (let i = 0; i < n; i++) {
7
        // 从后向前遍历（防止覆盖前状态）
8
        for (let w = capacity; w >= weights[i]; w--) {
9
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
10
        }
11
    }
12

13
    return dp[capacity];
14
}

示例#

1
const weights = [1, 3, 4];
2
const values = [15, 20, 30];
3
const capacity = 4;
4

5
console.log(knapsack01Optimized(weights, values, capacity));  // 输出 35（放入重量 1 和 3 的物品）

• 物品数量 n = 3
• 重量 weights = [1, 3, 4]
• 价值 values = [15, 20, 30]
• 背包容量 capacity = 4