假设你明天出发去旅行，面前摆着心爱的物品：相机、小说、零食、帐篷……但行李箱容量有限。怎么装，才能让这趟旅行的幸福感最高？把“行李箱容量”换成“预算”，把“幸福感”换成“收益”，这就是计算机科学中的经典问题——背包问题。 背包问题是动态规划中“分阶段做决策”的完美教材。它看似简单，却衍生出 01 背包、完全背包、多重背包、分组背包、混合背包等变体，像同一个旅行故事的不同购物场景：景区纪念品每件只能买一个，超市特产可以无限拿，商场折扣装每种最多拿几包，服装搭配每组只选一件。本文用旅行装行李的故事贯穿始终，逐步拆解这些变体的状态转移方程，并给出可运行的 Python 代码。

岗位关联

背包问题是动态规划求职面试的“入场券”，也是资源分配、预算优化等 AI 工程场景的底层算法。彻底吃透它，等于掌握了动态规划中最经典的决策框架。

目录
  1. 可视化演示
  2. 背包问题概述
  3. 01背包基础
  4. 01背包优化
  5. 完全背包
  6. 多重背包
  7. 分组背包
  8. 混合背包
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示01背包与完全背包的DP表填充过程、状态转移方程对比及资源分配应用场景。

本节配有交互动效（进入视口后自动加载，约 3KB）。

01背包状态转移 逆序遍历确保每件物品只选一次 dp[j]=max(dp[j],dp[j-w]+v) O(nW) 01背包空间优化至一维数组

背包问题概述

想象你的行李箱容量固定为 20 公斤，面前摆着相机（2kg，开心值 3）、帐篷（5kg，开心值 8）、小说（1kg，开心值 1）……你需要在不超过 20kg 的前提下，让总开心值最大。这就是背包问题最朴素的模样：有限容量下做最优取舍。

计算机科学家把“开心值”抽象为价值 v_i，“重量”抽象为代价 w_i，容量记为 C。目标是从 n 件物品中挑出一个子集，使总重量不超过 C 且总价值最大。根据物品可否重复选取，衍生出五大变体：01 背包（每件最多一次）、完全背包（无限次）、多重背包（有限次）、分组背包（每组选一个）、混合背包（前四者混合）。它们共享同一套“分阶段递推”的解题骨架，区别只在遍历方向与拆分技巧。

回顾旅行场景：景区纪念品店里的每件纪念品，你只能决定“买”还是“不买”——这就是 01 背包。去超市则可以无限拿同种特产，去商场折扣区每种限量拿几包……不同的购物规则，对应不同的背包变体，但最终都归结为同一个问题：在容量约束下如何让收获最大。

max⁡∑i=1nvixis.t.∑i=1nwixi≤C,  xi∈{0,1}\displaystyle \max \sum_{i=1}^{n} v_i x_i \quad \text{s.t.} \quad \sum_{i=1}^{n} w_i x_i \le C,\; x_i \in \{0,1\}
这个公式是 01 背包的数学原型：x_i 只取 0 或 1，表示“不带”或“带”。
  1. 价值总和最大化枚举所有可行的装入组合，目标是让 Σv_i x_i 达到最大，这是优化目标。
    max⁡∑i=1nvixi\displaystyle \max \sum_{i=1}^{n} v_i x_i
  2. 容量约束所有被选物品的重量之和不能超过背包容量 C，这是硬性限制条件。
    ∑i=1nwixi≤C\displaystyle \sum_{i=1}^{n} w_i x_i \le C
  3. 0-1 决策变量x_i 只能取 0 或 1，对应“这件物品不带/带”，不允许带半件或带多件。
    xi∈{0,1}\displaystyle x_i \in \{0,1\}

01背包基础

来到景区纪念品店，每件纪念品只有一个，你只能做“买/不买”的二元决策。这就是 01 背包：n 件物品，每件最多选一次。如何系统化决策？动态规划的思路是“分阶段递推”——先看前 i 件物品在容量 j 下能拿到多少价值，再一步步推到前 n 件、容量 C。

