背包问题

数据结构与算法专题 · 组合优化的经典模型

专题：数据结构与算法系统学习

关键词：数据结构, 算法, 背包问题, 0-1背包, 完全背包, 多重背包, 分组背包, 二进制优化, DP

一、背包问题概述

背包问题（Knapsack Problem）是组合优化领域的经典模型，也是动态规划（Dynamic Programming, DP）最核心的入门题型之一。几乎所有DP的进阶技巧（状态压缩、滚动数组、单调队列优化、二进制拆分、依赖关系处理等）都能在背包问题的各个变种中找到对应训练。无论你是准备算法竞赛（NOI/ACM-ICPC）还是技术面试（大厂笔试/LeetCode周赛），掌握背包问题的完整体系都是通往DP高手的必经之路。

背包问题的基本场景可以这样描述：给定一个容量有限的背包，以及若干物品，每个物品有各自的体积（或称重量、成本）和价值，要求在不超过背包容量的前提下，选择某些物品装入背包，使得装入物品的总价值最大。根据物品的可选方式不同，背包问题衍生出多个经典变种。

背包问题的五大经典变种：0-1背包（每件最多选一次）、完全背包（每件无限选）、多重背包（每件有限次）、分组背包（每组最多选一件）、依赖背包（选子件必须先选主件）。

背包类型	物品选择方式	时间复杂度	空间优化
0-1背包	每件最多选1次	O(NV)	一维数组，逆序枚举
完全背包	每件可选无限次	O(NV)	一维数组，正序枚举
多重背包	每件最多选s[i]次	O(NV log s) / O(NV)	二进制优化 / 单调队列
分组背包	每组至多选1件	O(NV)	组内0-1决策
依赖背包	选子项需选主项	O(NV)	树形DP + 分组背包

核心思想：所有背包问题的本质都是"有限资源下的最优分配决策"。DP的状态定义通常为 dp[i][j] 表示"从前 i 个物品中选，总体积不超过 j 的最大价值"。状态转移的差异只在于"第 i 个物品能选几次"。

二、0-1背包问题

0-1背包是最基础也最重要的背包模型。题目描述：有 N 件物品和一个容量为 V 的背包，第 i 件物品的体积为 v[i]，价值为 w[i]。每件物品只能选一次（要么选，要么不选，故称 0-1）。求在不超过背包容量的前提下能装入的最大总价值。

2.1 二维DP（基础版本）

定义 dp[i][j] 表示考虑前 i 件物品、背包容量为 j 时能获得的最大价值。状态转移方程为：

def knapsack_01_2d(N, V, v, w):
    # dp[i][j] 表示前i件物品、容量j的最大价值
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(V + 1):
            # 不选第i件
            dp[i][j] = dp[i - 1][j]
            # 选第i件（前提是容量够）
            if j >= v[i - 1]:
                dp[i][j] = max(dp[i][j],
                    dp[i - 1][j - v[i - 1]] + w[i - 1])
    return dp[N][V]

时间复杂度 O(NV)，空间复杂度 O(NV)。当 N、V 较大时（如 V=10^5），二维数组会爆内存，需要优化为一维。

2.2 一维DP（滚动数组优化）

观察二维递推式可以发现，dp[i][j] 只依赖 dp[i-1][...] 行的数据，因此可以用滚动数组压缩到一维。关键点：内层循环必须逆序枚举容量 j，这样 dp[j - v[i]] 引用的仍然是上一轮（i-1）的结果，不会出现同一件物品被重复选取的问题。

def knapsack_01_1d(N, V, v, w):
    dp = [0] * (V + 1)
    for i in range(N):
        # 逆序遍历容量，防止重复选取
        for j in range(V, v[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - v[i]] + w[i])
    return dp[V]

2.3 为什么必须逆序

假设正序遍历容量 j，当处理物品 i 时，dp[j - v[i]] 可能已经在当前轮次被更新过（即已经选过一次物品 i），这时再叠加物品 i 就相当于选了多次，违反了0-1背包"每件最多选一次"的约束。逆序则可以保证每个物品只被考虑一次。

记忆口诀：0-1逆序，完全正序。记住这一点就掌握了两种最基本背包的核心区别。

2.4 恰好装满 VS 不超过容量

如果题目要求"恰好装满背包"，只需将 dp 数组初始化为 -inf（负无穷），只让 dp[0] = 0。这样只有精确由若干物品拼出的容量才会被更新为正数，否则保持负无穷。最后判断 dp[V] > 0 即可。

