第10章：背包问题家族

背包问题是动态规划中最经典的问题家族，它不仅频繁出现在算法面试中，更重要的是它代表了一类"资源分配"的优化问题。对于有数学背景的工程师来说，背包问题可以理解为在约束条件下的离散优化——给定有限的资源（背包容量），如何选择物品使得价值最大化。本章将系统地介绍背包问题的各种变体，从最基础的01背包到复杂的多重背包，以及如何识别和转化实际问题为背包模型。

10.1 01背包：选或不选的决策

10.1.1 问题本质与状态定义

01背包是最基础的背包问题：有 $n$ 个物品，第 $i$ 个物品的重量为 $w_i$，价值为 $v_i$，背包容量为 $W$。每个物品只能选择一次（0或1），求最大价值。

从函数式编程的角度，这是一个典型的折叠（fold）操作，每次决策都是对当前状态的转换：

决策树视角:
           root
         /      \
    选物品1    不选物品1
      /  \       /  \
   选2   不选2  选2  不选2
   ...   ...   ...  ...

状态定义的艺术在于找到最小的信息集合来唯一确定子问题：

$dp[i][j]$ = 前 $i$ 个物品，背包容量为 $j$ 时的最大价值
状态转移：$dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)$

10.1.2 LeetCode 416：分割等和子集

这是01背包的经典变体：能否将数组分成两个和相等的子集？

问题转化：

目标和 = 数组总和的一半
物品 = 数组元素（重量=价值=元素值）
问题变为：能否恰好装满容量为 target 的背包？

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    # dp[i] 表示是否能凑出和为 i
    dp = [False] * (target + 1)
    dp[0] = True  # 空集的和为0

    for num in nums:
        # 倒序遍历，避免重复使用
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]

    return dp[target]

空间优化的关键：倒序遍历确保每个元素只使用一次。这利用了状态转移只依赖上一行的特性。

10.1.3 LeetCode 494：目标和

给数组每个元素添加 + 或 - 号，使得表达式结果为目标值，求方案数。

巧妙转化：设 P 为加正号的数集合，N 为加负号的数集合：

$sum(P) - sum(N) = target$
$sum(P) + sum(N) = sum(nums)$
两式相加：$2 \times sum(P) = target + sum(nums)$
因此：$sum(P) = \frac{target + sum(nums)}{2}$

问题转化为：选择一些数，使其和恰好为 $(target + sum(nums)) / 2$ 的方案数。

def findTargetSumWays(nums, target):
    total = sum(nums)
    # 无解的情况
    if abs(target) > total or (target + total) % 2 != 0:
        return 0

    pos_sum = (target + total) // 2
    # dp[i] 表示和为 i 的方案数
    dp = [0] * (pos_sum + 1)
    dp[0] = 1  # 空集是一种方案

    for num in nums:
        for j in range(pos_sum, num - 1, -1):
            dp[j] += dp[j - num]  # 累加方案数

    return dp[pos_sum]

10.1.4 优化技巧与陷阱

初始化陷阱：dp[0] 的含义要清晰 - 求最大值时：dp[0] = 0（空背包价值为0） - 求方案数时：dp[0] = 1（空集是一种方案） - 求恰好装满时：除 dp[0] = 0 外，其余初始化为 -∞
遍历顺序：一维数组必须倒序，二维数组可以正序
边界处理：注意数组越界，特别是 j - weight[i] >= 0

10.2 完全背包：无限使用的优化

10.2.1 与01背包的本质区别

完全背包允许每个物品使用无限次。看似更复杂，实际上状态转移更简单：

01背包：$dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)$（从上一行转移）完全背包：$dp[i][j] = \max(dp[i-1][j], dp[i][j-w_i] + v_i)$（从当前行转移）

空间优化后的关键区别：

01背包：倒序遍历（避免重复使用）
完全背包：正序遍历（允许重复使用）

10.2.2 LeetCode 322：零钱兑换