定义状态 dp[i][j]：前 i 件物品中选出若干件，放入容量为 j 的背包时，能获得的最大价值。对于第 i 件物品，只有两种选择：不放，则继承 dp[i-1][j]；放，则腾出 w_i 的空间，得到 dp[i-1][j-w_i] + v_i。两者取大即可。初始时 dp[0][j] = 0，表示没有物品可选时价值为 0。

两层循环即可求解：外层遍历物品 i，内层遍历容量 j 从 0 到 C。当 j < w_i 时装不下，只能执行“不放”分支。整个过程就像在旅行前逐个掂量纪念品：放得下就比一比“带 vs 不带”哪个更值，放不下就直接放弃。最终 dp[n][C] 就是最优答案。

dp[i][j]=max⁡(dp[i−1][j],  dp[i−1][j−wi]+vi)\displaystyle dp[i][j] = \max(dp[i-1][j],\; dp[i-1][j-w_i] + v_i)
这是 01 背包的心脏：每一格都只在“不放”与“放”两个选项中挑更大的那个。
  1. dp[i][j] 的定义记录“前 i 件物品、容量为 j”时能取得的最大价值，是递推的存储单位。
    dp[i][j]\displaystyle dp[i][j]
  2. 不放第 i 件既然不放，价值与前 i-1 件在该容量下的结果完全相同，直接继承。
    dp[i−1][j]\displaystyle dp[i-1][j]
  3. 放入第 i 件必须先预留 w_i 的容量给第 i 件，剩余容量 j-w_i 交给前 i-1 件去最优决策，最后加上价值 v_i。
    dp[i−1][j−wi]+vi\displaystyle dp[i-1][j-w_i] + v_i

01背包优化

纪念品太多，笔记本记不下整张二维表了。能不能只带一张纸，边看边更新？01 背包的“滚动数组”优化正是这个思路：dp[i][j] 只依赖 dp[i-1][...]，即“上一行”的数据，因此可以用一维数组 dp[j] 原地滚动覆盖。

但滚动时有个陷阱：如果容量从小到大（正序）更新，dp[j-w_i] 可能已经被本轮“放过第 i 件”的结果覆盖，导致同一件物品被重复选中——这在 01 背包中是不允许的。因此内层容量必须从大到小（逆序）更新，保证 dp[j-w_i] 读到的仍是上一轮“没放第 i 件”的旧值。

这张“纸”帮你在纪念品店快速比价：从大容量往小容量倒着看，每件物品只被考虑一次。空间省了，逻辑不变——这就是动态规划中典型的“滚动数组”技巧。

dp[j]=max⁡(dp[j],  dp[j−wi]+vi)(j:C→wi)\displaystyle dp[j] = \max(dp[j],\; dp[j-w_i] + v_i) \quad (j: C \to w_i)
逆序是 01 背包一维优化的灵魂：它悄悄保证了“每件物品最多用一次”。
  1. 一维数组 dp[j]把二维表的“当前行”压缩成一个数组，容量 j 对应下标 j，空间从 O(nC) 降到 O(C)。
    dp[j]\displaystyle dp[j]
  2. 更新方程在“旧值不放”与“放入后价值”之间取最大值，覆盖写入当前下标。
    max⁡(dp[j],  dp[j−wi]+vi)\displaystyle \max(dp[j],\; dp[j-w_i] + v_i)
  3. 逆序上限与下限j 从 C 递减到 w_i，小于 w_i 的容量装不下当前物品，无需更新。
    j:C→wi\displaystyle j: C \to w_i

完全背包

逛完景区来到超市特产区，货架上的果干、巧克力可以任意拿取，每种不设上限。这就是完全背包：每种物品可取无限次。状态定义与 01 背包完全一致，但转移时“放第 i 件”后，剩余容量依然可以继续放第 i 件，因此内层容量要正序遍历——这样才能让 dp[j-w_i] 读到本轮已经更新过、可能再次选了第 i 件的结果。