def knapsack_exact(N, V, v, w):
    INF = -10 ** 9
    dp = [INF] * (V + 1)
    dp[0] = 0
    for i in range(N):
        for j in range(V, v[i] - 1, -1):
            if dp[j - v[i]] != INF:
                dp[j] = max(dp[j], dp[j - v[i]] + w[i])
    return dp[V] if dp[V] != INF else -1

三、完全背包问题

完全背包与0-1背包的唯一区别在于：每件物品可以无限次选取（只要总体积不超过背包容量）。状态定义仍为 dp[i][j]，但转移方程变为取最大值：不选、选1次、选2次……直到放不下。

def knapsack_complete_2d(N, V, v, w):
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(V + 1):
            # k为选取件数
            k = 0
            while k * v[i - 1] <= j:
                dp[i][j] = max(dp[i][j],
                    dp[i - 1][j - k * v[i - 1]] + k * w[i - 1])
                k += 1
    return dp[N][V]

这种三重循环写法的时间复杂度为 O(NV * (V/v_avg))，在数据量较大时不可接受。通过对转移方程做数学推导，可以将内层的 k 循环优化掉，得到一个非常简洁的 O(NV) 解法。

3.1 一维优化（正序枚举）

完全背包的一维优化与0-1背包只有一处不同：内层循环改为正序枚举容量。因为完全背包允许重复选取，正序遍历时 dp[j - v[i]] 可能已经在当前轮次被更新过，恰好体现了"可以多次选择当前物品"的语义。

def knapsack_complete_1d(N, V, v, w):
    dp = [0] * (V + 1)
    for i in range(N):
        # 正序遍历容量，允许重复选取
        for j in range(v[i], V + 1):
            dp[j] = max(dp[j], dp[j - v[i]] + w[i])
    return dp[V]

对比口诀：0-1背包逆序（防重复），完全背包正序（允重复）。一维 DP 下两种背包的代码差异仅仅在一个循环方向上。

3.2 经典应用：零钱兑换

LeetCode 322. 零钱兑换是典型的完全背包问题（硬币无限枚），求组成目标金额所需的最少硬币数。

