罗罗编程学习记录
本页内容 展开查看

02.7.1.2 背包问题

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.1 DP 基础与线性 DP

02.7.1.2-001 背包问题怎么分类?

一句话结论

按物品选取次数分 01 背包(最多一次)、完全背包(无限次)、多重背包(有限次);按目标分最大价值、方案数、恰好装满;状态通常为物品下标 × 容量。

概念解释

  • 选取次数:一次/无限/有限。
  • 目标:最值、计数、可行性。

原理流程

  1. 确认物品可否重复取。
  2. 明确目标是最值还是计数。
  3. 选对应方程与遍历顺序。

代码 / 图示

01:每物一次;完全:无限;多重:有限次

常见误区

  • 误区:所有背包都倒序;正解:只有 01 背包倒序。
  • 误区:背包只求最大价值;正解:也可计数或判可行性。

追问

  • Q:背包状态怎么定义? A:dp[j] 容量 j 下的目标值。
  • Q:容量很大怎么办? A:按价值做对偶 DP,或判断不可行。

02.7.1.2-002 01 背包二维怎么写?

一句话结论

dp[i][j] 前 i 件物品容量 j 的最大价值;不选第 i 件取 dp[i-1][j],选则 dp[i-1][j-w[i]]+v[i];初始化 dp[0][j]=0;外层物品内层容量;时间 O(nW),空间 O(nW)。

概念解释

  • 状态:前 i 件、容量 j。
  • 末步:选/不选第 i 件。

原理流程

  1. 定义二维状态。
  2. 方程取两种末步最大。
  3. 填表取 dp[n][W]。

代码 / 示例

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= W; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j >= w[i - 1])
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
    }

常见误区

  • 误区:选物品时用当前层 dp[i];正解:01 背包前驱是上一层 i-1。
  • 误区:容量不足仍转移;正解:先判 j>=w[i]。

追问

  • Q:二维表第一行怎么填? A:0 件物品价值 0。
  • Q:复杂度? A:O(nW) 时间空间。

02.7.1.2-003 01 背包一维为什么倒序?

一句话结论

一维压缩后 dp[j] 复用上一层值;倒序遍历容量保证更新 dp[j] 时 dp[j-w] 仍是上一层旧值,防止同一物品被重复装入;正序会让物品被多次使用,变成完全背包。

概念解释

  • 压缩:只留容量维。
  • 倒序:保护旧值不被覆盖。

原理流程

  1. 二维压一维。
  2. 容量从大到小更新。
  3. 前驱 j-w 尚未被本轮覆盖。

代码 / 示例

for (int i = 0; i < n; i++)
    for (int j = W; j >= w[i]; j--)
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);

常见误区

  • 误区:一维也正序;正解:01 必须倒序。
  • 误区:倒序起点写成 W-1;正解:到 w[i] 为止。

追问

  • Q:倒序为什么能防重复? A:小容量旧值先保留,未被本轮改写。
  • Q:空间优化后是几层? A:O(W)。

02.7.1.2-004 完全背包为什么正序?

一句话结论

物品可无限次选取,容量正序遍历使更新 dp[j] 时 dp[j-w] 可能已是本轮含该物品的新值,从而允许再次装入同一物品;与 01 背包倒序正好相反。

概念解释

  • 可重复:同物品多次入包。
  • 正序:复用本轮新值。

原理流程

  1. 外层物品。
  2. 容量从小到大。
  3. 转移可再次选当前物品。

代码 / 示例

for (int i = 0; i < n; i++)
    for (int j = w[i]; j <= W; j++)
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);

常见误区

  • 误区:完全背包也倒序;正解:正序才允许重复取。
  • 误区:外层容量内层物品;正解:求最大价值两种顺序均可,计数组合/排列有区别。

追问

  • Q:完全背包能取多少次? A:受容量上限约束。
  • Q:复杂度? A:O(nW)。

02.7.1.2-005 恰好装满怎么初始化?

