第29讲 贪心算法：贪心算法的基本思想、典型问题（活动选择、哈夫曼编码、最小生成树）

贪心算法，说白了就是“每次选当前最优的”。

我刚开始学数据结构时，总觉得这玩意儿太简单了。不就是每次挑最好的吗？后来在项目中踩过几次坑，才发现——贪心算法看着简单，但证明它“为什么对”才是真正的难点。

这一讲，我们就把贪心算法的底裤扒干净。

29.1 贪心算法的基本思想

贪心算法的核心就一句话：局部最优 → 全局最优。

你想想看，我们做决策时，每一步都选当前看起来最好的那个选择。然后期望最后的结果也是最好的。嗯，这听起来有点理想主义。但确实有一类问题，贪心策略就是对的。

贪心算法的三要素：

  • 贪心选择性质：每一步的最优解，可以推导出全局最优解
  • 最优子结构：子问题的最优解，能组合成原问题的最优解
  • 无后效性：当前决策不影响后续决策的独立性

我在项目中遇到过一个问题：用贪心算法做任务调度，结果发现局部最优并不等于全局最优。那次教训让我明白——贪心算法必须证明其正确性，不能想当然。

我的个人习惯：拿到一个问题，先试试贪心能不能解。如果能找到反例，就换动态规划。如果找不到反例，再尝试证明贪心正确性。

29.2 活动选择问题

活动选择是贪心算法的经典入门题。场景是这样的：

你有一个会议室，一天内有 n 个活动要使用。每个活动有开始时间 s[i] 和结束时间 f[i]。问最多能安排多少个活动？

贪心策略：每次选结束时间最早的活动。

为什么？因为结束时间越早，留给后面的时间就越多。这个道理很朴素，但证明起来需要点功夫。

// 活动选择 - 贪心实现
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start;
    int finish;
} Activity;

// 按结束时间排序
int cmp(const void *a, const void *b) {
    return ((Activity*)a)->finish - ((Activity*)b)->finish;
}

int greedyActivitySelector(Activity arr[], int n) {
    qsort(arr, n, sizeof(Activity), cmp);
    
    int count = 1;  // 第一个活动必选
    int lastFinish = arr[0].finish;
    
    printf("选择活动: %d (开始=%d, 结束=%d)\n", 0, arr[0].start, arr[0].finish);
    
    for (int i = 1; i < n; i++) {
        if (arr[i].start >= lastFinish) {
            count++;
            printf("选择活动: %d (开始=%d, 结束=%d)\n", i, arr[i].start, arr[i].finish);
            lastFinish = arr[i].finish;
        }
    }
    return count;
}

int main() {
    Activity acts[] = {{1,4}, {3,5}, {0,6}, {5,7}, {3,8}, {5,9}, {6,10}, {8,11}, {8,12}, {2,13}, {12,14}};
    int n = sizeof(acts)/sizeof(acts[0]);
    printf("最多可安排 %d 个活动\n", greedyActivitySelector(acts, n));
    return 0;
}

我曾经踩过的坑：一开始我按开始时间排序，结果选了一堆早开始但持续时间长的活动，反而排挤了更多短活动。记住：活动选择必须按结束时间排序，这是铁律。

29.3 哈夫曼编码

哈夫曼编码是数据压缩领域的基石。它的思想也很贪心：出现频率高的字符，用短编码；出现频率低的字符，用长编码。

具体做法是构建一棵哈夫曼树：

  1. 把所有字符按频率放入优先队列（最小堆）
  2. 每次取出两个频率最小的节点，合并成一个新节点
  3. 新节点的频率 = 两个子节点频率之和
  4. 把新节点放回队列
  5. 重复直到只剩一个节点（根节点）

你想想看，这个过程是不是每次都在选“当前最小的两个”？这就是贪心。

// 哈夫曼编码 - 核心构建逻辑
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct Node {
    char ch;
    int freq;
    struct Node *left, *right;
} Node;

