# 贪心算法

贪心算法在每一步只做当前看来最好的选择，并且不撤回。它能否得到全局最优，取决于问题是否具有贪心选择性质和最优子结构；这两点需要证明，不能凭“每步都取最大或最小”假定。本页用找零钱和辗转相除说明贪心的写法与适用边界。子问题大量重叠、需要比较多个候选时，应改用[动态规划](/knowledge/cs/algorithms/dynamic-programming/)；沿一条路径不断缩小问题的递归写法见[递归](/knowledge/cs/algorithms/recursion/)。

## 定义

**贪心算法**在每一步都从当前候选集中选出按某个标准最优的一个，固定该选择，再在缩小后的问题上重复同一规则，直到问题解决。已经做过的选择不会被撤销，也不会为了照顾后续步骤而保留多个备选方案。

一次贪心求解要写清楚四件事：

* **候选集**：当前还能选哪些元素或动作。
* **选择规则**：用什么标准判断“当前最优”，例如面值最大、单位价值最高、结束时间最早。
* **可行性检查**：选入之后是否仍能构成可行解。
* **目标函数**：要最大化或最小化的量，例如硬币枚数、总价值、区间数量。

贪心可以写成循环，也可以写成递归；代码形式不决定它是不是贪心。判断标准是：每一步是否只保留一个选择，并且不再回头修改。

## 性质

### 贪心正确的条件

贪心只保证每一步局部最优，不自动保证全局最优。要说明一个贪心策略正确，通常需要证明两点：

1. **贪心选择性质**：存在一个全局最优解包含当前按规则选出的元素，因此可以先把这一步固定下来。
2. **最优子结构**：做出该选择后，剩余问题的最优解能与该选择拼成原问题的最优解。

常用证明方法是交换论证：假设某个最优解不含贪心选择，把它调整成含贪心选择的解，并说明目标值不会变差。调整过程必须对每一步都成立，只验证几个小例子不够。

> [!TIP]
> 先找反例，再写证明。若能在小规模输入上找到“贪心结果比最优解差”的例子，就说明策略不成立；找不到反例也不等于已经证明。

### 局部最优不等于全局最优

币值为1、3、4，要找6。贪心每一步取不超过余额的最大币值，得到 $4+1+1$，共3枚；最优解是 $3+3$，只需2枚。第一步选4在当下最优，却让剩下的2只能由两个1凑出。

这个反例说明：贪心的正确性依赖具体的候选结构和目标，不能把“每步取最大”或“每步取最小”直接当作算法。

### 与分治、动态规划的对比

| 策略   | 子问题关系      | 是否保存子问题答案 | 是否允许回退  |
| ---- | ---------- | --------- | ------- |
| 贪心   | 每一步只剩一个子问题 | 不保存       | 不回头     |
| 分治   | 子问题相互独立    | 通常不保存     | 通过递归返回  |
| 动态规划 | 子问题大量重叠    | 保存每个状态    | 按依赖顺序复用 |

分治把问题分成多个独立子问题；动态规划在子问题重叠时保存答案；贪心则沿着一条路径一直走到底。子问题重叠时继续用贪心，可能错过需要比较多个候选才能得到的最优解。

### 代价

贪心的运行时间由“步数 × 单步选择代价”决定。若每步都要排序或扫描全部候选，单步代价会上升；很多贪心算法先用 $O(n\log n)$ 排序，再线性扫描。贪心的空间开销通常很小，但正确性证明往往比实现本身更花时间。

## 例子

**找零钱：每次取不超过余额的最大币值**

币值为25、10、5、1分。对余额`T`，每次取不超过`T`的最大币值，减去后继续，直到`T`为0。

```python title="coin-change-greedy.py"
v = [25, 10, 5, 1]
n = [0, 0, 0, 0]


def change():
    T_str = input("要找给顾客的零钱，单位：分：")
    T = int(T_str)
    greedy(T)
    for i in range(len(v)):
        print("要找给顾客", v[i], "分的硬币：", n[i])
    s = 0
    for i in n:
        s = s + i
    print("找给顾客的硬币数最少为：", s)


def greedy(T):
    if T == 0:
        return
    elif T >= v[0]:
        T = T - v[0]
        n[0] = n[0] + 1
        greedy(T)
    elif v[0] > T >= v[1]:
        T = T - v[1]
        n[1] = n[1] + 1
        greedy(T)
    elif v[1] > T >= v[2]:
        T = T - v[2]
        n[2] = n[2] + 1
        greedy(T)
    else:
        T = T - v[3]
        n[3] = n[3] + 1
        greedy(T)


if __name__ == "__main__":
    change()
```