一句话结论

要求容量恰好装满时,不可达状态初始化为 -INF,dp[0]=0;普通“不超过容量”问题初始全 0;转移后仍为 -INF 表示该容量无法恰好凑出。

概念解释

  • 恰好装满:必须用尽容量。
  • 不可达:负无穷标记。

原理流程

  1. 判断题型是否恰好。
  2. 不可达填 -INF,dp[0]=0。
  3. 转移跳过不可达前驱。

代码 / 示例

Arrays.fill(dp, -INF);
dp[0] = 0;
// 仅当 dp[j-w] 可达才转移

常见误区

  • 误区:恰好装满也全 0 初始化;正解:0 会被误认为合法价值。
  • 误区:价值可为负处理 -INF 冲突;正解:取足够小的负数。

追问

  • Q:计数型恰好装满? A:dp[0]=1,其余 0。
  • Q:不要求装满呢? A:全 0 即可。

02.7.1.2-006 完全背包求组合数与排列数外层顺序怎么排?

一句话结论

求组合数(不区分顺序):外层物品、内层容量;求排列数(区分顺序):外层容量、内层物品;顺序不同方案是否计入决定两层谁在外。

概念解释

  • 组合:物品种类外循环。
  • 排列:容量外循环。

原理流程

  1. 判断方案是否区分顺序。
  2. 组合:物品质外层。
  3. 排列:容量外层。

代码 / 示例

// 组合数:外层物品
for (x : nums) for (j = x; j <= target; j++) dp[j] += dp[j - x];
// 排列数:外层容量
for (j = 1; j <= target; j++) for (x : nums) if (j >= x) dp[j] += dp[j - x];

常见误区

  • 误区:两种计数顺序混用;正解:外层顺序决定是否计顺序。
  • 误区:排列数还去重物品顺序;正解:排列本来就计顺序。

追问

  • Q:零钱兑换 II 是哪种? A:组合数,外层硬币。
  • Q:组合总和 IV 是哪种? A:排列数,外层容量。

02.7.1.2-007 零钱兑换 I(LC 322)怎么 DP?

一句话结论

dp[j] 凑金额 j 的最少硬币数;完全背包,初始化 dp[0]=0、其余 INF;外层硬币内层金额正序,dp[j]=min(dp[j], dp[j-c]+1);返回 dp[amount],不可达为 -1。

概念解释

  • 完全背包:硬币可重复用。
  • 最值:最少枚数。

原理流程

  1. 定义金额 j 最少硬币数。
  2. 方程枚举每种硬币转移。
  3. 不可达返回 -1。

代码 / 示例

int[] dp = new int[amount + 1];
Arrays.fill(dp, INF); dp[0] = 0;
for (int c : coins)
    for (int j = c; j <= amount; j++)
        dp[j] = Math.min(dp[j], dp[j - c] + 1);
return dp[amount] == INF ? -1 : dp[amount];

常见误区

  • 误区:初始化成 0;正解:最少枚数不可达要 INF。
  • 误区:倒序遍历;正解:完全背包正序。

追问

  • Q:复杂度? A:O(n·amount),空间 O(amount)。
  • Q:能贪心吗? A:一般硬币体系不行,需 DP 保证最优。

02.7.1.2-008 零钱兑换 II(LC 518)怎么求组合数?

一句话结论

dp[j] 凑金额 j 的硬币组合数;外层硬币、内层金额正序,保证硬币种类顺序固定,不重复计排列;dp[0]=1;返回 dp[amount]。

概念解释

  • 组合数:顺序不计。
  • 外层物品:固定种类顺序。

原理流程

  1. 计数状态 dp[j]。
  2. 外层硬币累加方案。
  3. dp[0]=1 基准。

代码 / 示例

dp[0] = 1;
for (int c : coins)
    for (int j = c; j <= amount; j++)
        dp[j] += dp[j - c];

