贪心算法：贪心思想、活动选择问题、哈夫曼编码、最小生成树（回顾贪心视角）

贪心算法，说白了就是「每一步都选当前最优，不管以后」。听起来有点短视对吧？但奇怪的是，很多问题用这种「短视」策略，反而能拿到全局最优解。我刚开始学的时候也觉得这玩意儿不靠谱，直到在项目中用它解决了一个调度问题，才真正服气。

这一章，我会带你从贪心的核心思想出发，依次搞定活动选择、哈夫曼编码，最后用贪心的视角重新审视最小生成树。嗯，你会发现，原来很多看似复杂的问题，背后都是同一个套路。

1. 贪心思想：局部最优真的能导出全局最优吗？

贪心算法的核心就一句话：在每一步选择中，都采取当前状态下最好或最优的选择。它不做回溯，不关心未来，只盯着眼前。

但这里有个大坑——贪心并不保证一定能得到全局最优解。你想想看，如果每个问题都能用贪心搞定，那动态规划就没存在的必要了。贪心能用的前提是：问题具有「最优子结构」和「贪心选择性质」。

• 最优子结构：一个问题的最优解包含其子问题的最优解。
• 贪心选择性质：通过局部最优选择，可以构造出全局最优解。

举个例子，找零钱问题：假设有1、5、10、25美分的硬币，要凑出36美分。贪心策略是每次选最大的——25+10+1=36，完美。但如果硬币面额是1、3、4，要凑6美分呢？贪心选4+1+1=3枚，但最优解是3+3=2枚。看到了吧？贪心在这里就翻车了。

2. 活动选择问题：会议室排期的经典案例

活动选择问题是贪心算法的入门题。场景是这样的：你有一个会议室，一堆活动要申请使用，每个活动有开始时间和结束时间。问最多能安排多少个活动？

贪心策略很简单：每次选结束时间最早的那个活动。为什么？因为结束时间越早，留给后面的时间就越多。

来看代码：

#include <stdio.h>

// 活动结构体
typedef struct {
    int start;
    int end;
} Activity;

// 按结束时间排序（这里假设已经排好序）
void activitySelection(Activity arr[], int n) {
    int i = 0;
    printf("选择的活动: %d (开始=%d, 结束=%d)\n", i, arr[i].start, arr[i].end);

    for (int j = 1; j < n; j++) {
        if (arr[j].start >= arr[i].end) {
            printf("选择的活动: %d (开始=%d, 结束=%d)\n", j, arr[j].start, arr[j].end);
            i = j;
        }
    }
}

int main() {
    Activity arr[] = {{1, 3}, {2, 5}, {3, 7}, {4, 6}, {6, 8}, {7, 9}};
    int n = sizeof(arr) / sizeof(arr[0]);
    activitySelection(arr, n);
    return 0;
}

输出结果：

选择的活动: 0 (开始=1, 结束=3)
选择的活动: 3 (开始=4, 结束=6)
选择的活动: 4 (开始=6, 结束=8)

你看，代码逻辑其实很简单。核心就是每次选结束时间最早的，然后跳过所有与之冲突的活动。

3. 哈夫曼编码：数据压缩背后的贪心

哈夫曼编码是数据压缩领域的经典算法。它的目标是用最短的二进制编码来表示一组字符，且编码是前缀码（没有一个编码是另一个编码的前缀）。

贪心策略：每次从频率最低的两个节点合并，构建一棵二叉树。频率越高的字符，编码越短。

步骤是这样的：

1. 统计每个字符的出现频率。
2. 把每个字符看作一个节点，频率作为权重。
3. 每次选两个权重最小的节点，合并成一个新节点，权重为两者之和。
4. 重复直到只剩一个节点（根节点）。
5. 左子树编码为0，右子树编码为1，从根到叶子路径即为该字符的编码。

来看代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// 哈夫曼树节点
typedef struct Node {
    char ch;
    int freq;
    struct Node *left, *right;
} Node;

// 最小堆（简化版，实际应用需用优先队列）
Node* createNode(char ch, int freq) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->ch = ch;
    node->freq = freq;
    node->left = node->right = NULL;
    return node;
}

// 构建哈夫曼树（这里只展示核心逻辑）
Node* buildHuffmanTree(char chars[], int freqs[], int n) {
    // 实际实现需要最小堆，这里简化
    // 每次取两个最小频率节点合并
    // 返回根节点
    return NULL; // 占位
}

// 打印编码
void printCodes(Node* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if (!root->left && !root->right) {
        printf("%c: ", root->ch);
        for (int i = 0; i < top; i++)
            printf("%d", arr[i]);
        printf("\n");
    }
}

哈夫曼编码的贪心体现在哪里？就是每次合并两个最小的。这个策略保证了总编码长度最短。我在做嵌入式项目时，用哈夫曼编码压缩过日志数据，效果立竿见影——存储空间直接省了一半。

4. 最小生成树：从贪心视角重新审视

最小生成树（MST）问题，你可能已经学过Prim算法和Kruskal算法。今天我们从贪心的角度重新看看它们。

先说Prim算法：从任意一个顶点开始，每次选一条连接「已选顶点集」和「未选顶点集」的最小权值边。这其实就是贪心——每次选当前能连的最短边。

再看Kruskal算法：把所有边按权值从小到大排序，每次选一条不会形成环的边。这也是贪心——每次选当前最小的边。

两个算法都是贪心，但贪心的「视角」不同：

算法	贪心策略	数据结构	时间复杂度
Prim	每次选连接已选集合的最小边	优先队列	O(E log V)
Kruskal	每次选全局最小边，不形成环	并查集	O(E log E)

为什么这两个贪心算法能保证得到全局最优？因为它们都满足「最优子结构」和「贪心选择性质」。Prim的贪心选择性质是：连接已选集合的最小边一定在某个MST中。Kruskal的则是：当前最小边如果不形成环，一定在某个MST中。

5. 知识体系总览

下面这张图总结了本章的核心知识结构，帮你理清贪心算法的脉络：

贪心算法其实没那么神秘。说白了就是：排序 + 局部最优选择 + 验证性质。排序是为了让「局部最优」有据可循，验证性质是为了确保不会翻车。

我在实际项目中用贪心解决过不少问题，比如任务调度、资源分配、路径规划。但每次用之前，我都会问自己三个问题：

1. 这个问题有没有最优子结构？
2. 局部最优选择能不能导出全局最优？
3. 有没有反例能推翻贪心策略？

如果三个问题都通过了，那就放心大胆地用。如果有一个不通过，嗯，那就老老实实上动态规划吧。

---

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