杨校老师课堂之备战信息学奥赛算法背包DP练习题汇总
背包DP（动态规划）是解决一类在容量限制下选择物品以获得最大价值或满足特定条件的优化问题。其核心模型为：
-
问题描述：有 N 个物品，第 i个物品体积为 vi，价值为 wi，背包总容量为 V。需选择物品装入背包，使得总体积不超过 V 且总价值最大。
-
关键思想：通过状态转移方程表示不同容量下的最优解，逐步递推求解全局最优。
背包DP的主要类型
-
0-1背包
-
每个物品只能选或不选一次。
-
状态转移方程：f[j]=max(f[j],f[j−vi]+wi)，需逆序遍历容量。
-
例题：洛谷 P1048（采药）、P2871（Charm Bracelet）。
-
-
完全背包
-
每个物品可无限次选取。
-
状态转移方程同0-1背包，但需正序遍历容量。
-
例题：洛谷 P2722（Score Inflation）。
-
-
多重背包
-
物品最多选 ki 次。
-
优化方法：二进制拆分（将 ki 分解为若干2的幂次之和）。
-
例题：洛谷 P1833（樱花）。
-
-
分组背包
-
物品分组，每组最多选一个。
-
状态转移时需遍历组内所有物品。
-
例题：洛谷 P1757（通天之分组背包）。
-
-
多维费用背包
-
背包限制多个维度（如体积+重量）。
-
状态需多维数组表示。
-
例题：洛谷 P1855（榨取kkksc03）。
-
-
依赖背包
-
选某物品需先选其依赖项（如树形结构）。
-
常结合树形DP实现。
-
例题：洛谷 P2014（选课）。
-
-
变种问题
-
求装满背包的方案数、前 k优解、必须装满等。
-
例题：洛谷 P1164（小A点菜）、P1858（多人背包）。
-
如何学习背包DP？
-
从基础类型入手
-
先掌握0-1背包和完全背包的状态定义、转移方程及空间优化方法。
-
推荐题目：洛谷 P1048、P2871、P2722。
-
-
理解遍历顺序的意义
-
0-1背包逆序避免重复选取，完全背包正序允许重复。
-
-
学习优化技巧
-
多重背包的二进制拆分，分组背包的循环顺序调整。
-
-
结合题单练习
-
按难度分类刷题，逐步掌握变种问题（如混合背包、依赖背包）。
-
-
参考经典题解
-
分析题解中的状态设计思路和边界条件处理。
-
洛谷背包DP题目推荐（共50题）
基础与经典题目（20题）
-
0-1背包
-
P1048 采药
-
P2871 [USACO07DEC] Charm Bracelet S
-
P1060 开心的金明
-
P1164 小A点菜
-
P1858 多人背包
-
-
完全背包
-
P2722 [USACO3.1] 总分 Score Inflation
-
P1616 疯狂的采药
-
-
多重背包
-
P1833 樱花
-
P1776 宝物筛选
-
-
分组背包
-
P1757 通天之分组背包
-
P1064 金明的预算方案
-
-
多维费用背包
-
P1855 榨取kkksc03
-
P1507 NASA的食物计划
-
-
依赖背包
-
P2014 [CTSC1997] 选课
-
进阶与变种题目（30题）
-
混合背包
-
P1833 樱花（多重+完全）
-
-
求方案数
-
P1164 小A点菜
-
P2340 [USACO03FALL] Cow Exhibition G
-
-
树形背包
-
P2014 [CTSC1997] 选课
-
P1272 重建道路
-
-
特殊限制
-
P1417 烹调方案（时间排序+0-1背包）
-
P1941 飞扬的小鸟（背包建模）
-
其他变种
-
P1441 砝码称重（01背包变种）
-
P1926 小书童——刷题大军
注意事项
-
识别问题类型：判断是0-1、完全、多重还是其他变种背包。
-
边界条件：初始化时需注意是否要求“恰好装满”。
-
空间优化：优先使用一维数组（滚动数组）
一、基础背包类型（25题）
1. 0-1背包（核心模型，必刷）
-
P1048 采药（经典入门，容量限制下的最大价值）
-
P2871 [USACO07DEC] Charm Bracelet S（基础0-1背包）
-
P1060 开心的金明（价格×重要度的变种0-1背包）
-
P1164 小A点菜（求恰好装满的方案数）
-
P2925 [USACO08DEC] Hay For Sale S（体积最大化问题）
-
P2639 [USACO09OCT] Bessie's Weight Problem G（体积最大化）
-
P1734 最大约数和（预处理约数和+0-1背包）
-
P1466 集合 Subset Sums（分割等和子集）
-
P1537 弹珠（多重背包转化为0-1背包）
-
P1855 榨取kkksc03（二维费用背包，时间+金钱）
2. 完全背包（无限次选择）
-
P2722 [USACO3.1] 总分 Score Inflation（基础完全背包）
-
P1616 疯狂的采药（完全背包经典题）
-
P1586 硬币（完全背包求方案数）
-
P2563 换教室（概率问题结合完全背包）
3. 多重背包（有限次数选择）
-
P1833 樱花（多重背包+混合背包）
-
P1776 宝物筛选（二进制拆分优化模板题）
-
P1782 旅行商的背包（多重背包+贪心）
二、进阶与变种（25题）
4. 分组背包（每组选一个）
-
P1757 通天之分组背包（分组模板题）
-
P1064 金明的预算方案（依赖背包+分组）
-
P2066 机器分配（分组+路径记录）
-
P1455 搭配购买（并查集预处理+分组）
5. 多维费用背包（多限制条件）
-
P1507 NASA的食物计划（体积+重量双限制）
-
P1910 连续自然数和（二维费用变种）
-
P1794 装备运输（体积+重量最大化）
6. 依赖背包（树形结构）
-
P2014 [CTSC1997] 选课（树形背包模板）
-
P1272 重建道路（子树保留问题）
7. 混合背包（0-1+完全+多重）
-
P1833 樱花（已列于多重背包，混合类型）
8. 特殊限制与变种
-
P1417 烹调方案（排序+0-1背包，价值随时间变化）
-
P1541 乌龟棋（多维背包，转化为卡片使用次数）
-
P1926 小书童——刷题大军（多阶段背包）
-
P1441 砝码称重（0-1背包求可称重量数）
-
P1858 多人背包（求前K优解）
-
P2340 [USACO03FALL] Cow Exhibition G（负体积处理）
-
P1941 飞扬的小鸟（完全背包+0-1背包混合）
9. 方案数及计数类
-
P1164 小A点菜（已列于0-1背包）
-
P1474 货币系统（完全背包求方案数）
-
P1566 加等式（求和为定值的子集数）
10. 扩展与综合题
-
P2854 [USACO06DEC] The Heist（贪心+背包）
-
P2306 被污染的牛奶（概率背包）
-
P3983 赛艇（多维+离散化优化）
-
P4138 挂饰（贪心预处理+0-1背包）
三、题单推荐与刷题策略
-
系统分类练习
-
优先完成基础类型（0-1、完全、多重），再挑战变种问题。
-
推荐题单：洛谷“DP全家桶#背包” ，包含P2871、P2722等经典题。
-
-
难点突破
-
树形背包：P2014需掌握DFS后序遍历与分组背包结合。
-
多维费用：P1855注意状态转移时的双重限制。
-
混合背包：P1833需先判断物品类型再选择转移方式。
-
-
优化技巧
-
空间优化：一维数组滚动（如P1048）。
-
多重背包：二进制拆分（P1776）或单调队列优化。
-
依赖问题：转化为树形结构（P1064需处理主件与附件）。
-
四、完整题号列表（共50题）
| 类型 | 题号列表（按难度排序） |
|---|---|
| 0-1背包 | P1048, P2871, P1060, P1164, P2925, P2639, P1734, P1466, P1537, P1855, P2340, P1941 |
| 完全背包 | P2722, P1616, P1586, P2563, P1474 |
| 多重背包 | P1833, P1776, P1782 |
| 分组背包 | P1757, P1064, P2066, P1455 |
| 多维背包 | P1507, P1910, P1794 |
| 依赖背包 | P2014, P1272 |
| 混合背包 | P1833 |
| 特殊变种 | P1417, P1541, P1926, P1441, P1858, P1566, P2854, P2306, P3983, P4138 |