DevDocs

主题

背包问题 ​

本章目标：彻底搞懂 0-1 背包、完全背包、多重背包，掌握空间优化技巧。

你将学到 ​

  • 0-1 背包的状态转移与空间优化
  • 完全背包的模板
  • 多重背包的二进制拆分
  • 背包问题在面试中的变形（硬币、分割、组合数）
  • 一维 DP 的遍历方向（0-1 逆序 vs 完全正序）

1. 概念 ​

背包问题是动态规划最经典的模型之一。核心场景：有容量有限的背包和一组物品，每种物品有重量和价值，如何选择使背包内总价值最大。

分类：

  • 0-1 背包：每种物品只有一个，选或不选
  • 完全背包：每种物品无限个
  • 多重背包：第 i 种物品有 c[i] 个
  • 分组背包：物品分多组，每组最多选一个

2. 核心模板 ​

0-1 背包 ​

python
def knapsack_01(weight, value, capacity):
    """
    n 个物品，每个有重量 weight[i] 和价值 value[i]
    背包容量为 capacity，每个物品最多选一次
    """
    n = len(weight)
    # 二维写法
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(capacity + 1):
            dp[i][j] = dp[i-1][j]  # 不选第 i 个
            if j >= weight[i-1]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-weight[i-1]] + value[i-1])
    return dp[n][capacity]

def knapsack_01_optimized(weight, value, capacity):
    """一维空间优化——内层必须逆序遍历"""
    dp = [0] * (capacity + 1)
    for i in range(len(weight)):
        for j in range(capacity, weight[i] - 1, -1):  # 逆序！
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    return dp[capacity]

为什么 0-1 背包要逆序？ 正序遍历时 dp[j-weight[i]] 可能已经包含了第 i 个物品（因为在本轮已被更新），导致同一物品被选了多次。

完全背包 ​

python
def knapsack_complete(weight, value, capacity):
    """每种物品无限个——内层正序遍历"""
    dp = [0] * (capacity + 1)
    for i in range(len(weight)):
        for j in range(weight[i], capacity + 1):  # 正序！
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    return dp[capacity]

复杂度 ​

  • 0-1 背包：时间 O(nW)，空间 O(W)（优化后）
  • 完全背包：时间 O(nW)，空间 O(W)

3. 面试变形 ​

LeetCode 416 · 分割等和子集（0-1 背包） ​

题意：判断数组能否分成两个和相等的子集。

思路：转化为容量为 sum/2 的 0-1 背包可行性问题。

python
def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):  # 逆序
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

LeetCode 322 · 零钱兑换（完全背包） ​

题意：给定硬币面额和金额，求最少硬币数。

思路：完全背包，求最小值。

python
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for j in range(coin, amount + 1):  # 正序
            dp[j] = min(dp[j], dp[j - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

LeetCode 518 · 零钱兑换 II（完全背包求组合数） ​

题意：给定硬币面额和金额，求可以凑成的组合数。

思路：完全背包求方案数。注意外层遍历硬币（组合数），如果求排列数则外层遍历金额。

python
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:  # 外层遍历硬币 → 组合数
        for j in range(coin, amount + 1):
            dp[j] += dp[j - coin]
    return dp[amount]

LeetCode 494 · 目标和（0-1 背包求方案数） ​

题意：给数组每个元素前加 + 或 -，使结果等于目标值，求方案数。

思路：转化为子集和问题。设加正号元素之和为 P，负号之和为 N，则 P-N=target，P=(sum+target)/2。转化为 0-1 背包求选若干元素之和等于 P 的方案数。

python
def findTargetSumWays(nums, target):
    total = sum(nums)
    if (total + target) % 2 != 0 or total + target < 0:
        return 0
    P = (total + target) // 2
    dp = [0] * (P + 1)
    dp[0] = 1
    for num in nums:
        for j in range(P, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[P]

LeetCode 279 · 完全平方数（完全背包） ​

思路：物品是 1,4,9,16,...，容量为 n，求最少物品数。

python
def numSquares(n):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, int(n**0.5) + 1):
        square = i * i
        for j in range(square, n + 1):
            dp[j] = min(dp[j], dp[j - square] + 1)
    return dp[n]

4. 易错点 ​

  • ⚠️ 0-1 背包逆序，完全背包正序——这是最容易犯的错
  • ⚠️ 求组合数（不考虑顺序）外层遍历物品，求排列数（考虑顺序）外层遍历容量
  • ⚠️ 初始化：求最大值用 0，求恰好装满用 dp[0]=0 其余 -inf
  • ⚠️ 分割等和子集先判断总和奇偶性

5. 推荐刷题清单 ​

题号题名难度关键
322零钱兑换Medium完全背包最小值
518零钱兑换 IIMedium完全背包组合数
416分割等和子集Medium0-1 背包可行性
494目标和Medium0-1 背包方案数
279完全平方数Medium完全背包
377组合总和 IVMedium完全背包排列数

延伸阅读 ​

基于 VitePress 构建 · 部署于 Cloudflare Pages

Copyright © 2024-present DevDocs