对比两张代码，唯一的差别就是内层循环方向：01 背包逆序防重选，完全背包正序允许重复。超市里你可以抓了又抓、装到放不下为止，而景区纪念品买完就没了——一个正序、一个倒序，完美对应两种购物规则。

dp[j]=max⁡(dp[j],  dp[j−wi]+vi)(j:wi→C)\displaystyle dp[j] = \max(dp[j],\; dp[j-w_i] + v_i) \quad (j: w_i \to C)
正序与逆序，一字之差，代表了“无限次”与“一次”的本质区别。
  1. 正序下界j 从 w_i 开始，容量达到物品重量才有装入的可能。
    j:wi→C\displaystyle j: w_i \to C
  2. 正序更新语义容量从小到大推进，dp[j-w_i] 可能已被本轮更新，等价于允许“反复加同一件物品”。
    dp[j−wi]\displaystyle dp[j-w_i]
  3. 状态沿用dp[j] 的旧值代表“完全不放第 i 件”的可选方案，与放入方案取 max。
    max⁡(dp[j],  dp[j−wi]+vi)\displaystyle \max(dp[j],\; dp[j-w_i] + v_i)

多重背包

商场折扣区规定：某款零食最多买 3 包，另一款最多买 5 包。这就是多重背包：每种物品有数量上限 c_i。最朴素的做法是拆成 c_i 件独立的 01 物品，但若 c_i 很大，效率堪忧。二进制拆分登场：把 c_i 拆成 1、2、4、… 以及剩余部分，这些“打包组”能组合出 0 到 c_i 的任意数量，且打包组数量从 c_i 降到 O(log c_i)。

以 13 包零食为例：拆成 1、2、4、6 四组，任意 0~13 的购买数量都可以由这四组的某个组合表示。之后每组当作一件 01 物品求解即可。更进一步的单调队列优化，则把多重背包的时间复杂度压到 O(nC)，适合超大数量场景——但初学掌握二进制拆分，已足以应对绝大多数面试与工程问题。

ci=1+2+4+⋯+2k+r\displaystyle c_i = 1 + 2 + 4 + \cdots + 2^{k} + r
二进制拆分的巧妙之处：用 log n 个打包组，就能表示任意 0 到 n 的选取数量。
  1. 连续幂次项1、2、4……这些 2 的幂次能组合出 0 到 2^{k+1}-1 的任意整数。
    1+2+4+⋯+2k\displaystyle 1 + 2 + 4 + \cdots + 2^{k}
  2. 剩余项 r当剩余数量不足以凑出下一个完整幂次时，直接作为独立打包组，保证总覆盖到 c_i。
    +  r\displaystyle +\; r
  3. 总和约束所有拆分项之和恰好等于原数量 c_i，不多不少。
    ci=1+2+4+⋯+2k+r\displaystyle c_i = 1 + 2 + 4 + \cdots + 2^{k} + r

分组背包

出门旅行要搭配衣服：上衣、裤子、鞋子各选一件。每组内部互斥，最多挑一件。这就是分组背包：物品被分成若干组，每组最多选一个。状态转移时，外层先枚举组，内层容量逆序，最内层枚举组内物品——为什么容量要放在组内物品之前？因为这样才能保证“整组最多选一件”。

搭配衣服时，你不可能同时穿两条裤子；分组背包用“容量逆序 + 组内枚举”的次序，天然保证了互斥选择。这也解释了为什么内层不能先枚举物品——否则同一组的多件物品会被当作 01 物品逐件塞进背包，破坏“最多选一件”的规则。