// 最小堆（简化版，实际应用需用堆结构）
Node* buildHuffmanTree(char chars[], int freqs[], int n) {
    // 这里仅展示逻辑，完整实现需用优先队列
    // 实际项目中，我一般用最小堆来维护
    Node *nodes[MAX];
    int size = n;
    
    // 初始化节点
    for (int i = 0; i < n; i++) {
        nodes[i] = (Node*)malloc(sizeof(Node));
        nodes[i]->ch = chars[i];
        nodes[i]->freq = freqs[i];
        nodes[i]->left = nodes[i]->right = NULL;
    }
    
    // 贪心合并（每次取两个最小的）
    while (size > 1) {
        // 找两个最小频率的节点（实际应用用堆）
        int min1 = 0, min2 = 1;
        if (nodes[0]->freq > nodes[1]->freq) {
            min1 = 1; min2 = 0;
        }
        for (int i = 2; i < size; i++) {
            if (nodes[i]->freq < nodes[min1]->freq) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->freq < nodes[min2]->freq) {
                min2 = i;
            }
        }
        
        // 合并
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->ch = '\0';
        newNode->freq = nodes[min1]->freq + nodes[min2]->freq;
        newNode->left = nodes[min1];
        newNode->right = nodes[min2];
        
        // 替换掉min1，把min2移到末尾
        nodes[min1] = newNode;
        nodes[min2] = nodes[size-1];
        size--;
    }
    
    return nodes[0];  // 返回根节点
}

避坑指南：哈夫曼编码的贪心正确性证明，用的是“贪心选择性质 + 最优子结构”。我曾经面试时被问到“为什么哈夫曼编码是最优的”，当时没答好。后来我总结了一个记忆方法：任何最优编码树，最底层的两个叶子一定是频率最小的两个字符。这个性质保证了贪心是对的。

29.4 最小生成树

最小生成树（MST）是图论中的经典问题。给定一个带权无向图，找一棵树连接所有节点，且总权重最小。

贪心算法在这里有两个著名实现：

算法 贪心策略 时间复杂度 适用场景
Prim算法 每次选离当前树最近的节点 O(V²) 或 O(E log V) 稠密图
Kruskal算法 每次选权重最小的边，且不形成环 O(E log E) 稀疏图

我个人习惯用 Kruskal，因为它配合并查集实现起来很优雅。

// Kruskal算法 - 最小生成树
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int u, v, weight;
} Edge;

// 并查集
int parent[100];

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

void unionSet(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) parent[ry] = rx;
}

int cmp(const void *a, const void *b) {
    return ((Edge*)a)->weight - ((Edge*)b)->weight;
}

void kruskalMST(Edge edges[], int n, int V) {
    qsort(edges, n, sizeof(Edge), cmp);
    
    for (int i = 0; i < V; i++) parent[i] = i;
    
    int mstWeight = 0;
    printf("最小生成树的边:\n");
    
    for (int i = 0; i < n; i++) {
        int ru = find(edges[i].u);
        int rv = find(edges[i].v);
        
        if (ru != rv) {  // 不会形成环
            printf("  %d -- %d (权重: %d)\n", edges[i].u, edges[i].v, edges[i].weight);
            mstWeight += edges[i].weight;
            unionSet(ru, rv);
        }
    }
    printf("总权重: %d\n", mstWeight);
}

我曾经犯过的错：写 Kruskal 时忘了初始化并查集，结果 find 函数返回了随机值。调试了半小时才发现。记住：用并查集前一定要初始化 parent[i] = i。

29.5 贪心算法知识体系

下面这张图，是我整理贪心算法时画的。它把三个经典问题的关系串起来了：

贪心算法知识体系 贪心算法 贪心选择性质 最优子结构 无后效性 活动选择 按结束时间排序 哈夫曼编码 最小堆合并 最小生成树 Prim / Kruskal 核心思想：局部最优 → 全局最优 需要证明贪心选择性质 + 最优子结构

29.6 贪心算法的适用条件

不是所有问题都能用贪心。我总结了一个快速判断方法：

  • 能排序吗？—— 贪心往往需要对数据排序
  • 局部最优能推导全局吗？—— 试着找一个反例
  • 有重叠子问题吗？—— 如果有，可能更适合动态规划

我的经验法则：

  • 如果问题涉及“选最多”、“权重最小”、“路径最短”，先试试贪心
  • 如果问题涉及“所有可能组合”、“最优排列”，大概率是动态规划
  • 如果问题能分解成独立子问题，贪心往往有效

29.7 总结

贪心算法，说白了就是“每次选最好的，然后希望最后也是最好的”。

三个经典问题——活动选择、哈夫曼编码、最小生成树——覆盖了贪心算法的核心应用场景。它们都有一个共同点：局部最优选择不会影响后续选择的最优性。

嗯，这一讲的内容就到这里。记住：贪心算法不是万能的，但用对了地方，它就是最高效的解法。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →