Part 5.1：DP 入门：背包问题

引言：小偷的“最优决策”

想象你是一个聪明的小偷，潜入了一家珠宝店。你背着一个容量有限的背包（比如最多能装 10 公斤），面前摆着一堆琳琅满目的珠宝，每件珠宝都有自己的重量和价值。你的目标是：在不超过背包容量的前提下，偷走总价值最高的珠宝。

你会怎么做？

先拿最贵的？但它可能很重，占满了背包，导致总价值不高。
先拿最轻的？但它们可能不值钱，装满了背包也发不了大财。
先拿“性价比”最高的（价值/重量）？这似乎是个不错的贪心策略，但事实证明它不一定能得到最优解。

这个问题，就是算法世界里鼎鼎大名的**背包问题 (Knapsack Problem)**，具体来说是 0-1 背包问题（因为每件物品要么拿，要么不拿，只有 0 和 1 两种选择）。

这个问题是动态规划 (Dynamic Programming, DP) 的经典入门案例。DP 是一种强大的算法思想，它能将一个复杂的问题分解为更小的、可重复的子问题，通过求解子问题的最优解来构建出原问题的最优解。

为什么背包问题如此重要？

面试价值：背包问题是 DP 领域的“Hello, World!”。在面试中，如果你能清晰地写出背包问题的 DP 解法，并解释其状态转移方程，就证明你已经具备了 DP 的入门能力。
工程价值：背包问题是一个泛化的资源分配模型。其思想可以应用于广告投放（有限预算下的最大化收益）、任务调度（有限时间内的最大化产出）、投资组合（有限风险下的最大化回报）等无数现实场景。

本文将以 0-1 背包问题为切入点，带你一步步踏入动态规划的殿堂，理解其核心思想，并掌握从问题建模到代码实现的全过程。

背景知识：动态规划的两大基石

一个问题能否用动态规划解决，取决于它是否满足两个核心特性：最优子结构和重叠子问题。

最优子结构 (Optimal Substructure)
- 定义：一个问题的最优解包含其子问题的最优解。
- 直觉：如果你的“全局最优策略”是由一系列“局部最优策略”组成的，那么它就具备最优子结构。
- 背包问题中的体现：假设你已经制定了偷前 i 件物品的最优方案。那么，这个方案对于前 i-1 件物品来说，也必然是在相应背包容量下的最优方案。否则，你就可以用一个更好的前 i-1 件物品的方案来替换，从而得到一个更好的前 i 件物品的方案，产生矛盾。
重叠子问题 (Overlapping Subproblems)
- 定义：在递归求解的过程中，许多相同的子问题会被反复计算多次。
- 直觉：如果你在解题时发现自己总是在重复计算同样的东西，那就说明存在重叠子问题。
- 背包问题中的体现：在考虑是否要拿第 i 件物品时，我们可能会问“背包容量为 w 时，前 i-1 件物品的最大价值是多少？”。在后续的计算中，我们可能又会遇到同样的问题。DP 的核心就是用一个“备忘录”（通常是数组或哈希表）来记录这些子问题的解，避免重复计算。

详细算法原理：0-1 背包问题

1. 算法的“直觉”：二维决策表

面对 N 件物品和一个容量为 W 的背包，我们如何做决策？

动态规划的思路是填一张二维表格。这张表格 dp[i][j] 的含义是：

**dp[i][j]**：在前 i 件物品中，当背包容量为 j 时，我们能获得的最大总价值。

我们的最终目标就是填满这张表，找到 dp[N][W] 的值。

如何填写这张表呢？对于第 i 件物品，我们只有两个选择：

不放第 i 件物品：那么，当前的最大价值就等于“只考虑前 i-1 件物品，在容量为 j 的背包里能获得的最大价值”，即 dp[i-1][j]。
放第 i 件物品：这个决策有一个前提——背包必须能装得下（即 j >= weight[i]）。如果能装下，那么当前背包的价值就等于“第 i 件物品的价值”加上“只考虑前 i-1 件物品，在剩余容量 j - weight[i] 的背包里能获得的最大价值”，即 value[i] + dp[i-1][j - weight[i]]。

我们在这两个选择中，取一个能使价值最大化的，就完成了决策。

2. 严谨原理：状态定义与状态转移方程

状态定义：dp[i][j] 表示从前 i 件物品中任意选择，放入容量为 j 的背包中所能获得的最大价值。
状态转移方程：
- 如果**当前背包容量 j 小于第 i 件物品的重量 weight[i-1]**（注意索引，weight 数组通常从 0 开始），那么第 i 件物品肯定放不进去。此时：
  dp[i][j] = dp[i-1][j]
