【背包dp】小结

背包问题总结

一、什么是背包问题？

定义：给定一个容量为 W 的背包和 n 件物品，每件物品有一个重量 w[i] 和价值 v[i]，要求选择若干物品放入背包，在不超过容量的前提下，使总价值最大。

背包问题本质是：约束优化 + 组合选择。

---

二、什么时候考虑用“背包思想”？

你可以在如下类型的问题中尝试用背包建模：

题目特征	关键词	是否适合背包建模？
有一个资源上限（如时间、钱、容量）	“最多”、“不超过”、“限制在…”	资源即背包容量
有多个选项可选，每个选项有代价和收益	“每个选择有花费和收益”、“从中选择一些”	每个选项就是一个“物品”
要最大化或最小化一个目标值（如最大收益、最小时间）	“求最大值/最小值”、“最优”	属于优化问题
每个选项只能选一次/多次/无限次	“可重复选”/“不可重复”	可映射到 0-1、完全、多重背包
组合问题，多个变量之间的选择组合	“在多个物品中挑选”	用状态转移建模组合方式

一句话记忆：
多个物品（选项），有一个资源限制，要做出最优组合决策，就可以考虑“背包思想”。

---

三、常见背包模型（及其差异）

类型	是否可重复	限制条件	应用举例
0-1 背包	否	每个物品最多选一次	挑战任务只能做一次
完全背包	是（无限）	每个物品可选任意次	硬币兑换、无限库存商品
多重背包	是（有限）	每个物品最多选 k 次	有限库存下的选购问题
分组背包	分组内最多选一个	每组内只能选一个	每种类别选一个代表
混合背包	混合限制	混合以上任意模型	综合现实场景，如同时有限和无限物品
二维/多维背包	多维限制	除重量外还有其他限制	同时限制时间/金钱等多种资源

---

四、状态表示 & 转移方程

通用思路

• 状态定义：dp[i][j] 表示前 i 个物品中，容量为 j 时可获得的最大价值。

• 状态转移：

  • 不选第 i 个物品：dp[i][j] = dp[i-1][j]
  • 选第 i 个物品：dp[i][j] = dp[i-1][j - w[i]] + v[i]（要满足 j >= w[i]）

状态压缩（降维优化）

因为 dp[i][*] 只依赖于 dp[i-1][*]，所以可以使用一维数组。

各类背包的一维优化写法对比：

类型	j 遍历顺序	解释
0-1 背包	for j from W down to w[i]	倒序：防止多次选择同一物品
完全背包	for j from w[i] to W	正序：允许重复使用当前物品
多重背包（二进制拆分）	拆成若干个 0-1 物品后处理	防止超时

---

五、例题归类（每种类型都附带一个经典应用）

背包类型	题目示例	描述
0-1 背包	经典最大价值问题	n 件物品，每个选一次，背包容量为 W
完全背包	硬币兑换	无限数量的硬币组成目标金额
多重背包	商品选购	每种商品有库存限制
分组背包	项目选择	每类项目只能选一个，例如 CPU/显卡/内存 各选一个
混合背包	商店打折组合	有些商品有限，有些无限
二维背包	同时限制金钱和时间	如同时给出“时间限制”和“重量限制”

---

六、注意事项 & 常见错误

问题	错误描述	正确做法
遍历顺序写错	完全背包使用倒序	完全背包需正序遍历 j
状态转移写错	忘了判断 j >= w[i]	加上条件判断
多重背包暴力写法超时	三重循环	用二进制拆分优化
使用二维数组时初始化错	未初始化第 0 行	初始化 dp[0][*] 为 0

---

七、总结口诀

背包问题口诀：

多个物品选几个，容量限制是核心；
选或不选看约束，价值最大找最优；
可重复用正序扫，只能选一次就倒流；
多重拆成 0-1 背，分组记得内部分组选。