学习目标

• 能独立写清状态含义、合法转移与初始化，而不是只背代码模板。
• 能实现本题的 C++17 动态规划，并解释为什么循环顺序满足依赖关系。
• 能用边界与反例检查「只计算恰好 H 会漏掉必须超额购买的最优解；把所有超过目标的重量统一封顶即可。」这一常见错误。

前置知识与环境

先阅读 第 14 章对应小节，并确保本机可使用 C++17。首次运行可执行 make doctor；Windows 未安装 Make 时可在仓库根使用 pnpm 命令。

题目

有 n 家供应商，每家出售固定重量、固定价格的一包干草，且可购买任意多包。至少需要 H 单位干草，求达到或超过 H 的最小费用。

输入格式

第一行 n H，随后 n 行为 cost weight。

输出格式

输出购买至少 H 单位干草的最小费用。

数据范围

n ≤ 100，H ≤ 50000，每包重量和费用均不超过 5000。

样例输入

2 15
10 6
14 10

样例输出

24

做题前先填状态卡

问题	本题答案
状态	dp[x] 表示获得“封顶为 H 的重量 x”所需最小费用。
选择	再购买某供应商的一包。
转移	dp[min(H,x+weight)]=min(dp[min(...)],dp[x]+cost)。
初值	dp[0]=0，其他状态为正无穷。
顺序	重量状态从小到大，允许同一包型重复使用。
答案	dp[H]。

不要急着写循环。先用一个最小输入手算状态表，再检查每个右侧依赖是否已经计算；如果依赖来自“当前物品的新状态”，还要说明这是否意味着允许重复选择。

复杂度目标

时间 O(nH)，空间 O(H)。

测试设计提示

公开测试共 20 组、总分 100 分，覆盖样例、最小规模、单行/单列或单元素、不可达/全负/重复值等题型边界，以及容易暴露循环方向和初始化错误的回归输入。测试只接受标准输出；调试信息请写到标准错误。

运行与评分

cd labs/chapter-14/exercise/E-14-30-buying-hay
make run

# 没有 Make 时，在仓库根执行
pnpm lab:run -- labs/chapter-14/exercise/E-14-30-buying-hay

# 作者与 CI 的严格检查
pnpm lab:verify -- labs/chapter-14/exercise/E-14-30-buying-hay

完成清单

• student/main.cpp 已替换占位逻辑，并能通过编译。
• 20 个公开测试全部通过，严格评分为 100/100。
• 能口头解释状态、转移、初始化、遍历顺序和复杂度。
• 主动构造了至少一个会击穿常见错误的额外输入。

思考与复盘

1. 如果改用另一种状态定义，转移和循环顺序会怎样变化？
2. 哪个最小反例最容易暴露「只计算恰好 H 会漏掉必须超额购买的最优解；把所有超过目标的重量统一封顶即可。」？
3. 能否压缩空间？压缩后会不会覆盖本轮仍需读取的状态？

题目来源与课程化说明

核心问题参考 洛谷 P2918。本 Lab 为课程标准输入/输出环境重新表述题面，并独立编写参考实现与测试数据；不复制第三方题解、代码或隐藏测试。