贪心算法

抓住最好的，继续往前

一个[[greedy-algorithm|贪心算法]]一步一步地构建解，而每一步它都做出*此刻*看起来最好的选择——最大的硬币、最早结束的会议、最便宜的边——而且从不反悔。它既不向前看，也不往回退。它是全部计算中最乐观的策略：它只是一味相信，一连串局部最优的选择，加起来就能凑成一个全局最优的答案。

当这份信任站得住脚时，回报是巨大的。贪心算法通常很短、通常很快——往往就是*把输入排个序，再扫一遍*——而且它完全绕开了动态规划那套笨重的机器。你会遇到两个你已经认识、却正是建立在贪心选择之上的结构：最小生成树（总是加入最便宜的安全边）和 Dijkstra 的最短路径（总是下一个敲定离起点最近的未完成节点）。

贪心何时奏效：区间调度

这是经典的胜局。你有一间会议室和一堆会议，每场都有开始与结束时间；你想塞进尽可能多、互不重叠的会议。奏效的贪心规则出人意料：*在还塞得下的会议里，永远挑结束得最早的那一场。*早早结束，就给它之后的一切留下了最多空间。按结束时间排序，然后扫一遍。

#include <vector>
#include <algorithm>
struct Meeting { int start, end; };

int maxMeetings(std::vector<Meeting> v) {
    // Greedy: sort by EARLIEST finishing time.
    std::sort(v.begin(), v.end(),
              [](const Meeting& a, const Meeting& b){ return a.end < b.end; });

    int count = 0, lastEnd = -1;
    for (const Meeting& m : v) {
        if (m.start >= lastEnd) {   // doesn't overlap what we kept
            count++;
            lastEnd = m.end;        // commit; never reconsider
        }
    }
    return count;
}

为什么这能*被证明*是最优的？直觉是一个交换论证：取任意一个最佳的安排，看它的第一场会议。如果它结束得不如贪心首选那么早，你就可以把贪心那场换进去——它结束得不会更晚，所以不会破坏它之后的任何安排。沿着序列不断重复这个交换，你就把一个最优安排变成了贪心的那个，且一场会议都没少。于是贪心至少不比最佳差——也就是说，它*就是*最佳。

贪心何时失败：硬币反例

现在来看陷阱。要用最少的硬币凑出一个金额，显而易见的贪心规则是*抓住塞得下的最大面额，重复。*用日常面额 {1, 5, 10, 25} 它总能行。但换一套硬币它就崩了。假设你的硬币是 {1, 3, 4}，而你必须凑出 6：

Coins available: { 1, 3, 4 }     Target: 6

GREEDY (take biggest first):        OPTIMAL:
    take 4   ->  remaining 2            take 3   ->  remaining 3
    take 1   ->  remaining 1            take 3   ->  remaining 0
    take 1   ->  remaining 0
    -----------------------             -----------------------
    4 + 1 + 1  =  THREE coins           3 + 3  =  TWO coins   (better!)

第二个胜局：霍夫曼编码

贪心再露锋芒的一处：霍夫曼编码，是许多文件压缩背后的思路。你想给高频字母短的位码、给罕见字母长的位码。贪心的招法：反复取出频率最低的两个条目，合并成一个频率为两者之和的节点，再放回去。如此进行，直到只剩一棵树——这棵树给出可证明为最优的编码。

1. 把每个符号连同它的频率，放进一个最小优先队列（频率最小的在顶）。
2. 弹出最小的两个。造一个新节点，其频率为两者之和，其左右子节点正是这两个。
3. 把这个合并后的节点压回队列。
4. 重复到只剩一个节点——霍夫曼树的根。左走 0、右走 1，就给了每个符号它的编码。

留意它的引擎：一个由最小堆支撑的优先队列，正是上一级台阶里的那个结构。贪心算法时时刻刻倚赖排序和优先队列，因为这两者都能廉价地回答「此刻最好的选择是什么？」——而这正是贪心唯一会问的问题。