Appearance
24. 先拿再说（贪心）
知识点：贪心（greedy）—— 每一步都选"眼前最好的"；以及它什么时候会失灵
项目：售货机找零钱 + 贪心的"反例"
故事开场：售货机的找零
自动售货机的找零程序坏了，老板请你修。规则很简单：
顾客付了钱，机器要找出
47元。硬币只有25、10、5、1元四种。 要求：硬币数量最少。
你盯着 47 元想了半天。突然，一个"急性子"办法蹦了出来：
每次都拿最大的硬币！
- 47 元：先拿 25（剩 22）
- 22 元：还能拿 25 吗？不能。拿 10（剩 12）
- 12 元：再拿 10（剩 2）
- 2 元：拿 1（剩 1），再拿 1（剩 0）
结果：25 + 10 + 10 + 1 + 1，5 枚硬币。
"还有没有比 5 枚更少的？"你试着换别的组合……怎么凑都是 5 枚！ "每次都拿最大的"，在 25/10/5/1 的硬币下，就是最优的。
老板满意地点点头："这叫贪心算法——每一步都贪婪地拿眼前最大的。 修好它！"
笨办法先行：贪心好写，可它总是对的吗？
贪心算法太好写了，你三下五除二就写完了：
ts
// 贪心找零：每次都拿最大的硬币（coins 从大到小排好）
function greedyChange(amount: number, coins: number[]): number[] {
const result: number[] = []
for (let i = 0; i < coins.length; i++) {
while (amount >= coins[i]) { // 能拿几枚拿几枚
result.push(coins[i])
amount = amount - coins[i]
}
}
return result
}
console.log(greedyChange(47, [25, 10, 5, 1]))输出：
[25, 10, 10, 1, 1]5 枚，完美。可这时候，老师走进来说：
"我改了一下硬币设计——现在只有 1、3、4 元三种。顾客要凑 6 元， 用你的贪心算法，找多少枚？"
你信心满满地运行：
ts
const coins2 = [4, 3, 1] // 从大到小排好
console.log(greedyChange(6, coins2))输出：
[4, 1, 1]"4+1+1，3 枚。"你宣布答案。
老师笑了："3+3 呢？只要 2 枚！"
你愣住了：贪心算法给出的不是最优解！
引出知识点：贪心——眼前最好 ≠ 全局最好
问题出在哪？
- 贪心：每次都拿"眼前最大的硬币"——4 元拿走了，剩下的 2 元 只能用 1+1 凑，共 3 枚
- 最优：忍住不拿 4 元，拿两张 3 元——2 枚
贪心的毛病是目光短浅：它从不"忍住眼前的小便宜"，也从不回头 （不像回溯会后悔）。眼前最好的选择，可能堵死了后面更优的路。
那贪心算法还有用吗？当然有用！在"眼前最优 = 全局最优"成立的问题上， 贪心又快又简单——找零（25/10/5/1）、活动安排、搭积木……都是贪心的天下。
判断能不能用贪心，有一个土办法：试着找一个"反例"—— 贪心给出的答案不是最优的例子。找到了，就不能用贪心；找不到， 贪心大概率是对的（严格证明需要数学，先学会找反例）。
回溯：所有路都试（稳，但慢） 贪心：只走眼前最好的一条（快，但可能错） 好算法 = 在"快"和"稳"之间选对的那一个。
动手实现：活动安排——贪心的"主场"
有一个贪心一定能赢的问题：活动安排。
文化节要借用一间教室，很多社团都想用，每个活动有开始时间和结束时间。 教室一次只能办一个活动。怎么选，才能安排最多的活动？
贪心的答案：每次都选"结束最早"的活动（而不是开始最早、也不是 用时最短）——因为结束得早，给后面的活动留的空间最大！
ts
// 活动列表：开始时间、结束时间（单位：小时）
// （已经按结束时间从早到晚排好了；没排好的话，先用插入排序排一下）
const activities = [
{ name: "合唱团", start: 9, end: 11 },
{ name: "围棋社", start: 10, end: 12 },
{ name: "编程社", start: 11, end: 13 },
{ name: "舞蹈社", start: 12, end: 14 },
{ name: "美术社", start: 13, end: 15 },
{ name: "足球队", start: 15, end: 17 },
]
const picked: string[] = []
let freeAt = 0 // 教室最早什么时候空出来
for (let i = 0; i < activities.length; i++) {
const act = activities[i]
if (act.start >= freeAt) { // 教室空着，能用！
picked.push(act.name)
freeAt = act.end // 这个活动结束，教室才空
}
}
console.log("安排的活动：" + picked.join("、"))输出：
安排的活动：合唱团、编程社、美术社、足球队4 个活动！走一遍你就明白贪心为什么对：
- 合唱团 9~11 点：教室空着，安排！教室 11 点才空
- 围棋社 10 点开始？教室还占着 → 跳过
- 编程社 11 点开始：正好！安排！教室 13 点才空
- 舞蹈社 12 点？占着 → 跳过
- 美术社 13 点：安排！教室 15 点空
- 足球队 15 点：安排！一共 4 个！
再想想："结束最早"为什么是关键？ 因为选它，教室最早空出来， 给后面的活动留了最大的余地——这就是"眼前最优 = 全局最优"的直觉。 （不信试试选"开始最早"的围棋社，或者"用时最短"的活动，数一数 能安排几个，都比 4 少！）
跑起来：找零 vs 最优，一眼看穿
回到找零问题。写一个"反例探测器"：用回溯把所有凑法都试一遍 （第 23 章的思路），看看贪心到底什么时候翻车：
ts
// 用回溯找"最少硬币"：把所有凑法都试一遍
function minCoinsBrute(amount: number): number {
if (amount === 0) {
return 0 // 不用找了
}
let best = Infinity // 先假设"无穷多枚"
for (let i = 0; i < coins2.length; i++) {
if (amount >= coins2[i]) {
const rest = minCoinsBrute(amount - coins2[i]) + 1
if (rest < best) {
best = rest // 记住更少的那条路
}
}
}
return best
}
console.log("凑 6 元：贪心 " + greedyChange(6, coins2).length + " 枚，" +
"回溯最优 " + minCoinsBrute(6) + " 枚")输出：
凑 6 元：贪心 3 枚，回溯最优 2 枚看，反例实锤了：同样的硬币（1/3/4），贪心 3 枚，最优 2 枚。
（Infinity 是"无穷大"——表示"还没找到凑法"。那 25/10/5/1 这种 "整齐"的币制为什么贪心就成立？因为现实的钱币是设计过的： 人民币 1/5/10/20/50/100，每种都是前一种的 2~2.5 倍，这种 "约数链条"让贪心每一步都不会后悔。币制整齐 → 贪心可信； 币制刁钻 → 贪心翻车。）
小挑战
- 手动反例：硬币 1/3/4，用贪心凑 8 元，得到几枚？最优是几枚？ （提示：贪心是 4+4？不，4+4 恰好也是最优——那凑 9 元呢？ 贪心 4+4+1 = 3 枚，最优 3+3+3 = 3 枚……咦，凑 10 元呢？ 贪心 4+4+1+1 = 4 枚，最优 3+3+4 = 3 枚！反例在这里！）
- 活动安排反着来：把活动安排改成"每次选开始最早的"， 自己造一个反例，证明它不行（提示：一个 9 点开始、一直用到 下午 5 点的活动，会把所有其他活动都挤掉——可它"开始最早"）。
- 反例探测器：用
minCoinsBrute测试 25/10/5/1 的币制下， 从 1 到 50 元，贪心是不是永远最优（提示：循环跑 50 次，比较greedyChange(i, [25,10,5,1]).length和minCoinsBrute(i)）。
课后练习
第 1 题（动手题）：38 元怎么找
用 25/10/5/1 的币制，贪心找 38 元零钱。先用手算，再写程序验证。
参考答案（点开查看）
ts
console.log(greedyChange(38, [25, 10, 5, 1]))
// [25, 10, 1, 1, 1]38 = 25 + 10 + 1 + 1 + 1，5 枚。
试试别的组合：10×3 + 5 + 1×3 = 7 枚；25 + 5 + 5 + 1×3 = 6 枚。 都 ≥ 5 枚——25/10/5/1 的币制下贪心就是最优。
第 2 题（思考题）：找反例
下面每个说法，贪心都"看起来"很有道理。试着各找一个反例：
① "凑钱当然先拿最便宜的"（要凑 8 元，纸币有 1、4、5、6 元） ② "装箱当然先放最大的"（箱子长 8，物品长 5、4、4）
参考答案（点开查看）
① 反例：先拿最便宜的（1 元）→ 1+1+1+1+1+1+1+1 = 8 张！ 最优是 4+4 = 2 张。"最便宜"贪心一败涂地。
② 反例：先放最大的 5，剩 3，装不下 4 → 只装了 5； 最优是先放 4、再放 4，装得满满当当 8！ "最大"不等于"最合适"——放得满才装得多。
找反例是检验贪心最重要的手艺——多造几个例子试试，别信直觉。
第 3 题（思考题）：贪心、回溯、动态规划
我们见过三种"决策"方法了：贪心（眼前最好）、回溯（全试一遍）、 动态规划（下一章！）。填一填：
| 方法 | 会不会后悔 | 保证最优吗 | 快还是慢 |
|---|---|---|---|
| 贪心 | ？ | ？ | ？ |
| 回溯 | ？ | ？ | ？ |
参考答案（点开查看）
| 方法 | 会不会后悔 | 保证最优吗 | 快还是慢 |
|---|---|---|---|
| 贪心 | 不后悔（永不回头） | 不一定（要找反例） | 快（O(n) 级别） |
| 回溯 | 会后悔（走错就退） | 一定（全试一遍） | 慢（指数级） |
贪心快但可能错，回溯稳但太慢——有没有又快又稳的？ 下一章的主角：动态规划。它把"重复算过的问题"记下来， 让回溯不再重复劳动——又快又稳。
下一课预告：爬楼梯。一次上 1 级或 2 级，10 级台阶有几种走法？ 用回溯硬算？1 级 1 种，2 级 2 种，3 级 3 种……可算到 40 级时， 程序开始"卡"了——它把同一个楼梯算了一遍又一遍！ 如果算过的答案都记下来呢？