dp[j]=max⁡(dp[j],  max⁡k∈Gi(dp[j−wk]+vk))\displaystyle dp[j] = \max(dp[j],\; \max_{k \in G_i} (dp[j-w_k] + v_k))
分组背包的三层循环次序是核心考点：组 → 容量 → 组内物品，缺一不可。
  1. 组内取最大在组 G_i 的所有物品中，挑出“放进容量 j 后价值最大”的那一件。
    max⁡k∈Gi(dp[j−wk]+vk)\displaystyle \max_{k \in G_i} (dp[j-w_k] + v_k)
  2. 不选整组dp[j] 的旧值表示整组什么都不选，直接继承上一组的结果。
    dp[j]\displaystyle dp[j]
  3. 两者取大在“这组不选任何物品”与“这组选最优的一件”之间做全局决策。
    max⁡(dp[j],  max⁡k∈Gi(dp[j−wk]+vk))\displaystyle \max(dp[j],\; \max_{k \in G_i} (dp[j-w_k] + v_k))

混合背包

一次长途旅行，你会同时遇到景区、超市、折扣区和服装店。混合背包就是把 01、完全、多重、分组混在一个输入里。处理策略并不复杂：按物品类型分流——01 物品容量逆序，完全物品容量正序，多重物品先二进制拆分转成 01 物品，分组物品套用分组三层循环。

整理行囊时，你不需要发明新方法，只需把每件物品“对号入座”：纪念品逆序、特产正序、折扣装拆分、衣物分组。背包问题的所有变体，本质上是同一棵决策树的不同分枝——理解了状态转移的方向逻辑，再复杂的混合输入也能迎刃而解。

