贪心算法（Greedy Algorithms）是什么，它们何时有效？

Question

IT Interview Practice · Accepted Answer

**贪心算法**在每一步都做出**局部最优选择**，希望这会导致全局最优。它简单快速，但仅当问题具有**贪心选择性质**和**最优子结构**时才正确。

## 核心思想

不要重新考虑过去的选择——提交最佳的即时选项并继续进行。

## 例子：标准硬币的硬币兑换

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

这对美国硬币是最优的，但对于集合 {1, 3, 4} **失败**，因为贪心对于 6 给出 4+1+1，而不是 3+3。

## 贪心何时有效

- **最优子结构：** 最优解包含最优的子解。
- **贪心选择性质：** 局部最优是全局最优的一部分。

有效的例子：Dijkstra、Kruskal/Prim (MST)、Huffman 编码、区间调度。

## 时间复杂度

通常很快——排序后通常为 O(n log n)。

## 陷阱

贪心**不总是正确的**。在相信它之前，请证明贪心选择性质或针对 brute-force/DP 基线进行测试。

## 为什么这很重要

当贪心适用时，它比 DP 或暴力法简单得多且速度快得多。

了解*何时*它是有效的——以及何时它悄悄地给出错误答案——是算法成熟度的标志。

许多基础图算法的核心是贪心的。

核心思想

例子：标准硬币的硬币兑换

相关问题

贪心何时有效

时间复杂度

陷阱

为什么这很重要