# 贪心算法与交换论证讲义

## 一、本节课到底在学什么

这节课最重要的并不是记住几个排序方法，而是学会回答：

> 为什么这样排序一定能得到最优答案？

我们要掌握三个内容：

1. 什么是贪心算法；
2. 什么叫“证明一个贪心策略正确”；
3. 怎样用交换论证完成证明。

本节课涉及三个典型问题：

- 区间调度：按照结束时间从早到晚选择；
- 最小化最大迟到时间：按照截止时间从早到晚安排；
- 奶牛玩杂技：按照“重量 + 力量”从小到大排列。

---

## 二、什么是贪心算法

贪心算法的想法是：

> 每一步都选择当前看起来最合适的方案，并且选定以后不再反悔。

例如，有很多门课程，但时间可能冲突。我们希望参加尽量多的课程。一个贪心想法是：每次选择结束最早、并且与已经选择的课程不冲突的课程。

但是，“看起来合理”不等于“一定正确”。

下面这些方法听起来也很合理：

- 每次选择时间最短的课程；
- 每次选择冲突最少的课程；
- 每次选择开始最早的课程。

它们却不一定能得到最优答案。

所以，设计出贪心策略后，不能只说：

- “我感觉这样最好”；
- “样例是对的”；
- “我试了几个数据都没问题”。

这些都不是数学证明。

---

## 三、证明到底是什么意思

### 1. 举例不是证明

一个策略在 10 个样例中都正确，只能说明目前还没有找到反例，不能说明它对所有数据都正确。

证明需要说明：

> 无论输入是什么，这个策略都不会比最优方案差。

### 2. 贪心证明的困难

贪心算法只考虑眼前的一步，而最优答案考虑的是整个方案。

因此我们要在二者之间搭一座桥：

> 从任意一个最优方案出发，把它逐渐改造成贪心方案，并保证修改过程中答案不会变差。

这就是交换论证。

---

## 四、交换论证的核心思想

可以把交换论证想成整理一支排错队伍。

假设最优方案的顺序和贪心规则不同。我们找到其中一对“排反了”的对象，将它们交换。如果能证明交换以后答案不会变差，那么交换后的方案仍然是最优方案。

继续交换，最终整个方案都会符合贪心规则。

于是我们证明了：

> 至少存在一个最优方案，它和贪心算法得到的方案一致。

### 标准证明模板

遇到贪心证明，可以尝试套用下面五步：

1. **写出贪心规则**：算法每一步选择什么？
2. **假设有一个最优方案**：把它记为 \(O\)。
3. **寻找不同之处**：找到 \(O\) 中第一个不符合贪心规则的位置，或找到一对顺序颠倒的相邻对象。
4. **进行交换**：把它们换成贪心要求的顺序。
5. **证明不会变差**：交换后仍然合法，并且目标值不变或更好。重复交换后，最优方案就变成了贪心方案。

最关键的是第 5 步。只说“交换一下”是不够的，必须说明：

- 交换后为什么仍然合法；
- 交换后为什么答案不会变差；
- 交换为什么可以不断进行并最终结束。

---

# 第一题：区间调度

## 五、问题描述

每个作业（或活动）都有：

- 开始时间 \(s_i\)；
- 结束时间 \(f_i\)。

同一时间只能做一个作业。目标是选择尽量多的互不冲突作业。

两个区间不冲突，是指前一个结束以后，后一个才开始。

## 六、正确的贪心策略

> 每次选择当前能够选择的、结束时间最早的作业。

实现方法：

1. 按结束时间从小到大排序；
2. 从左到右扫描；
3. 如果当前作业的开始时间不早于上一个已选作业的结束时间，就选择它。

排序复杂度是 \(O(n\log n)\)，扫描复杂度是 \(O(n)\)，总复杂度为：

\[
O(n\log n)
\]

## 七、为什么“结束最早”是正确的

设贪心算法首先选择的作业是 \(G\)。因为 \(G\) 结束得最早，所以对于其他任何作业 \(X\)，都有：

\[
f_G\le f_X
\]

现在考虑一个最优方案 \(O\)。

### 情况一：最优方案的第一个作业就是 \(G\)

那么贪心选择已经和最优方案一致，不需要修改。

### 情况二：最优方案的第一个作业是 \(X\)，不是 \(G\)

把最优方案中的 \(X\) 替换成 \(G\)。

因为 \(G\) 的结束时间不晚于 \(X\)，所以原来能排在 \(X\) 后面的所有作业，也一定能排在 \(G\) 后面。