{j:C→wi01 / 拆分后的多重j:wi→C完全\displaystyle \begin{cases} j: C \to w_i & \text{01 / 拆分后的多重} \\ j: w_i \to C & \text{完全} \end{cases}
混合背包不是新算法，而是“遍历方向选择器”：类型决定方向，方向决定正确性。
  1. 逆序分支01 物品和经过二进制拆分后的多重物品，统一按逆序更新，保证每件最多选一次。
    j:C→wi\displaystyle j: C \to w_i
  2. 正序分支完全背包物品按正序更新，允许同种物品被反复选取直到装满。
    j:wi→C\displaystyle j: w_i \to C
  3. 矩阵化表达整个混合背包就是按类型选择上式中的某一分支，再套用统一的 max 转移。
    {j:C→wi01 / 拆分后的多重j:wi→C完全\displaystyle \begin{cases} j: C \to w_i & \text{01 / 拆分后的多重} \\ j: w_i \to C & \text{完全} \end{cases}

AI 应用场景

云资源预算分配（01背包）

阶段：资源调度与成本优化

解决的问题：AI 训练任务常有多组候选配置（如不同 GPU 实例），每组有算力单价和预估收益，而总预算有限。传统做法靠人工拍板或贪心选最贵，往往浪费预算。用 01 背包，每个配置是一次性选项，预算即容量，收益即价值，dp[j] = max(dp[j], dp[j-w]+v) 直接给出最优采购组合。

具体案例：某团队要在 10 万元预算内从 6 种 GPU 实例中选型，每种最多租一台，通过 01 背包求得收益最大组合，比人工决策收益提升 18%。

营销预算多渠道分配（多重背包）

阶段：广告投放策略优化

解决的问题：营销活动在多个渠道投放，每个渠道有投放次数上限（如同广告位库存），不同投放次数对应不同转化收益。多重背包的二进制拆分恰好匹配“每渠道最多投 c_i 次”的约束，拆分后按 01 背包求解，预算分配从经验驱动变为算法驱动。

具体案例：一家电商公司在 50 万预算内，对 4 个广告渠道分别有 3/5/2/4 次投放上限，用多重背包求得最优投放次数组合，ROI 提升 12%。

货运车辆装载规划（分组+混合背包）

阶段：物流路径规划中的装载子问题

解决的问题：货车装载时，货物按品类分组（如生鲜、电子、服装），每组因安全规则最多选一定数量，同时部分货物可拆零（完全）、部分限量（多重）。混合背包策略按类型分流处理，一键生成合规且利润最高的装载方案，替代人工估算。

具体案例：物流公司对一辆 20 吨货车规划装载，货物分 3 组共 9 类，用混合背包求解后装载率从 82% 提升到 94%。

Python 演示

python55 行
def knapsack_01(weights, values, capacity):    """01背包：每件物品最多选一次，容量倒序遍历"""    dp = [0] * (capacity + 1)    for i in range(len(weights)):        for j in range(capacity, weights[i] - 1, -1):            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])    return dp[capacity]  def knapsack_complete(weights, values, capacity):    """完全背包：每种物品可取无限次，容量正序遍历"""    dp = [0] * (capacity + 1)    for i in range(len(weights)):        for j in range(weights[i], capacity + 1):            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])    return dp[capacity]  def knapsack_multiple(weights, values, counts, capacity):    """多重背包：二进制拆分后转为01背包"""    w, v = [], []    for i in range(len(weights)):        rest = counts[i]        k = 1        while k <= rest:            w.append(weights[i] * k)            v.append(values[i] * k)            rest -= k            k <<= 1        if rest > 0:            w.append(weights[i] * rest)            v.append(values[i] * rest)    return knapsack_01(w, v, capacity)  def knapsack_group(groups, capacity):    """分组背包：每组最多选一个，组->容量->物品三层循环"""    dp = [0] * (capacity + 1)    for group in groups:        for j in range(capacity, -1, -1):            for w, val in group:                if j >= w:                    dp[j] = max(dp[j], dp[j - w] + val)    return dp[capacity]  if __name__ == '__main__':    wt = [2, 3, 4, 5]    vl = [3, 4, 5, 8]    C = 10    print('01背包最优价值:', knapsack_01(wt, vl, C))    print('完全背包最优价值:', knapsack_complete(wt, vl, C))    print('多重背包最优价值:', knapsack_multiple([2, 3], [3, 4], [3, 2], C))    groups = [[(2, 3), (3, 4)], [(4, 5), (5, 8)], [(1, 2)]]    print('分组背包最优价值:', knapsack_group(groups, C))
目的：一套代码覆盖背包四大变体，直接运行即可对比同一批物品在不同规则下的最优价值。
  1. dp = [0] * (capacity + 1)一维滚动数组，容量从 0 到 C，下标即容量。
  2. for j in range(capacity, weights[i] - 1, -1)01 背包容量倒序，防止同件物品重复选择。
  3. for j in range(weights[i], capacity + 1)完全背包容量正序，允许无限次取同一物品。
  4. while k <= rest二进制拆分的核心循环：不断取出 1、2、4… 的幂次打包组。
  5. rest -= k; k <<= 1扣掉已取数量，k 左移一位翻倍，继续拆下一组。
  6. if rest > 0剩余不足一个幂次的零头，单独作为一组。
  7. return knapsack_01(w, v, capacity)拆分后的多重背包直接复用 01 背包函数。
  8. for group in groups: for j ... for w, val in group分组背包严格要求“组 → 容量 → 组内物品”三层顺序。

常见误区

误区完全背包每种物品可以取无限次，所以要在 01 背包基础上加一层循环枚举取多少件，`dp[j] = max(dp[j-k*w]+k*v)`。

正解不需要显式加层！内层容量正序遍历时，dp[j-w] 已经是本轮更新过的结果，它天然允许同一物品被反复纳入，等价于枚举所有 k。正序就是“无限次”的隐式实现，加第三层反而把 O(nC) 变成 O(nC²)，性能大幅劣化。

为何常见：刚学动态规划时习惯把“数量”显式建模，忽略了遍历顺序本身就编码了物品的可重复性，因此容易多写一层循环。

误区既然完全背包正序，那么 01 背包一维优化应该也是正序，或者方向无关紧要。

正解方向至关重要。01 背包内层必须逆序，才能让 dp[j-w] 引用“上一轮（尚未放当前物品）”的状态；若正序，同一件物品会被反复计算，结果变成“无限次取用”，得到完全背包的解。可以这样记忆：倒序防重，正序任意。