- 如果**当前背包容量 j 大于等于第 i 件物品的重量 weight[i-1]**，我们需要做出选择：
  dp[i][j] = max(不放第 i 件, 放第 i 件)
  dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i-1][j - weight[i-1]])
**初始化 (Base Case)**：
- dp[0][j] = 0 (当没有物品可选时，最大价值为 0)
- dp[i][0] = 0 (当背包容量为 0 时，最大价值为 0)

步骤分解 (Step-by-step)

创建 DP 表：创建一个 (N+1) x (W+1) 的二维数组 dp，并全部初始化为 0。
外层循环：遍历物品 i，从 1 到 N。
内层循环：遍历背包容量 j，从 1 到 W。
状态转移：在循环体内，根据状态转移方程填写 dp[i][j] 的值。
返回结果：循环结束后，dp[N][W] 就是最终答案。

动画式案例

假设我们有 3 件物品，背包容量为 4。

物品	重量 (w)	价值 (v)
0	1	15
1	3	20
2	4	30

1. 初始化 dp 表 (4x5)

   j=0  j=1  j=2  j=3  j=4
i=0 [ 0,   0,   0,   0,   0 ]
i=1 [ 0,   0,   0,   0,   0 ]
i=2 [ 0,   0,   0,   0,   0 ]
i=3 [ 0,   0,   0,   0,   0 ]

2. i = 1 (考虑物品 0: w=1, v=15)

dp[1][1] = max(dp[0][1], v[0]+dp[0][0]) = max(0, 15+0) = 15
dp[1][2] = max(dp[0][2], v[0]+dp[0][1]) = max(0, 15+0) = 15
… (对于 j>=1, 都能放下物品0)

   j=0  j=1  j=2  j=3  j=4
i=0 [ 0,   0,   0,   0,   0 ]
i=1 [ 0,  15,  15,  15,  15 ]
i=2 [ 0,   0,   0,   0,   0 ]
i=3 [ 0,   0,   0,   0,   0 ]

3. i = 2 (考虑物品 1: w=3, v=20)

dp[2][1]: 装不下物品1, dp[2][1] = dp[1][1] = 15
dp[2][2]: 装不下物品1, dp[2][2] = dp[1][2] = 15
dp[2][3]: max(dp[1][3], v[1]+dp[1][0]) = max(15, 20+0) = 20
dp[2][4]: max(dp[1][4], v[1]+dp[1][1]) = max(15, 20+15) = 35

   j=0  j=1  j=2  j=3  j=4
i=0 [ 0,   0,   0,   0,   0 ]
i=1 [ 0,  15,  15,  15,  15 ]
i=2 [ 0,  15,  15,  20,  35 ]
i=3 [ 0,   0,   0,   0,   0 ]

4. i = 3 (考虑物品 2: w=4, v=30)

dp[3][1..3]: 装不下物品2, dp[3][j] = dp[2][j]
dp[3][4]: max(dp[2][4], v[2]+dp[2][0]) = max(35, 30+0) = 35

最终 DP 表

   j=0  j=1  j=2  j=3  j=4
i=0 [ 0,   0,   0,   0,   0 ]
i=1 [ 0,  15,  15,  15,  15 ]
i=2 [ 0,  15,  15,  20,  35 ]
i=3 [ 0,  15,  15,  20,  35 ]

最终答案是 dp[3][4] = 35。

Python 实现

二维 DP 实现

def knapsack_01_2d(weights, values, capacity):
    """
    0-1 背包问题的二维动态规划解法。
    :param weights: 物品重量列表
    :param values: 物品价值列表
    :param capacity: 背包容量
    :return: 最大价值
    """
    n = len(weights)
    # dp[i][j]: 前 i 个物品，容量为 j 时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight = weights[i - 1]
        value = values[i - 1]
        for j in range(1, capacity + 1):
            if j < weight:
                # 背包容量不足，无法放入第 i 个物品
                dp[i][j] = dp[i - 1][j]
            else:
                # 选择不放或放第 i 个物品
                dp[i][j] = max(dp[i - 1][j], value + dp[i - 1][j - weight])

    return dp[n][capacity]

# --- 案例测试 ---
weights = [1, 3, 4]
values = [15, 20, 30]
capacity = 4
max_value = knapsack_01_2d(weights, values, capacity)
print(f"最大价值是: {max_value}") # 输出: 最大价值是: 35

空间优化：一维 DP 实现

观察状态转移方程 dp[i][j] = max(dp[i-1][j], ...)，我们发现计算第 i 行的状态只依赖于第 i-1 行。这提示我们可以用一个一维数组来代替二维数组，进行状态压缩。