因此：

- 替换后的方案仍然合法；
- 作业数量没有减少；
- 新方案仍然是最优方案；
- 新方案的第一个选择变成了贪心选择 \(G\)。

接下来，对剩下的作业重复同样的论证，最终可以得到一个完全符合贪心算法的最优方案。

所以，“选择结束时间最早的作业”是安全的。

## 八、孩子可以怎样口头回答

> 假设有一个最优方案，它的第一个作业不是结束最早的作业。我用结束最早的作业替换它。因为新作业结束得更早，所以原来后面的作业仍然都能安排，作业总数不会减少。因此一定存在一个以结束最早作业开头的最优方案。对剩余作业重复这个过程，就能证明贪心算法正确。

## 九、容易答错的地方

错误说法：

> 结束越早，留给后面的时间越多，所以一定正确。

这句话只表达了直觉，还不算完整证明。

应当补充：

> 将任意最优方案的第一个作业替换为结束最早的作业，后面的安排仍然合法，作业数量也不减少。

“替换最优方案”才是证明的关键。

---

# 第二题：使最大迟到时间最小

## 十、问题描述

每个作业 \(i\) 有：

- 处理时间 \(p_i\)：完成它需要多久；
- 截止时间 \(d_i\)：希望在什么时间前完成；
- 完成时间 \(C_i\)。

迟到时间定义为：

\[
L_i=\max(C_i-d_i,0)
\]

目标是让所有作业中最大的迟到时间尽量小：

\[
\min \max_i L_i
\]

## 十一、正确的贪心策略 EDF

> 按截止时间 \(d_i\) 从小到大安排作业。

EDF 是 Earliest Deadline First 的缩写，意思是“截止时间最早的作业优先”。

## 十二、什么叫“逆序”

如果相邻两个作业 \(A、B\) 的顺序是：

\[
A\rightarrow B
\]

但它们的截止时间满足：

\[
d_A>d_B
\]

就说明截止时间较晚的 \(A\) 反而排在截止时间较早的 \(B\) 前面。这叫一个逆序。

EDF 顺序中不存在这样的逆序。

## 十三、相邻交换证明

设在 \(A、B\) 开始前，已经过去了 \(t\) 时间。

原顺序为：

\[
A\rightarrow B
\]

其中：

\[
d_A>d_B
\]

原顺序下的完成时间是：

\[
C_A=t+p_A
\]

\[
C_B=t+p_A+p_B
\]

交换后，顺序变为：

\[
B\rightarrow A
\]

交换后的完成时间是：

\[
C'_B=t+p_B
\]

\[
C'_A=t+p_B+p_A
\]

注意：

- 交换后，截止时间更早的 \(B\) 提前完成；
- \(A\) 虽然推迟完成，但 \(A\) 的截止时间比 \(B\) 晚；
- 两个作业全部完成的时刻没有改变，仍然是 \(t+p_A+p_B\)；
- 其他作业的完成时间完全不受影响。

更严格地看，交换前这两个作业的最大“完成时间减截止时间”为：

\[
\max(t+p_A-d_A,\ t+p_A+p_B-d_B)
\]

因为 \(d_A>d_B\)，所以：

\[
t+p_A-d_A<t+p_A+p_B-d_B
\]

因此交换前两者的最大值就是：

\[
t+p_A+p_B-d_B
\]

交换后的两个值为：

\[
t+p_B-d_B
\]

和

\[
t+p_B+p_A-d_A
\]

它们都不大于交换前的最大值：

\[
t+p_B-d_B
\le
t+p_A+p_B-d_B
\]

并且：

\[
t+p_A+p_B-d_A
<
t+p_A+p_B-d_B
\]

所以，交换以后最大迟到时间不会增加。

只要方案中仍有逆序，就交换相邻的逆序作业。每次交换都不会让答案变差，而且逆序数量会减少。最终所有作业都按截止时间升序排列，也就是 EDF 顺序。

因此 EDF 是最优策略。

## 十四、孩子可以怎样口头回答

> 假设一个最优方案没有按截止时间升序排列，那么其中一定存在一对相邻逆序作业：前面的截止时间较晚，后面的截止时间较早。交换这两个作业后，截止时间早的作业提前完成；另一个作业虽然推迟，但它的截止时间更晚；其他作业的完成时间不变。通过比较可知，交换后最大迟到时间不会增加。不断消除逆序，最后得到 EDF 顺序，所以 EDF 是最优的。

---

# 第三题：奶牛玩杂技

## 十五、问题描述

每头奶牛有：