常见误区

  • 误区:外层金额内层硬币;正解:那会算成排列数。
  • 误区:dp[0] 初始 0;正解:空组合 1 种。

追问

  • Q:与 LC 322 区别? A:一个求最少枚数,一个求组合数。
  • Q:复杂度? A:O(n·amount)。

02.7.1.2-009 目标和(LC 494)怎么转 01 背包?

一句话结论

选若干取正、其余取负,设正数和 P、负数和 N,P+N=sum、P-N=target,得 P=(sum+target)/2;问题转为从数组选若干元素和为 P 的方案数,01 背包计数。

概念解释

  • 转化:正负分配变子集和。
  • 计数:选法方案数。

原理流程

  1. 推导出正数目标 P。
  2. 校验 P 合法(非负、整数)。
  3. 01 背包倒序计数。

代码 / 示例

int P = (sum + target) / 2;
dp[0] = 1;
for (int x : nums)
    for (int j = P; j >= x; j--) dp[j] += dp[j - x];

常见误区

  • 误区:(sum+target) 为奇数还计算;正解:无解返回 0。
  • 误区:完全背包正序;正解:每元素一次,倒序。

追问

  • Q:P 小于 0 怎么办? A:无解。
  • Q:复杂度? A:O(n·P)。

02.7.1.2-010 分割等和子集(LC 416)怎么做?

一句话结论

总和为奇数直接 false;目标容量 sum/2,01 背包判断能否凑出该子集;dp[j] 表示能否凑出容量 j,布尔/计数均可;倒序更新;时间 O(n·sum),空间 O(sum)。

概念解释

  • 子集和:选一部分元素。
  • 可行性:布尔 DP。

原理流程

  1. 总和奇偶判断。
  2. 目标 half。
  3. 01 背包可行性填表。

代码 / 示例

boolean[] dp = new boolean[half + 1];
dp[0] = true;
for (int x : nums)
    for (int j = half; j >= x; j--)
        dp[j] |= dp[j - x];

常见误区

  • 误区:总和奇数直接尝试;正解:先奇偶剪枝。
  • 误区:正序允许重复选元素;正解:01 倒序。

追问

  • Q:复杂度? A:O(n·sum),空间 O(sum)。
  • Q:元素大于 half 怎么办? A:天然不可选,循环自然跳过。

02.7.1.2-011 多重背包怎么用二进制拆分?

一句话结论

每种物品有限 c 件,拆成 1、2、4… 二进制组,每组视为一个 01 物品;任意 0~c 件都由这些组组合表示;拆分后按 01 背包倒序处理,把多重转为 01。

概念解释

  • 二进制拆分:数量打包成组。
  • 等价组合:各组可拼出任意件数。

原理流程

  1. 按 2 的幂拆 c 件。
  2. 每组权重价值合并。
  3. 01 背包倒序枚举。

代码 / 示例

for (int k = 1; k <= c; c -= k, k <<= 1) {
    // 物品组:重量 k*w,价值 k*v
}

常见误区

  • 误区:余数不打包;正解:最后剩余件数单独成组。
  • 误区:拆分后按完全背包;正解:每组是 01 物品。

追问

  • Q:拆分后物品数多少? A:O(log c) 每组。
  • Q:复杂度? A:O(n·log c·W)。

02.7.1.2-012 多重背包单调队列优化是什么思路?

一句话结论

按容量模余数分组,同组内转移是滑动窗口最值;用单调队列维护窗口内最优前驱,把每种物品的转移从 O(c·W) 降到 O(W);属进阶优化,面试能讲清思路即可。

概念解释

  • 同余组:j 按模 w 分组。
  • 滑动窗口:限件数内取最值。

原理流程

  1. 按余数分组。
  2. 单调队列维护窗口最优。
  3. 转移取队首。

代码 / 示例

同余链上,窗口长度为件数限制,队首给最优前驱