为何常见：两个变体代码几乎一样，只有一个 range 的方向差异，肉眼不易察觉，缺乏对比实验时就会混淆。

误区把数量 c 拆成 1、2、4、8… 直到超过 c 为止，剩下的不管了，直接按 01 背包求解。

正解拆分必须覆盖 0 到 c 的每一种取值。比如 c=13，拆 1、2、4 后还剩 6，这个“零头”必须单独成组，否则最多只能表示 0~7，无法凑出 8~13 的选取数量。正确拆分是 1、2、4、6，四组可覆盖 0~13 全部整数。

为何常见：初学者只记得“拆成 2 的幂”，却忽略了剩余部分的必要性，把幂次拆完就当作结束。

误区分组背包和普通背包一样，外层枚举物品再枚举容量就行，组内物品逐个处理。

正解分组背包必须“组 → 容量 → 组内物品”。若把物品放在最外层，同组的多件物品会被分散到不同轮次，相当于允许同组选多件，破坏“每组最多选一个”的约束。容量放在组内物品之前，是保证整组互斥的关键。

为何常见：01 背包的习惯“物品外层、容量内层”太牢固，遇到分组变体时容易惯性照搬，没有回到状态定义去推理依赖关系。

误区背包问题 dp 数组初始化全部填 0，任何情况下都是对的。

正解如果题目要求“恰好装满背包”，初始化为 dp[0]=0, dp[1..C]=-∞（价值可能为负时用极小值），因为只有容量 0 是合法起点，其余容量在未放入任何物品时不可达。若题目只要求“不超过容量”，全 0 才正确。初始化方式取决于状态语义，不能一概而论。

为何常见：模板题大多用“不超过容量”的宽松版本，导致学习者没见过“恰好装满”的严格版本，面试换问法时就踩坑。

面试题

Q1. 01背包一维优化时，内层容量为什么必须倒序遍历？

单选题 · easy

  • A.防止同一件物品被重复选取← 正确答案
  • B.让物品价值排序更高效
  • C.减少外层循环次数
  • D.保证背包恰好装满

答案：A。倒序遍历时，dp[j-w] 读到的是上一轮尚未放入当前物品的旧值，从而保证每件物品最多选一次。正序会让 dp[j-w] 携带本轮已放入的信息，导致同件物品被反复选取，变成完全背包的行为。就像景区纪念品买完就没了，不能回头再买。

Q2. 完全背包与01背包的代码唯一区别是什么？

单选题 · easy

  • A.内层容量的遍历方向不同← 正确答案
  • B.外层物品的遍历方向不同
  • C.初始化数组长度不同
  • D.完全背包不需要动态规划

答案：A。01 背包内层容量倒序，完全背包内层容量正序，其余代码完全相同。正序遍历允许 dp[j-w] 引用本轮已更新的值，天然支持同种物品无限次取用，对应超市特产随便拿的场景。

Q3. 01背包状态 dp[i][j] 的含义是什么？

单选题 · easy

  • A.前 i 件物品放入容量 j 背包的最大价值← 正确答案
  • B.所有物品放入容量 j 背包的最小重量
  • C.第 i 件物品单独放入时的价值
  • D.容量 j 背包最多能装的物品件数

答案：A。dp[i][j] 是“前 i 件物品中选若干件、总重不超过 j 的最大价值”，它是动态规划的状态定义。理解了它，转移方程 max(不放, 放) 就是顺理成章的两种决策。

Q4. 多重背包中，物品数量 13 经二进制拆分后的结果是？

单选题 · mid

  • A.1、2、4、6← 正确答案
  • B.1、2、3、7
  • C.2、4、8、1
  • D.4、4、4、1

答案：A。按 1、2、4、8… 拆，1+2+4=7，剩余 13-7=6，所以拆成 1、2、4、6。这四组能组合出 0~13 的任意整数。B 选项 3 不是幂次且组合不完整，C 选项 2、4、8 已经是 14 超过原数，D 选项无法覆盖 0~13 的连续区间。