- 重量 \(W_i\)；
- 力量 \(S_i\)。

奶牛从上到下叠在一起。

某头奶牛的压扁指数等于：

\[
\text{它上方所有奶牛的总重量}-\text{它自己的力量}
\]

目标是安排奶牛的顺序，使所有奶牛中最大的压扁指数尽量小。

## 十六、正确的贪心策略

> 按照 \(W_i+S_i\) 从小到大排列奶牛。

这里的排列方向是从上到下：

- \(W_i+S_i\) 小的奶牛放上面；
- \(W_i+S_i\) 大的奶牛放下面。

## 十七、为什么要比较相邻两头奶牛

假设有两头相邻奶牛 \(A、B\)，它们上方其他奶牛的总重量为 \(T\)。

交换 \(A、B\) 时：

- 它们上方的总重量 \(T\) 不变；
- 它们下方所有奶牛承受的总重量不变；
- 因此只需要比较 \(A、B\) 自己的压扁指数。

这是相邻交换的好处：一次只研究两个对象，问题会简单很多。

## 十八、交换前后的压扁指数

### 顺序一：\(A\) 在上，\(B\) 在下

\[
\begin{array}{c}
A\\
B
\end{array}
\]

\(A\) 上方重量是 \(T\)，所以：

\[
R_A=T-S_A
\]

\(B\) 上方还有 \(A\) 的重量，所以：

\[
R_B=T+W_A-S_B
\]

这两头奶牛中的最大压扁指数为：

\[
M_{AB}
=
T+\max(-S_A,\ W_A-S_B)
\]

### 顺序二：\(B\) 在上，\(A\) 在下

\[
\begin{array}{c}
B\\
A
\end{array}
\]

此时：

\[
R'_B=T-S_B
\]

\[
R'_A=T+W_B-S_A
\]

两头奶牛中的最大压扁指数为：

\[
M_{BA}
=
T+\max(-S_B,\ W_B-S_A)
\]

## 十九、关键不等式

假设：

\[
W_A+S_A\le W_B+S_B
\]

把式子移项，可以得到：

\[
W_A-S_B\le W_B-S_A
\]

另外，因为奶牛的重量 \(W_B\ge 0\)，所以：

\[
-S_A\le W_B-S_A
\]

因此，顺序 \(A\rightarrow B\) 中需要比较的两个数：

\[
-S_A,\qquad W_A-S_B
\]

都不大于：

\[
W_B-S_A
\]

而 \(W_B-S_A\) 正是顺序 \(B\rightarrow A\) 的最大值候选之一。

所以：

\[
M_{AB}\le M_{BA}
\]

这说明：

> 当 \(W_A+S_A\le W_B+S_B\) 时，把 \(A\) 放在 \(B\) 上面不会更差。

反过来说，如果相邻奶牛满足：

\[
W_A+S_A>W_B+S_B
\]

说明这两头奶牛排反了，交换它们不会让答案变差。

不断交换所有排反的相邻奶牛，最后就会得到按 \(W_i+S_i\) 升序排列的顺序。

因此，这个贪心策略是正确的。

## 二十、孩子可以怎样口头回答

### 简短版

> 我们考虑两头相邻奶牛。交换它们不会影响其他奶牛，所以只需比较这两头。如果 \(W_A+S_A\le W_B+S_B\)，通过比较交换前后的压扁指数，可以证明 \(A\) 放在 \(B\) 上面不会更差。因此，如果相邻奶牛的“重量加力量”是逆序的，就可以交换。不断交换后会得到按 \(W_i+S_i\) 升序排列的最优方案。

### 完整版

> 设两头相邻奶牛 \(A、B\) 上方的总重量为 \(T\)。\(A\) 在上时，两头奶牛的压扁指数分别是 \(T-S_A\) 和 \(T+W_A-S_B\)；交换以后分别是 \(T-S_B\) 和 \(T+W_B-S_A\)。当 \(W_A+S_A\le W_B+S_B\) 时，有 \(W_A-S_B\le W_B-S_A\)，所以 \(A\) 在上不会使最大压扁指数更大。因此所有逆序相邻奶牛都可以交换，最终得到按 \(W_i+S_i\) 升序排列的最优方案。

---

# 二十一、三个证明有什么共同点