最少硬币数问题：硬币无限供应，凑出目标金额的最少硬币数。

def coinChange(coins, amount):
    # dp[i] = 凑出金额 i 的最少硬币数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 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

10.2.3 LeetCode 518：零钱兑换 II

方案计数问题：凑出目标金额的组合数（不是排列数）。

关键区别：组合 vs 排列

组合：{1,2} 和 {2,1} 是同一种方案
排列：[1,2] 和 [2,1] 是不同方案

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1  # 凑出0元有1种方案（不选）

    # 外层循环物品，内层循环容量 => 组合数
    for coin in coins:
        for j in range(coin, amount + 1):
            dp[j] += dp[j - coin]

    return dp[amount]

10.2.4 LeetCode 377：组合总和 IV

求排列数而非组合数：

def combinationSum4(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    # 外层循环容量，内层循环物品 => 排列数
    for j in range(1, target + 1):
        for num in nums:
            if j >= num:
                dp[j] += dp[j - num]

    return dp[target]

循环顺序的本质：

物品在外：先固定物品顺序，保证组合唯一性
容量在外：每个位置都尝试所有物品，允许不同顺序

10.3 多重背包与分组背包

10.3.1 多重背包：有限数量的物品

每个物品有限定的数量 $c_i$。朴素方法是将其展开为01背包，但可以用二进制优化：

将数量 $c$ 分解为 $1, 2, 4, ..., 2^k, c - 2^{k+1} + 1$，这样可以组合出 $[0, c]$ 内的任意数量。

def multipleKnapsack(weights, values, counts, capacity):
    # 二进制拆分
    new_weights, new_values = [], []
    for i in range(len(weights)):
        c = counts[i]
        k = 1
        while k <= c:
            new_weights.append(weights[i] * k)
            new_values.append(values[i] * k)
            c -= k
            k *= 2
        if c > 0:
            new_weights.append(weights[i] * c)
            new_values.append(values[i] * c)

    # 转化为01背包
    dp = [0] * (capacity + 1)
    for i in range(len(new_weights)):
        for j in range(capacity, new_weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - new_weights[i]] + new_values[i])

    return dp[capacity]

10.3.2 LeetCode 474：一和零

特殊的多维背包问题：每个字符串消耗两种资源（0的个数和1的个数）。

def findMaxForm(strs, m, n):
    # dp[i][j] = 最多i个0和j个1时的最大子集大小
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for s in strs:
        zeros = s.count('0')
        ones = s.count('1')
        # 01背包的倒序遍历
        for i in range(m, zeros - 1, -1):
            for j in range(n, ones - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)

    return dp[m][n]

10.3.3 分组背包：互斥选择

物品分为若干组，每组最多选一个。这是01背包的推广：

def groupKnapsack(groups, capacity):
    dp = [0] * (capacity + 1)

    for group in groups:  # 遍历每个组
        # 倒序遍历容量（01背包）
        for j in range(capacity, -1, -1):
            # 尝试选择组内的每个物品
            for weight, value in group:
                if j >= weight:
                    dp[j] = max(dp[j], dp[j - weight] + value)

    return dp[capacity]

10.4 背包的变体：恰好装满、方案计数

10.4.1 恰好装满 vs 不超过容量

两种问题的初始化不同：

不超过容量：dp[0...W] = 0（任何容量都可以不装）
恰好装满：dp[0] = 0, dp[1...W] = -∞（只有容量0可以恰好装满）

10.4.2 LeetCode 139：单词拆分

字符串能否拆分为字典中的单词？这是一个"恰好覆盖"的背包变体：

def wordBreak(s, wordDict):
    n = len(s)
    # dp[i] = s[0:i] 能否被拆分
    dp = [False] * (n + 1)
    dp[0] = True  # 空串

    for i in range(1, n + 1):
        for word in wordDict:
            length = len(word)
            if i >= length and s[i-length:i] == word:
                dp[i] = dp[i] or dp[i - length]

    return dp[n]