Q5. 分组背包要求“每组最多选一个”，三层循环的正确次序是？

单选题 · mid

  • A.组 → 容量（倒序） → 组内物品← 正确答案
  • B.组内物品 → 容量 → 组
  • C.容量 → 组 → 组内物品
  • D.三种次序结果相同

答案：A。容量放在“组内物品”之前，确保同组物品竞争同一个容量槽位，最多只有一件被选中；若把组内物品放外层（B 选项），同组物品会被先后塞入背包，破坏互斥约束。就像穿衣搭配，组内各件只能竞争同一个“名额”。

Q6. 若题目要求“恰好装满背包”，dp 数组的初始化方式应为？

单选题 · mid

  • A.dp[0]=0，其余 dp[1..C]=-∞← 正确答案
  • B.全部初始化为 0
  • C.全部初始化为 -∞
  • D.dp[0]=-∞，其余为 0

答案：A。“恰好装满”要求只有容量 0 是合法起点（空包恰好装满 0），其他容量在没有放入任何物品时不可达，必须用 -∞ 表示“不可能”。若全部填 0，转移时会从非法状态推出错误解。相当于旅行中只有空箱是初始可达状态，没放东西却“恰好装满”其他容量是不合逻辑的。

Q7. 关于混合背包的统一处理策略，下列说法正确的是？

多选题 · mid

  • A.01 物品容量倒序更新← 正确答案
  • B.完全物品容量正序更新← 正确答案
  • C.多重物品先二进制拆分再按 01 处理← 正确答案
  • D.所有物品统一按完全背包处理

答案：ABC。混合背包的正确做法是“分类各就各位”：01 逆序，完全正序，多重先拆成 01。D 选项把所有物品当完全背包处理，会破坏 01 与多重的数量限制。就像整理行囊时，景区纪念品、超市特产、折扣装要分别用不同的“购买规则”对待。

Q8. 关于各变体背包的时间复杂度，下列说法正确的是？

多选题 · hard

  • A.01 背包为 O(nC)← 正确答案
  • B.完全背包为 O(nC)← 正确答案
  • C.二进制拆分后的多重背包为 O(nC log m)← 正确答案
  • D.单调队列优化的多重背包为 O(nC)← 正确答案

答案：ABCD。01 和完全都是两重循环 O(nC)。二进制拆分把每种 m 件拆成 O(log m) 组，总复杂度 O(nC log m)。单调队列优化把“枚举件数”的循环消去，每种物品只遍历容量一次，降到 O(nC)。复杂度排序是多重背包优化的主线，也是面试追问的高频点。

Q9. 01背包转移方程 dp[j] = max(dp[j], dp[j-w_i]+v_i) 中，j-w_i 表示什么？

单选题 · easy

  • A.放入第 i 件后剩余可用的容量← 正确答案
  • B.第 i 件物品的重量减去价值
  • C.背包已经占用的空间
  • D.未放入物品的总重量

答案：A。j-w_i 是容量 j 减去第 i 件物品的重量 w_i，即放入它之后剩余的空间，交给前 i-1 件物品去最优利用。这与旅行打包完全对应：先给相机留出 2kg，剩下的重量再塞别的纪念品。

Q10. 关于多重背包的优化手段，以下哪些是正确的？

多选题 · mid

  • A.二进制拆分后再用 01 背包求解← 正确答案
  • B.单调队列优化可将复杂度降到 O(nC)← 正确答案
  • C.用贪心每次选单位价值最高的物品
  • D.完全背包的代码可以直接套用

答案：AB。二进制拆分把数量 c 拆成 O(log c) 组，转成 01 背包；单调队列进一步消去数量维度，达到 O(nC)。贪心（C）在背包问题中无法保证全局最优，因为物品不可分割且容量有限。完全背包代码（D）允许无限取用，违背多重背包的数量上限，直接套用会得到错误答案。