def coinChange(coins, amount):
    INF = 10 ** 9
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for c in coins:
        for j in range(c, amount + 1):
            dp[j] = min(dp[j], dp[j - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

四、多重背包问题

多重背包是0-1背包和完全背包的中间态：第 i 件物品最多可以选 s[i] 次（既不是一次，也不是无限次）。暴力做法是对每件物品枚举选取 0 ~ s[i] 件，时间复杂度 O(NV * max_s)，需要优化。

4.1 二进制优化

核心思想：将数量为 s 的同种物品，按二进制拆分成若干组，每组视为一件独立的新物品（0-1背包处理）。任何 0~s 之间的选取数量都可以由这些二进制组组合而成（类似二进制表示任意整数）。例如 s=13 时拆分为 1、2、4、6（13-1-2-4=6），这四个组可以组成 0~13 的所有整数。

def knapsack_multiple_binary(N, V, v, w, s):
    # 二进制拆分
    goods = []
    for i in range(N):
        k = 1
        while k <= s[i]:
            goods.append((k * v[i], k * w[i]))
            s[i] -= k
            k <<= 1  # k *= 2
        if s[i] > 0:
            goods.append((s[i] * v[i], s[i] * w[i]))
    # 转化为0-1背包
    dp = [0] * (V + 1)
    for vv, ww in goods:
        for j in range(V, vv - 1, -1):
            dp[j] = max(dp[j], dp[j - vv] + ww)
    return dp[V]

二进制优化将物品总数从 N 增至 N * log(max_s)，时间复杂度 O(V * sum(log s[i]))，足以应对大部分竞赛和面试场景。

4.2 单调队列优化（进阶）

如果数据范围进一步加大（如 V 和 s 都达到 10^4 量级），二进制优化的 O(V log s) 仍然可能超时。此时可以使用单调队列（滑动窗口）将多重背包优化到严格的 O(NV)。

def knapsack_multiple_mono(N, V, v, w, s):
    dp = [0] * (V + 1)
    for i in range(N):
        vi, wi, si = v[i], w[i], s[i]
        # 按模vi的余数分组处理
        for r in range(vi):
            # 单调队列存放下标j，要求dp值递减
            q = collections.deque()
            for j in range(r, V + 1, vi):
                # 移除超出滑动窗口范围的队头
                if q and q[0] < j - si * vi:
                    q.popleft()
                # 队尾维护单调递减
                val = dp[j] - j // vi * wi
                while q and dp[q[-1]] - q[-1] // vi * wi <= val:
                    q.pop()
                q.append(j)
                # 队头为最优值
                dp[j] = dp[q[0]] + (j - q[0]) // vi * wi
    return dp[V]

注意：单调队列优化的理解门槛较高，面试中如果时间有限，掌握二进制优化足以解决绝大多数多重背包问题。单调队列更适合竞赛场景。

五、分组背包问题

分组背包将物品分成若干组，每组内部有多个物品，但每组最多只能选一件（也可以不选）。状态定义仍然是 dp[j] 表示容量 j 的最大价值，但在处理每个组时，组内的物品之间是互斥的。

5.1 核心思路

外层循环遍历组，内层先枚举容量（逆序），再枚举组内物品。逆序容量 + 组内物品枚举的顺序确保了"每组最多选一件"的约束。

def knapsack_group(V, groups):
    # groups: [[(v1,w1), (v2,w2), ...], ...]
    dp = [0] * (V + 1)
    for group in groups:
        # 先逆序枚举容量
        for j in range(V, -1, -1):
            # 再枚举组内物品
            for vv, ww in group:
                if j >= vv:
                    dp[j] = max(dp[j], dp[j - vv] + ww)
    return dp[V]

三层循环顺序的记忆：分组背包的循环顺序是"组 → 容量 → 组内物品"，不能调换。容量逆序确保了每个组内物品的决策不会互相影响。

5.2 应用场景

分组背包常用于选择互斥选项的场景，例如：选择课程时每个类别最多选一门、选择装备时每个部位只能佩戴一件、选择投资组合中每个行业最多投一个项目等。

六、依赖背包问题

依赖背包（又称"有依赖的背包问题"）引入了物品之间的依赖关系：如果要选择某个子物品，必须首先选择其父物品（主件）。例如"买电脑必须先买主机"、"买手机必须先买套餐"等。这种依赖关系通常构成一棵树形结构。

6.1 树形DP + 分组背包

典型解法是对树进行后序遍历（DFS），在每棵子树上做一遍分组背包。每个子树返回一个 DP 数组，父节点再将这些子树的 DP 结果进行合并。

def knapsack_dependency(V, v, w, children, root):
    # children: 邻接表, root: 根节点
    def dfs(u):
        # 选主件u，至少占用v[u]容量
        dp_u = [-10**9] * (V + 1)
        for j in range(v[u], V + 1):
            dp_u[j] = w[u]
        # 处理每个子树（分组背包）
        for child in children[u]:
            dp_child = dfs(child)
            # 合并子树的DP结果
            for j in range(V, v[u] - 1, -1):
                for k in range(V - j + 1):
                    if dp_child[k] >= 0:
                        dp_u[j + k] = max(dp_u[j + k],
                                             dp_u[j] + dp_child[k])
        return dp_u

    dp_root = dfs(root)
    return max(dp_root)

关键理解：依赖背包的核心思想是将子树视为一个"物品组"，每个子树可以贡献不同的容量-价值组合，父节点从所有子树的组合中选出最优的分配方案。这是树形DP与分组背包的绝妙结合。

七、背包问题的经典应用

背包问题的思想在 LeetCode 和算法面试中有大量直接应用。以下是几个最经典的题目及其与背包模型的对应关系。

7.1 子集和（Subset Sum）

给定一个正整数数组 nums 和一个目标值 target，判断是否能选出若干数使其和等于 target。本质是0-1背包的布尔版本：每个数选或不选，容量 = target，价值 = 数值本身，判断是否能恰好装满。

def canPartition(nums, target):
    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]

7.2 分割等和子集（LeetCode 416）

给定一个只包含正整数的非空数组，判断能否将其分割成两个子集，使两个子集的元素和相等。等价于：能否选出若干数，使它们的和为总和的一半（即 target = sum / 2）。

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        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]

7.3 目标和（LeetCode 494）

给定一个非负整数数组 nums 和一个目标数 target，在每个数前添加 "+" 或 "-"，求有多少种表达式结果等于 target。等价于：将数组分成正子集 P 和负子集 N，求 sum(P) - sum(N) = target，转化为 sum(P) = (target + total) / 2，求组成该和的方案数。

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

7.4 零钱兑换 II（LeetCode 518）

给定不同面额的硬币和一个总金额，求凑成总金额的组合数（每种硬币无限枚）。这是完全背包求方案数的经典题目。注意外层循环硬币、内层正序容量，得到的是组合数（不考虑顺序）。

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:
        for j in range(c, amount + 1):
            dp[j] += dp[j - c]
    return dp[amount]

组合 VS 排列：如果要求排列数（即顺序不同的方案视为不同），则外层循环容量、内层循环物品。LeetCode 377. 组合总和IV 就是排列数的版本，代码为 for j in range(1, target+1): for num in nums: dp[j] += dp[j-num]。两种循环顺序的区别必须牢记。

7.5 单词拆分（LeetCode 139）