`n[i]` 记录第`i`种币值用了多少枚。对63分，程序依次取25、25、10、1、1、1，共6枚。对25、10、5、1这套币值，贪心恰好最优；换一套币值就未必，见上面的1、3、4反例。

> [!NOTE]
> 这里用递归写只是为了按“取一枚、余额减少、继续取”的顺序展开。每次调用只走一个分支，没有回溯，改成`while T > 0`的循环结果相同。

**最大公约数：辗转相除**

辗转相除每一步都把“求 $x$ 与 $y$ 的最大公约数”换成“求 $b$ 与 $a \bmod b$ 的最大公约数”，其中 $a\ge b$。余数严格小于除数，所以问题规模一定减小。

1. **令 $a\ge b$**

   比较两个正整数，较大的记为 $a$，较小的记为 $b$。

2. **检查整除**

   若 $a \bmod b=0$，则 $b$ 就是最大公约数，直接返回。

3. **缩小问题**

   否则用 $(b,\,a\bmod b)$ 继续，直到出现整除。

```python title="gcd.py"
def main():
    x_str = input("请输入正整数x的值：")
    x = int(x_str)
    y_str = input("请输入正整数y的值：")
    y = int(y_str)
    print(x, "和", y, "的最大公约数是：", GCD(x, y))


def GCD(x, y):
    if x > y:
        a = x
        b = y
    else:
        a = y
        b = x
    if a % b == 0:
        return b
    return GCD(a % b, b)


if __name__ == "__main__":
    main()
```

依据是 $\gcd(a,b)=\gcd(b,a\bmod b)$：任何同时整除 $a$ 和 $b$ 的数也整除 $a\bmod b$，反之亦然，所以两对数的公约数集合相同，最大公约数也相同。`GCD(48, 18)` 依次计算 $(48,18)\to(18,12)\to(12,6)$，返回6。

> [!NOTE]
> 辗转相除每一步只有一个确定的化简，没有在多个候选之间比较，严格说更接近“不断缩小问题”的递归化简；把它和贪心放在一起，是因为两者都沿一条路径推进、不保存所有子问题的答案。

## 交互探索

用面额 $1$、$3$、$4$ 的硬币找零，比较逐次取最大面额与最少硬币的方案。

交互演示：每次拿最大面额一定最省硬币吗？。比较贪心找零与最少硬币方案。 请在站点操作演示。

## 练习

1. 币值为25、10、5、1分，要找63分。按“每次取不超过余额的最大币值”的贪心策略，共使用 \_\_\_\_\_\_（count） 枚硬币。

   答案：6

   依次取25、25、10、1、1、1，合计 $25+25+10+1+1+1=63$，共6枚。

2. 币值为1、3、4，要找6。贪心策略先取4，最后得到3枚硬币；最优解需要 \_\_\_\_\_\_（min） 枚。

   答案：2

   最优解是 $3+3$，只需2枚。贪心先取4后，余额2只能用两个1凑出。

3. `GCD(48, 18)` 的返回值是 \_\_\_\_\_\_（gcd）。

   答案：6

   $(48,18)\to(18,12)\to(12,6)$，$12\bmod 6=0$，返回6。

4. 下列哪一项最能说明一个贪心策略是正确的？

   * A.  每一步的局部最优选择都能被某个全局最优解包含，并且剩余子问题仍具有最优子结构
   * B.  每一步都取了当前候选中的最大值
   * C.  算法用递归实现，并且没有回溯
   * D.  在小规模输入上运行结果与暴力枚举一致

   答案：A

   贪心选择性质和最优子结构合起来才能保证局部选择可以扩展到全局最优。取最大值、递归实现和少量测试都不能替代证明。

5. 在币值为1、3、4、目标为6的例子中，贪心为什么没有得到最优解？

   * A.  第一步取4在当下最优，但剩余余额2只能由两个1凑出，而最优解完全不使用4
   * B.  贪心没有检查所有硬币的真伪
   * C.  目标6不是任何币值的整数倍
   * D.  贪心必须先排序，而代码没有排序

   答案：A

   局部最优的选择占用了余额，使后续只能用更小的币值补足。最优解 $3+3$ 在第一步没有取最大值，却减少了总枚数。