背包问题

题单介绍

个人在学习背包问题时积累的题目,在每种问题中选取了部分比较经典的题目,供练习. **如果想锻炼思维,直接看题目列表** [洛谷日报 #61 背包问题](https://www.luogu.com.cn/blog/RPdreamer/bei-bao-wen-ti) 本人已退役,不定时上线,有建议可私聊 ### 01背包 [P1048 采药](https://www.luogu.com.cn/problem/P1048) [P1049 装箱问题](https://www.luogu.com.cn/problem/P1049) [P1164 小A点菜](https://www.luogu.com.cn/problem/P1164) [P1060 开心的金明](https://www.luogu.com.cn/problem/P1060) [P3985 不开心的金明](https://www.luogu.com.cn/problem/P3985) ### 完全背包 [P1616 疯狂的采药](https://www.luogu.com.cn/problem/P1616) [P2722 USACO3.1总分 Score Inflation](https://www.luogu.com.cn/problem/P2722) [P1853 投资的最大效益](https://www.luogu.com.cn/problem/P1853) [P2918 USACO08NOV Buying Hay S](https://www.luogu.com.cn/problem/P2918) ### 多重背包 #### 弱化 [P1833 樱花](https://www.luogu.com.cn/problem/P1833) [P5365 SNOI2017 英雄联盟](https://www.luogu.com.cn/problem/P5365) [P1077 摆花](https://www.luogu.com.cn/problem/solution/P1077) #### 可行性问题 [P2347 砝码称重](https://www.luogu.com.cn/problem/P2347) #### 二进制优化/单调栈优化 [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776) [P1782 旅行商的背包](https://www.luogu.com.cn/problem/P1782) ### 多维背包 [P1855 榨取kkksc03](https://www.luogu.com.cn/problem/P1855) [P1507 NASA的食物计划](https://www.luogu.com.cn/problem/P1507) [P1541 乌龟棋](https://www.luogu.com.cn/problem/P1541) [P2732 USACO3.3 商店购物 Shopping Offers](https://www.luogu.com.cn/problem/P2732) 关于多维多重背包/多维完全背包 在洛谷上暂未找到,欢迎私信补充. ### 混合背包 [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) ### 有依赖的背包 [P1064 金明的预算方案](https://www.luogu.com.cn/problem/P1064) [P1273 有线电视网](https://www.luogu.com.cn/problem/P1273) ### 通关练习(实际上不知道分到哪里) [P5662 纪念品](https://www.luogu.com.cn/problem/P5662) [P4141 消失之物](https://www.luogu.com.cn/problem/P4141) [P1941 飞扬的小鸟](https://www.luogu.com.cn/problem/P1941)

题目列表

  • [NOIP2005 普及组] 采药
  • [NOIP2001 普及组] 装箱问题
  • 小A点菜
  • 不开心的金明
  • [NOIP2006 普及组] 开心的金明
  • 疯狂的采药
  • [USACO3.1]总分 Score Inflation
  • 投资的最大效益
  • [USACO08NOV]Buying Hay S
  • 樱花
  • [SNOI2017] 英雄联盟
  • [NOIP1996 提高组] 砝码称重
  • 宝物筛选
  • 旅行商的背包
  • 榨取kkksc03
  • NASA的食物计划
  • [NOIP2010 提高组] 乌龟棋
  • [USACO3.3]商店购物 Shopping Offers
  • [USACO06DEC]The Fewest Coins G
  • 通天之分组背包
  • [BJOI2019] 排兵布阵
  • [NOIP2006 提高组] 金明的预算方案
  • 有线电视网
  • [CSP-J2019] 纪念品
  • 消失之物
  • [NOIP2014 提高组] 飞扬的小鸟