01背包问题
题单介绍
用于学习01背包
一、经典0-1背包模板题
[P1048 [NOIP 2005 普及组] 采药](https://www.luogu.com.cn/problem/P1048)
##### 本质：纯0-1背包问题，时间即背包容量，草药是物品。
##### 关键词：模板题，入门必刷。
[P1060 [NOIP 2006 普及组] 开心的金明](https://www.luogu.com.cn/problem/P1060)
##### 变种：价值是“价格×重要度”，但核心仍是0-1背包。
二、0-1背包变种与扩展
[P1164 小A点菜](https://www.luogu.com.cn/problem/P1164)
##### 变种：背包问题求方案数，状态转移改为累加。
##### 关键点：f[j] += f[j - v[i]]。
[P1049 [NOIP 2001 普及组] 装箱问题](https://www.luogu.com.cn/problem/P1049)
##### 本质：背包容量最大化（价值=体积）。
##### 技巧：f[j] = max(f[j], f[j - v[i]] + v[i])。
[P1734 最大约数和](https://www.luogu.com.cn/problem/P1734)
##### 变种：物品是1~S的数，体积为数本身，价值为其约数和。
三、多维约束或特殊条件
[P1507 NASA的食物计划](https://www.luogu.com.cn/problem/P1507)
##### 变种：二维费用背包，状态增加一维（f[j][k]）。
[P2340 [USACO03FALL]Cow Exhibition G](https://www.luogu.com.cn/problem/P2340)
##### 技巧：将“智商”作为容量，情商为价值，偏移负数后DP。
四、输出方案或具体路径
[P1757 通天之分组背包](https://www.luogu.com.cn/problem/P1757)
##### 扩展：分组背包是0-1背包的进阶，理解后能更好掌握状态设计。
[P1417 烹调方案](https://www.luogu.com.cn/problem/P1417)
##### 关键点：贪心+背包，考察对决策顺序的理解。
[P1855 榨取kkksc03](https://www.luogu.com.cn/problem/P1855)
##### 题目描述：双重限制（金钱+时间）下的0-1背包。
##### 难度：二维费用+常规背包，适合巩固。
刷题建议
#### 从模板题开始：先刷 P1048 采药 和 P1060 开心的金明，理解状态转移方程。
#### 逐步进阶：尝试变种题（如方案数、二维费用），注意状态定义的灵活性。
#### 总结规律：
#### 0-1背包核心代码
#### 遇到变种时，思考如何调整 f[] 的含义（如方案数、最小化体积等）。