02.7.1.2 背包问题
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.1 DP 基础与线性 DP
02.7.1.2-001 背包问题怎么分类?
一句话结论
按物品选取次数分 01 背包(最多一次)、完全背包(无限次)、多重背包(有限次);按目标分最大价值、方案数、恰好装满;状态通常为物品下标 × 容量。
概念解释
- 选取次数:一次/无限/有限。
- 目标:最值、计数、可行性。
原理流程
- 确认物品可否重复取。
- 明确目标是最值还是计数。
- 选对应方程与遍历顺序。
代码 / 图示
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 件。
原理流程
- 定义二维状态。
- 方程取两种末步最大。
- 填表取 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] 仍是上一层旧值,防止同一物品被重复装入;正序会让物品被多次使用,变成完全背包。
概念解释
- 压缩:只留容量维。
- 倒序:保护旧值不被覆盖。
原理流程
- 二维压一维。
- 容量从大到小更新。
- 前驱 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 背包倒序正好相反。
概念解释
- 可重复:同物品多次入包。
- 正序:复用本轮新值。
原理流程
- 外层物品。
- 容量从小到大。
- 转移可再次选当前物品。
代码 / 示例
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 表示该容量无法恰好凑出。
概念解释
- 恰好装满:必须用尽容量。
- 不可达:负无穷标记。
原理流程
- 判断题型是否恰好。
- 不可达填 -INF,dp[0]=0。
- 转移跳过不可达前驱。
代码 / 示例
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 完全背包求组合数与排列数外层顺序怎么排?
一句话结论
求组合数(不区分顺序):外层物品、内层容量;求排列数(区分顺序):外层容量、内层物品;顺序不同方案是否计入决定两层谁在外。
概念解释
- 组合:物品种类外循环。
- 排列:容量外循环。
原理流程
- 判断方案是否区分顺序。
- 组合:物品质外层。
- 排列:容量外层。
代码 / 示例
// 组合数:外层物品
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。
概念解释
- 完全背包:硬币可重复用。
- 最值:最少枚数。
原理流程
- 定义金额 j 最少硬币数。
- 方程枚举每种硬币转移。
- 不可达返回 -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]。
概念解释
- 组合数:顺序不计。
- 外层物品:固定种类顺序。
原理流程
- 计数状态 dp[j]。
- 外层硬币累加方案。
- 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 背包计数。
概念解释
- 转化:正负分配变子集和。
- 计数:选法方案数。
原理流程
- 推导出正数目标 P。
- 校验 P 合法(非负、整数)。
- 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。
原理流程
- 总和奇偶判断。
- 目标 half。
- 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。
概念解释
- 二进制拆分:数量打包成组。
- 等价组合:各组可拼出任意件数。
原理流程
- 按 2 的幂拆 c 件。
- 每组权重价值合并。
- 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 分组。
- 滑动窗口:限件数内取最值。
原理流程
- 按余数分组。
- 单调队列维护窗口最优。
- 转移取队首。
代码 / 示例
同余链上,窗口长度为件数限制,队首给最优前驱
常见误区
- 误区:所有多重背包都需单调队列;正解:数据量小二进制拆分足够。
- 误区:队列窗口边界写错;正解:超出件数限制弹出队首。
追问
- Q:优化后复杂度? A:O(nW)。
- Q:什么时候用二进制拆分? A:件数不大、追求实现简单。
02.7.1.2-013 背包求方案数怎么写方程?
一句话结论
最值背包把 max 换成累加:可达前驱方案数相加;01 倒序、完全按组合/排列定顺序;初始化 dp[0]=1;不可达为 0;注意物品重复选取对应的顺序。
概念解释
- 计数:累加前驱方案。
- 基准:空集 1 种。
原理流程
- 状态存方案数。
- 方程求和替代取最值。
- 顺序按组合/排列。
代码 / 示例
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 件,沿前驱回溯记录物品;只存最值无法还原方案。
概念解释
- 全表保留:回推需要各层状态。
- 前驱回推:逐件判断选否。
原理流程
- 二维 DP 填表。
- 终态倒推每件选否。
- 收集选中物品。
代码 / 示例
若 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]。
概念解释
- 可重复:步数反复用。
- 有序:不同顺序算不同。
原理流程
- 外层目标高度。
- 内层枚举步幅。
- 累加前驱方案。
代码 / 示例
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 背包价值/重量约束怎么转换?
一句话结论
题目约束可能是重量、数量、体积或成本,统一抽象为“容量维度”;目标是价值最大或方案计数;多约束时增加对应维度(二维背包),状态为物品 × 各约束容量。
概念解释
- 容量维度:被消耗的约束。
- 多约束:多维状态。
原理流程
- 识别消耗型约束。
- 映射为容量维。
- 多约束加维度。
代码 / 示例
二维背包: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] 已被本轮改写,当前物品被重复装入。
概念解释
- 旧值保护:小容量未被覆盖。
- 重复使用:新值含当前物品。
原理流程
- 压缩后数组存上一层。
- 倒序保证前驱为旧值。
- 当前物品只入一次。
代码 / 图示
倒序 j: W→w;j-w < j 尚未更新 → 旧层值
正序 j: w→W;j-w 已更新 → 重复使用
常见误区
- 误区:认为倒序只是习惯;正解:是防重复的必要条件。
- 误区:物品可重入也倒序;正解:那是完全背包。
追问
- Q:二维为什么不用倒序? A:前驱在 i-1 层,物理隔离。
- Q:怎么验证重复使用? A:小例对比同一物品出现次数。
02.7.1.2-018 背包空间优化后遍历顺序注意什么?
一句话结论
一维后按背包类型定方向:01 倒序、完全正序;外层始终是物品(最值);计数再按组合/排列调整外层;优化不改变转移方程,只改数组复用方式。
概念解释
- 方向:01/完全。
- 外层:物品或容量。
原理流程
- 判断物品可否重复。
- 定容量遍历方向。
- 计数按顺序定外层。
代码 / 示例
01:物品质外,容量倒序;完全最值:物品质外,容量正序
常见误区
- 误区:优化后改变转移语义;正解:方程不变,只复用数组。
- 误区:计数题外层照搬最值写法;正解:组合/排列要调外层。
追问
- Q:一维数组初始值怎么设? A:按恰好/不装满与最值/计数分别处理。
- Q:优化后还能二维回推方案吗? A:不能,需保留二维表。
02.7.1.2-019 背包常见初始化与顺序误区有哪些?
一句话结论
高频误区:恰好装满未用 -INF、01 正序重复选、完全倒序漏解、计数外层顺序错、dp[0] 基准填错;先判断题型(01/完全、最值/计数、恰好/不超)再套初始化与顺序。
概念解释
- 题型矩阵:选取次数 × 目标 × 约束。
- 初始化:基准与不可达。
原理流程
- 归类背包类型。
- 定初始化。
- 定遍历方向与外层。
代码 / 示例
排查:01/完全 / 最值/计数 / 恰好/不超 / 外层顺序
常见误区
- 误区:一题套所有模板;正解:先分类再选写法。
- 误区:不可达状态参与取最值;正解:-INF 隔离。
追问
- Q:结果为负可能是什么错? A:恰好装满初始化或不可达未隔离。
- Q:方案数偏大? A:排列组合外层顺序错或 01 重复选。
02.7.1.2-020 背包复杂度 O(nW) 怎么理解?
一句话结论
n 件物品、容量 W,每件物品在每个容量上做一次常数转移,时间 O(nW);一维空间 O(W),二维 O(nW);多重背包拆分后乘 log c;状态随容量线性,容量过大需对偶或剪枝。
概念解释
- 状态:物品 × 容量。
- 转移:单状态常数次比较/累加。
原理流程
- 数状态 n×W。
- 单状态 O(1) 转移。
- 空间按表或一维。
代码 / 示例
01/完全:O(nW);多重拆分:O(n·log c·W)
常见误区
- 误区:背包复杂度按物品数 O(n);正解:容量维也在状态里。
- 误区:W 很大仍开数组;正解:价值对偶或判断不可行。
追问
- Q:容量 W 超内存怎么办? A:按价值 DP,求达到价值的最小重量。
- Q:背包能贪心吗? A:一般不能,需 DP 枚举取舍。