常见误区

  • 误区:所有多重背包都需单调队列;正解:数据量小二进制拆分足够。
  • 误区:队列窗口边界写错;正解:超出件数限制弹出队首。

追问

  • Q:优化后复杂度? A:O(nW)。
  • Q:什么时候用二进制拆分? A:件数不大、追求实现简单。

02.7.1.2-013 背包求方案数怎么写方程?

一句话结论

最值背包把 max 换成累加:可达前驱方案数相加;01 倒序、完全按组合/排列定顺序;初始化 dp[0]=1;不可达为 0;注意物品重复选取对应的顺序。

概念解释

  • 计数:累加前驱方案。
  • 基准:空集 1 种。

原理流程

  1. 状态存方案数。
  2. 方程求和替代取最值。
  3. 顺序按组合/排列。

代码 / 示例

dp[0] = 1;
for (int x : nums)
    for (int j = W; j >= x; j--) dp[j] += dp[j - x];

常见误区

  • 误区:计数也取 max;正解:方案数累加。
  • 误区:初始化 dp[0]=0;正解:空方案 1。

追问

  • Q:计数溢出怎么办? A:按题意取模。
  • Q:组合与排列计数区别? A:外层顺序不同。

02.7.1.2-014 背包求具体方案怎么记录?

一句话结论

二维填表保留全表(不能压缩),结束后从 dp[n][W] 回推:比较是否选了第 i 件,沿前驱回溯记录物品;只存最值无法还原方案。

概念解释

  • 全表保留:回推需要各层状态。
  • 前驱回推:逐件判断选否。

原理流程

  1. 二维 DP 填表。
  2. 终态倒推每件选否。
  3. 收集选中物品。

代码 / 示例

若 dp[i][j] == dp[i-1][j] 未选;否则选 i 并减 w[i]

常见误区

  • 误区:一维压缩后回推;正解:历史层已覆盖,需二维。
  • 误区:等值方案任选记录不一致;正解:按题意规则选其一。

追问

  • Q:方案数多要全部输出吗? A:回溯枚举,DP 只辅助剪枝。
  • Q:回推顺序? A:从 n 到 1 倒推。

02.7.1.2-015 完全背包爬楼梯式排列怎么理解?

一句话结论

每步可走指定台阶数、求爬到顶的方法数,元素可重复且顺序计入,对应完全背包排列数:外层台阶数(容量)、内层步数(物品),dp[j]=Σdp[j-step]。

概念解释

  • 可重复:步数反复用。
  • 有序:不同顺序算不同。

原理流程

  1. 外层目标高度。
  2. 内层枚举步幅。
  3. 累加前驱方案。

代码 / 示例

dp[0] = 1;
for (int j = 1; j <= n; j++)
    for (int s : steps)
        if (j >= s) dp[j] += dp[j - s];

常见误区

  • 误区:外层步幅;正解:排列数要容量外层。
  • 误区:倒序;正解:可重复正序。

追问

  • Q:与组合总和 IV 关系? A:同一类排列型完全背包。
  • Q:复杂度? A:O(n·k),k 步幅种类。

02.7.1.2-016 背包价值/重量约束怎么转换?

一句话结论

题目约束可能是重量、数量、体积或成本,统一抽象为“容量维度”;目标是价值最大或方案计数;多约束时增加对应维度(二维背包),状态为物品 × 各约束容量。

概念解释

  • 容量维度:被消耗的约束。
  • 多约束:多维状态。

原理流程

  1. 识别消耗型约束。
  2. 映射为容量维。
  3. 多约束加维度。

代码 / 示例

二维背包:dp[i][j][k],重量 j、体积 k

常见误区

  • 误区:多约束压成一个容量;正解:独立约束各占一维。
  • 误区:价值当容量;正解:价值是目标,不是消耗。

追问

  • Q:背包容量很大怎么办? A:按价值做对偶,状态为价值求最小重量。
  • Q:二维背包复杂度? A:O(n·W·V)。

