背包精选
来源于这里
背包九讲
洛谷日报的背包讲解
背包DP OI Wiki
01背包 模板：P1048 [NOIP2005 普及组] 采药
- P1802 5 倍经验日
01背包简单变化
- P2946 [USACO09MAR]Cow Frisbee Team S
01背包拓展
- P2340 [USACO03FALL]Cow Exhibition G
01背包的良好变形
完全背包 模板：P1616 疯狂的采药
- P2918 [USACO08NOV]Buying Hay S
考虑一下特殊情况
- P1853 投资的最大效益
利用贪心进行预处理最后累加
多重背包 模板：P1776 宝物筛选
- P5365 [SNOI2017] 英雄联盟
多重背包拓展
- P1782 旅行商的背包
较为综合
和毒瘤
混合背包 模板：P1833 樱花
- P2623 物品选取
可以直接暴力水过 注意函数背包那里是减号
- P2851 [USACO06DEC]The Fewest Coins G
分组背包+完全背包，注意最多只用跑到多少？为什么？
分组背包 模板：P1757 通天之分组背包
- P5322 [BJOI2019] 排兵布阵
其实告诉你它是分组背包就已经减难度了
多维费用背包 模板：P1507 NASA的食物计划
- P1541 [NOIP2010 提高组] 乌龟棋
四维DP
- P2732 [USACO3.3]商店购物 Shopping Offers
五维完全背包
树形背包 模板：P2014 [CTSC1997] 选课
树上背包及其优化详解
更多树形DP详见：树形DP题单
- 有依赖的背包 模板：P1064 [NOIP2006 提高组] 金明的预算方案
- P2967 [USACO09DEC]Video Game Troubles G
有依赖背包的优化
- P1273 有线电视网
树上的分组背包
- P4516 [JSOI2018] 潜入行动
devinwang倾情推荐
- P3780 [SDOI2017]苹果树
devinwang倾情推荐
泛化物品的背包
- P1336 最佳课题选择
记得开
long long
- P1417 烹调方案
算一下式子，按式子排序就可以直接背包
背包问题问法的变化
输出字典序最小的最优方案
- P2066 机器分配
注意字典序最小，最后可以倒着扫
求方案总数
- P1474 [USACO2.3]Money System / [USACO07OCT]Cow Cash G
简单求方案数
- P1385 密令
背包问题的巧妙转化
还有记得初始化
最优方案的总数
求次优解、第K优解
综合练
- CF417A Elimination
分两类背包跑
- P2904 [USACO08MAR]River Crossing S
利用背包思想
- P3985 不开心的金明
利用特殊条件压空间
- P5020 [NOIP2018 提高组] 货币系统
猜结论+完全背包可行性判断
- P5662 [CSP-J2019] 纪念品
背包问题的内容的转化
- P1941 [NOIP2014 提高组] 飞扬的小鸟
混合背包+细节处理
- P4141 消失之物
背包的灵活变化
- P2854 [USACO06DEC]Cow Roller Coaster S
二维背包拓展