优化：使用字典树或哈希集合加速单词匹配。

10.4.3 方案计数的细节

计数问题要特别注意：

初始值：dp[0] = 1（空集是一种方案）
状态转移：累加而非取最大值
顺序问题：组合还是排列？

# 通用模板
def countWays(items, target, is_combination=True):
    dp = [0] * (target + 1)
    dp[0] = 1

    if is_combination:
        # 组合：物品在外
        for item in items:
            for j in range(item, target + 1):
                dp[j] += dp[j - item]
    else:
        # 排列：容量在外
        for j in range(1, target + 1):
            for item in items:
                if j >= item:
                    dp[j] += dp[j - item]

    return dp[target]

10.4.4 状态压缩与滚动数组

当状态转移只依赖上一行时，可以用滚动数组优化空间：

# 二维DP的滚动数组优化
def knapsack2D(weights, values, capacity):
    n = len(weights)
    # 只保留两行
    dp = [[0] * (capacity + 1) for _ in range(2)]

    for i in range(n):
        curr = i % 2
        prev = 1 - curr
        for j in range(capacity + 1):
            dp[curr][j] = dp[prev][j]
            if j >= weights[i]:
                dp[curr][j] = max(dp[curr][j], 
                                   dp[prev][j - weights[i]] + values[i])

    return dp[(n - 1) % 2][capacity]

本章小结

背包问题家族展示了动态规划的精髓：通过系统的状态定义和转移，将复杂的组合优化问题转化为简单的递推关系。

核心要点：

问题识别：资源分配、选择决策 → 背包模型
状态定义：$dp[i][j]$ 的含义要精确
转移方程： - 01背包：$dp[i-1][j-w] + v$（上一行） - 完全背包：$dp[i][j-w] + v$（当前行）
空间优化： - 01背包：倒序遍历 - 完全背包：正序遍历
变体处理： - 恰好装满：初始化技巧 - 方案计数：累加而非最大值 - 组合vs排列：循环顺序

关键公式：

基础转移：$dp[j] = \max(dp[j], dp[j-w_i] + v_i)$
方案计数：$dp[j] += dp[j-w_i]$
最少物品：$dp[j] = \min(dp[j], dp[j-w_i] + 1)$

常见陷阱与错误

1. 初始化错误

# 错误：求最小值时初始化为0
dp = [0] * (n + 1)  # ❌
# 正确：
dp = [float('inf')] * (n + 1)
dp[0] = 0  # ✓

2. 循环顺序混淆

# 01背包错误使用正序
for j in range(weight, capacity + 1):  # ❌ 会重复使用
# 正确：
for j in range(capacity, weight - 1, -1):  # ✓

3. 边界条件遗漏

# 错误：没有检查容量
dp[j] = dp[j - weight] + value  # ❌ 可能越界
# 正确：
if j >= weight:
    dp[j] = max(dp[j], dp[j - weight] + value)  # ✓

4. 组合与排列混淆

# 求组合数却把容量循环放外层
for j in range(target + 1):
    for coin in coins:  # ❌ 这样算的是排列数

# 正确的组合数计算
for coin in coins:
    for j in range(coin, target + 1):  # ✓

5. 状态定义不清

# 模糊的定义
dp[i] = "某种最优值"  # ❌

# 清晰的定义
dp[i] = "前i个物品，容量为j时的最大价值"  # ✓

6. 没有考虑无解情况

# 错误：直接返回dp值
return dp[amount]  # ❌ 可能是初始的inf

# 正确：检查是否有解
return dp[amount] if dp[amount] != float('inf') else -1  # ✓

调试技巧

打印DP表：观察状态转移是否符合预期
小数据验证：用1-2个物品手算验证
边界测试：容量为0、物品为空等极端情况
分步调试：先写二维，验证后再优化为一维

记住：背包问题的本质是"选择"的艺术，掌握了基本模式后，关键在于识别和转化。