02.7.1.2-017 01 背包倒序防重复使用的原理再说明

一句话结论

倒序更新时,计算 dp[j] 用到的 dp[j-w] 位于更小容量,本轮尚未被遍历到,仍是上一层(未含当前物品)的值;正序时 dp[j-w] 已被本轮改写,当前物品被重复装入。

概念解释

  • 旧值保护:小容量未被覆盖。
  • 重复使用:新值含当前物品。

原理流程

  1. 压缩后数组存上一层。
  2. 倒序保证前驱为旧值。
  3. 当前物品只入一次。

代码 / 图示

倒序 j: W→w;j-w < j 尚未更新 → 旧层值
正序 j: w→W;j-w 已更新 → 重复使用

常见误区

  • 误区:认为倒序只是习惯;正解:是防重复的必要条件。
  • 误区:物品可重入也倒序;正解:那是完全背包。

追问

  • Q:二维为什么不用倒序? A:前驱在 i-1 层,物理隔离。
  • Q:怎么验证重复使用? A:小例对比同一物品出现次数。

02.7.1.2-018 背包空间优化后遍历顺序注意什么?

一句话结论

一维后按背包类型定方向:01 倒序、完全正序;外层始终是物品(最值);计数再按组合/排列调整外层;优化不改变转移方程,只改数组复用方式。

概念解释

  • 方向:01/完全。
  • 外层:物品或容量。

原理流程

  1. 判断物品可否重复。
  2. 定容量遍历方向。
  3. 计数按顺序定外层。

代码 / 示例

01:物品质外,容量倒序;完全最值:物品质外,容量正序

常见误区

  • 误区:优化后改变转移语义;正解:方程不变,只复用数组。
  • 误区:计数题外层照搬最值写法;正解:组合/排列要调外层。

追问

  • Q:一维数组初始值怎么设? A:按恰好/不装满与最值/计数分别处理。
  • Q:优化后还能二维回推方案吗? A:不能,需保留二维表。

02.7.1.2-019 背包常见初始化与顺序误区有哪些?

一句话结论

高频误区:恰好装满未用 -INF、01 正序重复选、完全倒序漏解、计数外层顺序错、dp[0] 基准填错;先判断题型(01/完全、最值/计数、恰好/不超)再套初始化与顺序。

概念解释

  • 题型矩阵:选取次数 × 目标 × 约束。
  • 初始化:基准与不可达。

原理流程

  1. 归类背包类型。
  2. 定初始化。
  3. 定遍历方向与外层。

代码 / 示例

排查:01/完全 / 最值/计数 / 恰好/不超 / 外层顺序

常见误区

  • 误区:一题套所有模板;正解:先分类再选写法。
  • 误区:不可达状态参与取最值;正解:-INF 隔离。

追问

  • Q:结果为负可能是什么错? A:恰好装满初始化或不可达未隔离。
  • Q:方案数偏大? A:排列组合外层顺序错或 01 重复选。

02.7.1.2-020 背包复杂度 O(nW) 怎么理解?

一句话结论

n 件物品、容量 W,每件物品在每个容量上做一次常数转移,时间 O(nW);一维空间 O(W),二维 O(nW);多重背包拆分后乘 log c;状态随容量线性,容量过大需对偶或剪枝。

概念解释

  • 状态:物品 × 容量。
  • 转移:单状态常数次比较/累加。

原理流程

  1. 数状态 n×W。
  2. 单状态 O(1) 转移。
  3. 空间按表或一维。

代码 / 示例

01/完全:O(nW);多重拆分:O(n·log c·W)

常见误区

  • 误区:背包复杂度按物品数 O(n);正解:容量维也在状态里。
  • 误区:W 很大仍开数组;正解:价值对偶或判断不可行。

追问

  • Q:容量 W 超内存怎么办? A:按价值 DP,求达到价值的最小重量。
  • Q:背包能贪心吗? A:一般不能,需 DP 枚举取舍。