def knapsack_01_1d(weights, values, capacity):
    """
    0-1 背包问题的一维动态规划（空间优化）解法。
    """
    n = len(weights)
    # dp[j]: 容量为 j 时的最大价值
    dp = [0] * (capacity + 1)

    for i in range(n):
        weight = weights[i]
        value = values[i]
        # 必须倒序遍历，以保证 dp[j - weight] 是上一轮（i-1）的状态
        for j in range(capacity, weight - 1, -1):
            dp[j] = max(dp[j], value + dp[j - weight])

    return dp[capacity]

# --- 案例测试 ---
max_value_1d = knapsack_01_1d(weights, values, capacity)
print(f"空间优化后的最大价值是: {max_value_1d}") # 输出: 空间优化后的最大价值是: 35

关键点：内层循环 j 必须从后往前遍历。这是为了确保当我们计算 dp[j] 时，所依赖的 dp[j - weight] 还是上一轮循环（即 i-1）的结果，而不是本轮已经被更新过的值。

复杂度推导过程

时间复杂度

我们需要填充整个 dp 表。
外层循环遍历 N 个物品。
内层循环遍历背包容量 W。

总的计算量是 N * W。

因此，时间复杂度为 **O(N * W)**。

空间复杂度

二维 DP 实现：我们需要一个 (N+1) x (W+1) 的二维数组。因此，空间复杂度为 **O(N * W)**。
一维 DP 实现：我们只需要一个长度为 W+1 的一维数组。因此，空间复杂度优化为 **O(W)**。

优势 / 劣势 / 易错点

优势

保证最优解：与贪心算法不同，动态规划通过遍历所有子问题的最优解，保证能找到全局最优解。
思想普适：DP 的思想可以应用于各种各样的优化问题。

劣势

伪多项式时间：O(N * W) 的复杂度看起来是多项式时间，但它与 W 的大小有关。如果 W 非常大（例如 10^9），这个算法就会超时。因此它被称为伪多项式时间算法。
不易理解：状态定义和状态转移方程的推导是 DP 的难点，需要大量的练习。

易错点

数组索引：dp[i] 对应的是第 i-1 个物品，注意索引的转换。
空间优化时的遍历顺序：一维 DP 实现中，内层循环必须倒序遍历，否则会重复使用同一个物品，变成了完全背包问题。

适用场景

0-1 背包问题模型适用于所有满足以下条件的场景：

面临一系列选择。
每个选择都有两种状态（选或不选）。
存在一个资源限制（如重量、成本、时间）。
目标是最大化或最小化某个指标（如价值、收益）。

现实案例：

广告投放：有 N 个广告渠道，每个渠道有成本和预期收益，总预算有限，求最大化总收益。
任务选择：有 N 个任务，每个任务有耗时和价值，总时间有限，求最大化总价值。

扩展算法 & 进阶方向

背包问题是一个庞大的家族，0-1 背包只是起点。

完全背包 (Unbounded Knapsack)：每种物品有无限件。状态转移方程变为 dp[j] = max(dp[j], value + dp[j - weight])，内层循环正序遍历即可。
**多重背包 (Bounded Knapsack)**：每种物品有有限的 k 件。可以将其拆分为 k 个 0-1 背包问题，或使用二进制优化。
**分组背包 (Grouped Knapsack)**：物品被分成若干组，每组中最多只能选一件。

总结

动态规划是算法学习中一座必须翻越的大山，而 0-1 背包问题正是攀登这座山的起点。通过本文，我们学习了：

✅ DP 的核心思想：最优子结构与重叠子问题。
✅ 0-1 背包的状态定义：dp[i][j] 代表前 i 件物品在容量 j 下的最大价值。
✅ 状态转移方程：dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i-1][j - weight[i-1]])。
✅ 从二维到一维的空间优化：通过倒序遍历实现状态压缩。
✅ 复杂度：时间 O(N * W)，空间 O(W)（优化后）。

掌握了 0-1 背包，你就拿到了打开动态规划大门的钥匙。在下一篇文章中，我们将探讨另一个经典的 DP 问题——**最长上升子序列 (LIS)**。

大学算法全体系 > Part 5：动态规划

#算法基础 #动态规划 #DP #背包问题 #0-1背包

Part 5.1：DP 入门：背包问题

https://hjjjkh.github.io/posts/5e813b19

作者

李国强

发布于

2025年11月15日

许可协议

Part 2.5：二叉树遍历：理解树的四种核心视角上一篇

Part 7.1：贪心算法——局部最优通向全局最优的艺术下一篇