PricingLoginStart free
DSA Interview Prep · 课时

0/1 背包与空间优化

推导 0/1 背包递推式，填充二维表，然后通过逆序遍历容量将其压缩为一维数组。

第 1 / 4 课13 个步骤

0/1 背包与空间优化 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

0/1 背包问题

0/1 背包问题：给定 n 个物品，每个物品的重量为 w[i]、价值为 v[i]，以及容量为 W 的背包，请选择物品，使总价值最大且不超过容量。每个物品恰好选择一次（0 = 不选，1 = 选择）。这是包括分割等和子集、目标和在内的大量面试 DP 问题的典型范式。

DP 状态与递推式

将 dp[i][c] 定义为使用前 i 个物品、容量为 c 时的最大价值。对于物品 i，有两种选择：不选它（dp[i-1][c]），或者在 w[i] <= c 时选择它（dp[i-1][c-w[i]] + v[i]）。递推式为：当 w[i] <= c 时，dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])；否则 dp[i][c] = dp[i-1][c]。基本情况：对于所有 c，都有 dp[0][c] = 0。

二维 DP 表实现

二维表共有 (n+1) x (W+1) 个单元，针对每个物品逐行填充。填完所有行后，dp[n][W] 就是最大价值。该算法的时间复杂度为 O(n × W)，空间复杂度为 O(n × W)——这是伪多项式复杂度，在 W 较小时效率很高。

def knapsack_2d(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    
    for i in range(1, n+1):
        w, v = weights[i-1], values[i-1]
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]  # skip item i
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    
    return dp[n][W]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8))  # 10

为什么一维 DP 要逆序遍历容量

关键观察是：第 i 行只依赖第 i-1 行。因此，我们可以使用单个一维数组并原地更新。不过，如果从左到右（从小到大）遍历容量 c，物品 i 可能会被计算两次——因为 c-w[i] 的更新值可能已经包含了物品 i。从右到左（从大到小）遍历，可以确保每个物品在每次行更新中最多使用一次。

# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
#     dp[c] = max(dp[c], dp[c-w] + v)   <-- dp[c-w] may already use item i

# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
#     dp[c] = max(dp[c], dp[c-w] + v)   <-- dp[c-w] still from previous row

一维空间优化实现

只保留一个数组，并将容量从 W 递减遍历到 w[i]，就能以 O(W) 的空间复杂度得到与二维表相同的结果。时间复杂度仍为 O(n × W)。必须牢记这一空间优化——面试官经常要求您将二维背包降为一维。

def knapsack_1d(weights, values, W):
    dp = [0] * (W + 1)
    
    for i in range(len(weights)):
        w, v = weights[i], values[i]
        for c in range(W, w - 1, -1):  # iterate RIGHT TO LEFT
            dp[c] = max(dp[c], dp[c - w] + v)
    
    return dp[W]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8))  # 10

重建 selected 项目

要找出哪些项目被 selected，需要完整的二维表。填表后，从 dp[n][W] 开始反向追踪：如果 dp[i][c] != dp[i-1][c]，说明物品 i 被选入了——从 c 中减去它的重量，然后移动到第 i-1 行。持续这一过程，直到 i = 0。一维优化会舍弃这种重建能力。

def knapsack_with_items(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        w, v = weights[i-1], values[i-1]
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    
    # Reconstruct
    selected, c = [], W
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i-1][c]:
            selected.append(i-1)
            c -= weights[i-1]
    return dp[n][W], selected[::-1]

print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))

实践示例：最大化总价值

考虑以下物品：weights=[2,3,4,5]、values=[3,4,5,6]，以及 W=8。最优选择是重量为 3（价值为 4）和重量为 5（价值为 6）的物品——总重量为 8，价值为 10。也可以选择重量为 2 和 5 的物品——总价值为 9；或者选择重量为 2 和 3 的物品——价值为 7。DP 能正确找出最大值 10。请注意，贪心方法（选择价值与重量比最高的物品）会先选择比值为 1.5 的物品（重量为 2，价值为 3），但这并不总是最优的。

分数背包与 0/1 背包

在分数背包中，您可以只取物品的一部分。对价值与重量的比值进行排序后，即可使用贪心方法求解。在0/1 背包中，物品不可分割，贪心方法会失败，因此必须使用 DP。面试官会利用这一差别来检验您是否知道贪心方法何时适用。如果被问到分数背包，请立即提到排序加贪心；如果是 0/1 背包，则应采用 DP。

# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
    items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
    total = 0
    for v, w in items:
        if W >= w:
            total += v; W -= w
        else:
            total += v * (W / w); break
    return total

print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))

伪多项式时间复杂度

0/1 背包是 NP-complete 问题，但我们可以在 O(nW) 时间内求解它。这个矛盾的原因在于 O(nW) 是伪多项式复杂度：W 是一个数值，而不是输入规模。W 的二进制表示需要 O(log W) 位，因此真正的复杂度是 O(n × 2^(log W))，相对于输入规模而言是指数级的。当 W 较小时（例如 10⁴），DP 是实用的；当 W 可能达到 10⁹ 时，就需要采用其他方法。

面试追问：容量很大时怎么办

如果面试官将 W 限制为非常大的值（例如 10⁹），但 n 较小，标准 DP 就会失效。可选方法包括：(1) 使用 O(2^(n/2) × n) 时间的折半搜索，(2) 对分数背包变体使用贪心近似，或者 (3) 使用分支限界。对于大多数 W <= 10⁵ 的面试题，采用逆序遍历的一维 DP 是预期答案。

大容量下的折半搜索

当 W 非常大而 n 较小时（例如 n=40），标准的 O(nW) DP 不可行，但暴力枚举 2^n 个子集又太慢。折半搜索会将物品分成两半，分别枚举每一半的全部 2^(n/2) 个子集，然后寻找最优配对。先按重量对其中一半排序，再对另一半的每个子集使用二分搜索，在容量限制内找到最佳配对。该算法的复杂度为 O(2^(n/2) × n)，当 n 不超过 40 时具有实用性。

快速检查

测试您对本课数据结构 & 算法——编程面试准备相关概念的理解。

在交互式课程中回答

课程回顾

本课您学习了：0/1 背包 DP 的状态 dp[i][c] 表示使用 i 个物品、容量为 c 时的最大价值，递推式会对每个物品做不选或选择的决策，以及一维空间优化通过从右到左遍历容量来防止重复计算物品。接下来我们将学习物品可以重复使用的完全背包，并将其应用于硬币兑换 II。

免费开始

用 AI 导师学习 Python — 免费

在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。

课程
30
课程
120
免费开始学习查看完整课程

常见问题解答

「0/1 背包与空间优化」课时是免费的吗？

是的 — 「0/1 背包与空间优化」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

「0/1 背包与空间优化」这节课中我会学到什么？

推导 0/1 背包递推式，填充二维表，然后通过逆序遍历容量将其压缩为一维数组。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。

「0/1 背包与空间优化」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 0/1 背包与空间优化
  2. 完全背包与零钱兑换 II
  3. 等和子集分割
  4. 带正负号的目标和
← 返回 DSA Interview Prep