| 问题 | 贪心规则 | 修改最优方案的方法 | 为什么不会更差 |
|---|---|---|---|
| 区间调度 | 结束时间最早优先 | 替换最优方案的第一个区间 | 新区间结束更早，后面的区间仍能安排 |
| 最大迟到时间 | 截止时间升序 | 交换相邻逆序作业 | 截止时间早的提前，最大迟到时间不增加 |
| 奶牛玩杂技 | \(W_i+S_i\) 升序 | 交换相邻逆序奶牛 | 交换后两头奶牛的最大压扁指数不增加 |

共同套路是：

> 找到不同 → 局部交换或替换 → 证明不变差 → 重复修改 → 得到贪心方案。

---

# 二十二、常见错误

## 错误一：只描述算法，不证明

> 把所有对象排序，然后从头到尾处理。

这只说明“怎么做”，没有说明“为什么对”。

## 错误二：只说贪心选择看起来最好

> 结束早可以留出更多时间，所以选结束早的。

这只是直觉。应当补充怎样替换最优方案，以及替换后为什么仍然合法。

## 错误三：交换后只看其中一个对象

交换两个作业或两头奶牛后，必须比较二者的最大值，不能只看其中一个。

## 错误四：忘记说明其他对象不受影响

相邻交换证明中应当说明：

- 交换位置以前的对象没有变化；
- 交换位置以后的总处理时间或总重量没有变化；
- 所以其他对象的目标值不变。

## 错误五：证明了交换一次，却没说明最终能得到贪心顺序

还需要说明：

> 每次交换都会减少逆序数量；逆序数量不可能无限下降，所以过程一定结束；结束时就是贪心顺序。

---

# 二十三、看到新题时怎样寻找贪心规则

可以按照下面的思路尝试：

1. 先猜一种排序关键字，例如开始时间、结束时间、长度、截止时间、重量或力量；
2. 只取两个相邻对象 \(A、B\)；
3. 分别计算 \(A\rightarrow B\) 和 \(B\rightarrow A\) 的结果；
4. 比较在什么条件下一个顺序不比另一个差；
5. 把比较条件整理成一个排序式；
6. 再用相邻交换证明这个顺序正确。

奶牛题就是这样得到 \(W_i+S_i\) 的：

\[
W_A-S_B\le W_B-S_A
\]

移项后：

\[
W_A+S_A\le W_B+S_B
\]

排序关键字并不是凭空猜出来的，而是从交换前后的比较中推导出来的。

---

# 二十四、自测练习

## 练习 1

证明区间调度时，为什么可以用结束最早的区间替换最优方案的第一个区间？

## 练习 2

最大迟到时间问题中，如果相邻作业满足 \(d_A>d_B\)，为什么要交换它们？

## 练习 3

奶牛 \(A\) 的重量和力量为：

\[
W_A=3,\quad S_A=5
\]

奶牛 \(B\) 的重量和力量为：

\[
W_B=6,\quad S_B=4
\]

谁应该放在上面？

## 练习 4

为什么奶牛题交换相邻两头奶牛时，不需要重新计算其他奶牛的压扁指数？

## 练习 5

请补全交换论证的四个关键词：

> 最优方案 → 找到______ → 进行______ → 证明不会______ → 得到贪心方案。

---

# 二十五、自测答案

## 练习 1 答案

因为贪心选择的区间结束时间不晚于最优方案的第一个区间。替换后，原来能排在后面的区间仍然都能安排，区间数量也不减少。

## 练习 2 答案

因为截止时间更早的 \(B\) 应当优先。交换后 \(B\) 提前完成，\(A\) 虽然推迟但截止时间更晚；其他作业的完成时间不变。计算可以证明最大迟到时间不会增加。

## 练习 3 答案

\[
W_A+S_A=3+5=8
\]

\[
W_B+S_B=6+4=10
\]

因为 \(8<10\)，所以 \(A\) 应当放在 \(B\) 上面。

## 练习 4 答案

两头奶牛上方的总重量没有变化；它们下方的奶牛仍然承受 \(W_A+W_B\) 的总重量。因此交换只会改变 \(A、B\) 自己的压扁指数。

## 练习 5 答案

> 最优方案 → 找到**不同或逆序** → 进行**交换或替换** → 证明不会**变差** → 得到贪心方案。

---

# 二十六、最后需要真正记住的话

不要死记每一道题的公式，先记住这个证明骨架：

> 假设存在一个最优方案。如果它和贪心方案不同，就找到第一个不同的位置或一对相邻逆序对象，把它们交换成贪心要求的顺序。证明交换后方案仍然合法，而且答案不会变差。不断交换后，最优方案最终会变成贪心方案。因此贪心策略正确。

能够用自己的话讲清楚这段逻辑，就真正理解了交换论证。