背包入门题单

根据洛谷“疯狂的背包问题”题单整理，从 0/1、完全、多重背包模板逐步练习复合模型、方案恢复与综合应用。

0 / 0 已完成

背包入门题单

洛谷原题单

这份题单先用 19 道模板题对比不同背包模型，再按原题单顺序完成 31 道应用题。学习时重点记录状态含义、容量枚举方向、初值和答案落点，而不是只背转移式。

一、基础模型模板

先掌握三种基本物品限制，以及“求最优值、判断可行、统计方案”三类常见目标。

0/1 背包

完全背包

多重背包

二、复合模型模板

在基本模型上增加物品类型、费用维度、分组或依赖关系，练习先辨认限制再选择转移方式。

三、方案恢复与最优方案计数

这一组不再只求最优值，还要恢复方案或统计最优方案，注意区分不可达状态与值为零的合法状态。

四、经典模型练习

以下练习保持洛谷原题单顺序。先把 0/1、完全背包和“恰好装满”状态练熟。

五、状态设计与模型变形

这一组把背包状态用于可行性、计数、二维费用、分组和数论对象，重点练习从题意识别“物品、容量、选择限制”。

六、综合应用与优化

最后一组综合方案计数、状态反推、依赖关系和多重背包优化。遇到陌生题面时，先尝试把状态写成“处理前若干物品、容量为某值时的答案”。

复盘要求

每完成一道题，至少记录下面四项：

text
物品和容量分别是什么：
每件物品能选几次：
状态定义与初始化：
容量为什么正序或倒序枚举：

当题目要求可行性、方案数、恰好装满或输出方案时，再单独写清楚状态值的语义，避免沿用“最大价值”模板造成初始化错误。