背包精选

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