背包问题(简单)

背包问题

特点:码量较少(目前只有一题超过1KB)且难度较低,让新手也可以享受切题的快乐。

没学过背包问题的可以去看看洛谷日报中的背包问题或者背包九讲。

题目:

题目 题目解法 题目难度 实际难度
P1048 采药 01背包 \color{#FF8C00}{\tt 普及-} \color{#FF8C00}{\tt 普及-}
P2871 [USACO07DEC]Charm Bracelet S 01背包 \color{#FF8C00}{\tt 普及-} \color{#FF8C00}{\tt 普及-}
P1049 装箱问题 01背包稍微变形 \color{#FF8C00}{\tt 普及-} \color{#FF8C00}{\tt 普及-}
P1060 开心的金明 01背包稍微变形 \color{#FF8C00}{\tt 普及-} \color{#FF8C00}{\tt 普及-}
P1164 小A点菜 01背包稍微变形 \color{#FF8C00}{\tt 普及-} \color{#FF8C00}{\tt 普及-}
P1510 精卫填海 01背包稍微变形 \color{#FFD700}{普及/提高-} \color{#FF8C00}{\tt 普及-}
P2639 [USACO09OCT]Bessie's Weight Problem G 01背包稍微变形 \color{#FF8C00}{\tt 普及-} \color{#FF8C00}{\tt 普及-}
P2925 [USACO08DEC]Hay For Sale S 01背包稍微变形 \color{#FF8C00}{\tt 普及-} \color{#FF8C00}{\tt 普及-}
P1926 小书童——刷题大军 01背包变形 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P1802 5倍经验日 01背包变形 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P1734 最大约数和 01背包变形 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P8742 [蓝桥杯 2021 省 AB] 砝码称重 01背包变形 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P2392 kkksc03考前临时抱佛脚 01背包变形 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P1466 [USACO2.2]集合 Subset Sums 01背包变形 \color{#FFD700}{普及/提高-} \color{#FF8C00}{普及-}
P2370 yyy2015c01 的 U 盘 01背包变形 \color{#FFD700}{普及/提高-} \color{#FFD700}{普及/提高-}
CF294B Shaass and Bookshelf 01背包变形 \color{#32CD32}{普及+/提高} \color{#FFD700}{普及/提高-}
CF19B Checkout Assistant 01背包变形 \color{#0000FF}{提高+/省选-} \color{#FFD700}{普及/提高-}
P4141 消失之物 01背包变形 \color{#FFD700}{普及/提高-} \color{#32CD32}{普及+/提高}
P1156 垃圾陷阱 01背包变形 \color{#32CD32}{普及+/提高} \color{#32CD32}{普及+/提高}
P1507 NASA的食物计划 二维01背包 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P1910 L国的战斗之间谍 二维01背包 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P1855 榨取kkksc03 二维01背包稍微变形 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-} \color{#FFD700}{普及/提高-}
P1877 [HAOI2012]音量调节 二维01背包变形 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P1509 找啊找啊找GF 二维01背包变形 \color{#FFD700}{普及/提高-} \color{#FFD700}{普及/提高-}
P3985 不开心的金明 二维01背包变形 \color{#32CD32}{普及+/提高} \color{#FFD700}{普及/提高-}
P1455 搭配购买 01背包+并查集 \color{#FFD700}{普及/提高-} \color{#FFD700}{普及/提高-}
P1941 飞扬的小鸟 01背包变形+完全背包变形 \color{#32CD32}{普及+/提高} \color{#32CD32}{普及+/提高}
P2170 选学霸 01背包变形+并查集 \color{#32CD32}{普及+/提高} \color{#32CD32}{普及+/提高}
P1858 多人背包 01背包 k 优解变形 \color{#0000FF}{提高+/省选-} \color{#32CD32}{普及+/提高}
P1616 疯狂的采药 完全背包 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P2722 [USACO3.1]总分 Score Inflation 完全背包 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P1679 神奇的四次方数 完全背包变形 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P1832 A+B Problem(再升级) 完全背包变形 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P1853 投资的最大效益 完全背包变形 \color{#FFD700}{普及/提高-} \color{#FF8C00}{普及-}
CF189A Cut Ribbon 完全背包变形 \color{#FFD700}{普及/提高-} \color{#FF8C00}{普及-}
CF417A Elimination 完全背包变形 \color{#FFD700}{普及/提高-} \color{#FF8C00}{普及-}
P2918 [USACO08NOV]Buying Hay S 完全背包变形 \color{#FFD700}{普及/提高-} \color{#FFD700}{普及/提高-}
P5662 纪念品 完全背包变形 \color{#32CD32}{普及+/提高} \color{#FFD700}{普及/提高-}
P5020 [NOIP2018 提高组] 货币系统 完全背包变形 \color{#32CD32}{普及+/提高} \color{#32CD32}{普及+/提高}
P2347 砝码称重 多重背包变形 \color{#FF8C00}{普及-} \color{#FF8C00}{普及-}
P6771 [USACO05MAR]Space Elevator 太空电梯 多重背包变形 \color{#FFD700}{普及/提高-} \color{#FFD700}{普及/提高-}
P5365 [SNOI2017]英雄联盟 多重背包变形 \color{#32CD32}{普及+/提高} \color{#FFD700}{普及/提高-}
P1776 宝物筛选 多重背包二进制优化 \color{#32CD32}{普及+/提高} \color{#FFD700}{普及/提高-}
P2851 [USACO06DEC]The Fewest Coins G 多重背包+完全背包 \color{#0000FF}{提高+/省选-} \color{#FFD700}{普及/提高-}
P1833 樱花 混合背包 \color{#32CD32}{普及+/提高} \color{#FFD700}{普及/提高-}
P1782 旅行商的背包 混合背包二进制优化+完全背包+卡常 \color{#0000FF}{提高+/省选-} \color{#32CD32}{普及+/提高}
P1757 通天之分组背包 分组背包 \color{#FF8C00}{普及-} \color{#FFD700}{普及/提高-} \color{#32CD32}{普及+/提高}
P5322 [BJOI2019]排兵布阵 分组背包变形 \color{#0000FF}{提高+/省选-} \color{#FFD700}{普及/提高-}
P1064 金明的预算方案 有依赖的背包 \color{#32CD32}{普及+/提高} \color{#FFD700}{普及/提高-} \color{#FFD700}{普及/提高-}
P2904 [USACO08MAR]River Crossing S 背包思想 \color{#FFD700}{普及/提高-} \color{#FFD700}{普及/提高-}

最后:

1.如题目难度不符合实际,补充的题目或修改建议欢迎私信。

2.这个题单的题应该算比较简单,以后再写一个难一点的。

3.写题单不易,能不能帮忙收藏一下啊。


  1. P1048 - [NOIP 2005 普及组] 采药
  2. P2871 - [USACO07DEC] Charm Bracelet S
  3. P1049 - [NOIP 2001 普及组] 装箱问题
  4. P1060 - [NOIP 2006 普及组] 开心的金明
  5. P1164 - 小 A 点菜
  6. P1510 - 精卫填海
  7. P8742 - [蓝桥杯 2021 省 AB] 砝码称重
  8. P2639 - [USACO09OCT] Bessie's Weight Problem G
  9. P2925 - [USACO08DEC] Hay For Sale S
  10. P1802 - 5 倍经验日
  11. P1734 - 最大约数和
  12. P1926 - 小书童——刷题大军
  13. P2392 - kkksc03考前临时抱佛脚
  14. P1507 - NASA的食物计划
  15. P1910 - L 国的战斗之间谍
  16. P1855 - 榨取kkksc03
  17. P1877 - [HAOI2012] 音量调节
  18. P1616 - 疯狂的采药
  19. P2722 - [USACO3.1] 总分 Score Inflation
  20. P1679 - 神奇的四次方数
  21. P1832 - A+B Problem(再升级)
  22. P2347 - [NOIP 1996 提高组] 砝码称重
  23. P1757 - 通天之分组背包
  24. P1466 - [USACO2.2] Subset Sums
  25. P1853 - [NWERC 2004] 投资的最大效益
  26. P1509 - 找啊找啊找GF
  27. P1455 - 搭配购买
  28. P2370 - yyy2015c01 的 U 盘
  29. P2918 - [USACO08NOV] Buying Hay S
  30. P2904 - [USACO08MAR] River Crossing S
  31. P6771 - [USACO05MAR] Space Elevator 太空电梯
  32. CF189A - Cut Ribbon
  33. CF417A - Elimination
  34. P5662 - [CSP-J 2019] 纪念品
  35. P1064 - [NOIP 2006 提高组] 金明的预算方案
  36. P1833 - 樱花
  37. P1941 - [NOIP 2014 提高组] 飞扬的小鸟
  38. P2170 - 选学霸
  39. P3985 - 不开心的金明
  40. P5365 - [SNOI2017] 英雄联盟
  41. CF294B - Shaass and Bookshelf
  42. P1776 - 宝物筛选
  43. P5020 - [NOIP 2018 提高组] 货币系统
  44. P1782 - 旅行商的背包
  45. P1858 - 多人背包
  46. P4141 - 消失之物
  47. P5322 - [BJOI2019] 排兵布阵
  48. CF19B - Checkout Assistant
  49. P2851 - [USACO06DEC] The Fewest Coins G
  50. P1156 - [USACO01OPEN] 垃圾陷阱