给定一个字符串和一个单词列表，判断是否可以用列表中的单词拼接成该字符串。这可以看作完全背包的变体：目标字符串长度是容量，单词是物品（体积为单词长度，无限使用），但是转移条件不是简单的数值相加，而是要求字符串匹配。

def wordBreak(s, wordDict):
    n = len(s)
    wordSet = set(wordDict)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for word in wordSet:
            L = len(word)
            if i >= L and dp[i - L] and s[i - L:i] == word:
                dp[i] = True
                break
    return dp[n]

八、背包问题方案数与方案输出

除了求最大价值外，背包问题还经常考察两点：方案数（有多少种方式恰好装满背包）和具体方案（打印出选择了哪些物品）。

8.1 求方案数（恰好装满）

将 DP 数组的含义改为"达到容量 j 的方案数"。初始 dp[0] = 1（空集是一种方案），转移方程为 dp[j] += dp[j - v[i]]。

# 0-1背包方案数（恰好装满）
def count_ways_01(N, V, v):
    dp = [0] * (V + 1)
    dp[0] = 1
    for i in range(N):
        for j in range(V, v[i] - 1, -1):
            dp[j] += dp[j - v[i]]
    return dp[V]

# 完全背包方案数（组合数）
def count_ways_complete(V, v):
    dp = [0] * (V + 1)
    dp[0] = 1
    for vi in v:
        for j in range(vi, V + 1):
            dp[j] += dp[j - vi]
    return dp[V]

8.2 输出具体方案（最优解回溯）

在 DP 过程中额外记录一个 choice 数组保存每个状态下的"最后决策"，DP结束后从终点倒推回起点，即可还原出具体的物品选择序列。

def knapsack_with_path(N, V, v, w):
    dp = [0] * (V + 1)
    # choice[i][j] 表示容量j时是否选了物品i
    choice = [[False] * (V + 1) for _ in range(N)]
    for i in range(N):
        for j in range(V, v[i] - 1, -1):
            if dp[j - v[i]] + w[i] > dp[j]:
                dp[j] = dp[j - v[i]] + w[i]
                choice[i][j] = True
    # 回溯：从终点倒推
    selected = []
    j = V
    for i in range(N - 1, -1, -1):
        if choice[i][j]:
            selected.append(i)
            j -= v[i]
    return dp[V], selected[::-1]  # 最大价值和选中的物品下标列表

方案回溯的要点：二维 choice 数组会消耗额外空间（N*V），对于大数据可以用一维 pre 数组记录前驱状态的下标，节约内存。回溯时需要注意遍历顺序——从最后一个物品往第一个物品倒推。

九、核心要点总结

0-1背包：一维DP逆序枚举容量，每件物品最多选一次，是一切背包问题的基础。
完全背包：一维DP正序枚举容量，每件物品无限选，与0-1背包仅循环方向不同。
多重背包：二进制优化将有限件物品拆成log个0-1物品，单调队列优化可达严格的O(NV)。
分组背包：每组最多选一件，三层循环顺序为"组→容量→组内物品"，容量逆序。
依赖背包：树形DP + 分组背包，后序遍历子树，父节点合并子树的DP结果。
方案数：dp[0]=1，转移用加法，0-1逆序/完全正序，注意组合与排列的区别。
方案输出：DP过程记录choice数组，结束后从终点回溯到起点，倒推出具体方案。
循环顺序至关重要：物品-容量-决策的三层循环顺序决定了背包的类型，不能随意调换。

十、进一步思考

背包问题虽然经典，但它的思想远远不止于这几种固定模式。在实际问题中，背包的"体积"和"价值"可以有非常灵活的映射：

多维背包：物品有多个维度的限制（如体积+重量），DP 数组扩展为二维或多维。
混合背包：题目中同时包含0-1、完全、多重三种类型的物品，分别用对应的转移方式处理即可。
背包+其他约束：如"恰好选 K 件"（增加一维记录件数）、"价值与体积成非线性关系"等。
泛化物品：物品的价值不再是固定值，而是与分配到的容量相关（如价值 = f(v_allocated)）。

掌握背包问题的关键是理解DP 状态的定义、转移方程的推导、循环顺序的含义、空间优化的原理。建议初学者按以下路径循序渐进：0-1背包（二维）→ 0-1背包（一维）→ 完全背包（一维）→ 多重背包（二进制优化）→ 分组背包 → 依赖背包。每学一个变种都在之前的基础上思考"和之前的有什么不同"、"为什么需要这种调整"，这样才能真正融会贯通。

"背包问题学好了，动态规划就学会了一半。" —— 算法竞赛圈广为流传的一句话，足以说明背包问题在DP学习中的基石地位。