贪心算法¶

约 1422 个字 36 行代码预计阅读时间 8 分钟

贪心算法（greedy algorithm）是一种「只看眼前，不管以后」的求解策略：在每一步都做出当前看来最好的选择，期望最终能得到全局最优解。它没有固定的算法框架，更像是一类「设计哲学」，常常以寥寥几行代码就解决看似复杂的问题。

贪心的诱惑在于：代码极短、思路直观、常数很小。危险也在于此——如果问题不具备「贪心选择性质」，局部最优就无法保证全局最优，写出来的代码跑得飞快但结果全错。因此贪心的难点从来不是写代码，而是证明这个贪心策略是对的。

什么样的问题能用贪心¶

一个问题能用贪心，通常需要同时满足下面两个性质：

贪心选择性质：全局最优解可以通过一系列局部最优选择构造出来。换句话说，做出某个局部最优选择后，剩下的子问题仍然可以独立求解，且不会破坏最优性。
最优子结构：原问题的最优解包含其子问题的最优解。这一点和动态规划共享，区别在于 DP 要遍历所有可能的子问题，而贪心只沿着一条「当前最好」的路径走下去。

能同时满足这两条的问题并不多。更常见的是「看上去像贪心，但贪心会错」的情形，这时候就要换成动态规划。

经典例题¶

活动选择¶

给定一组活动 \(\{(s_i, f_i)\}\)，每个活动有开始时间 \(s_i\) 和结束时间 \(f_i\)。要求从中选出尽可能多的互不冲突（时间段不重叠）的活动。

贪心策略：按结束时间 \(f_i\) 升序排序，依次考虑每个活动，能选就选。

int activity_selection(vector<pair<int,int>> acts) {
    sort(acts.begin(), acts.end(),
         [](const auto& a, const auto& b) { return a.second < b.second; });
    int cnt = 0, last_end = 0;
    for (auto [s, f] : acts) {
        if (s >= last_end) {
            ++cnt;
            last_end = f;
        }
    }
    return cnt;
}

正确性证明思路：假设最优解 \(\text{OPT}\) 的第一个活动不是结束时间最早的那个 \(a_1\)。将 \(\text{OPT}\) 的第一个活动替换为 \(a_1\) 后，新解仍然合法，且活动数不减少。由此不断替换下去，说明存在某个最优解以 \(a_1\) 起手。之后对剩下问题归纳即可。

如果改成按「开始时间早」或者「持续时间短」来排序，都能举出反例。这是贪心「一步错步步错」的典型例子。

区间覆盖¶

给定区间 \([0, T]\) 和一组子区间 \([l_i, r_i]\)，选最少的子区间把 \([0, T]\) 完整覆盖。

贪心策略：按左端点排序；每轮在所有左端点不超过当前覆盖终点的区间中，选右端点最大的一个；更新覆盖终点；重复直到覆盖 \(T\)。

复杂度 \(O(n\log n)\)，瓶颈在排序。

Huffman 编码¶

Huffman 编码解决的是「无前缀可变长编码」的最优性问题：给定每个字符的频率，构造出一棵二叉编码树，使得总编码长度 \(\sum f_i \cdot \text{depth}(i)\) 最小。

贪心策略：每次从所有待合并节点中取出两个频率最小的，合并成一个新节点，新节点的频率是二者之和，重新入堆。重复 \(n - 1\) 次。

int huffman_cost(vector<int>& freq) {
    priority_queue<int, vector<int>, greater<int>> pq(freq.begin(), freq.end());
    int cost = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        cost += a + b;
        pq.push(a + b);
    }
    return cost;
}

这里每次取两个最小元素，正是典型的「局部最优」。利用堆做优先队列，总复杂度 \(O(n\log n)\)。

最小生成树¶

Kruskal 和 Prim 都是贪心算法。前者按边权升序考察每条边，用并查集判断是否成环；后者从一个节点出发，每次向已有树中加入离它最近的未加入节点。具体实现见图算法中的最小生成树一节。

加油站问题¶

一辆车从起点出发沿环形公路行驶，每个加油站可以补充 \(\text{gas}_i\) 升油，从 \(i\) 到 \(i+1\) 要消耗 \(\text{cost}_i\) 升油。油箱无限大，初始空。问能否走完一圈；若能，返回任意一个合法起点。

贪心策略：累计当前油量 tank，一旦 tank < 0 说明从当前起点开始走不到这里——此时直接把候选起点更新为下一个位置，tank 清零。如果全局总和 sum(gas) >= sum(cost)，最终的候选起点一定合法。

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < (int)gas.size(); ++i) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank  += diff;
        if (tank < 0) {
            start = i + 1;
            tank  = 0;
        }
    }
    return total >= 0 ? start : -1;
}

只需要一次遍历，复杂度 \(O(n)\)。

贪心不对的典型陷阱¶

0/1 背包。一个经典反例是按「价值/重量比」贪心——对分数背包（可切分）是最优的，但对 0/1 背包就会错。因为 0/1 背包里一个物品是整体的，局部比率最大不一定让整体最优。正确解法是动态规划。

零钱兑换。硬币面值 {1, 3, 4}，要凑出 6 元，贪心会选 4 + 1 + 1（三枚），但最优是 3 + 3（两枚）。贪心在这类整数背包问题里普遍不可靠——只有面值满足特殊结构（如常见的 1, 5, 10, 25）时才恰好正确。

写贪心的一般流程¶

观察问题的结构，提出一个候选贪心策略。
尝试证明正确性：常用的是「交换论证」（exchange argument）——假设存在一个不以贪心选择起手的最优解，通过把它的第一个选择换成贪心的选择，证明新解同样合法且不变劣。
找不到证明，就去找反例；找不到反例，也不能就断定它是对的。严谨性和直觉缺一不可。
一旦证明存在缺口，立刻退回动态规划或其他方法。

贪心是效率和难度之间天然的平衡木——能用就赚大了，不能用就错得一塌糊涂。因此真正老练的做法是：先写一个暴力解兜底，再去怀疑一个贪心策略能否替代它。