贪心算法：贪心思想、活动选择问题、哈夫曼编码、找零问题
贪心算法，说白了就是「每一步都选当前最好的」。
听起来很简单对吧？但实际用起来，坑不少。我刚开始学的时候，总觉得这玩意儿太随意了，能靠谱吗？后来在项目中用多了才发现——嗯，它确实不保证全局最优，但一旦能用，效率是真的高。
贪心思想的核心
贪心算法的核心就一句话：局部最优 → 全局最优。
你想想看，每次做决策时，都选当前看起来最好的那个。不去考虑未来，也不回溯。这种策略在某些问题上非常有效，比如找零、活动安排、哈夫曼编码。
但要注意，贪心不是万能的。我曾经在一个背包问题上硬套贪心，结果算出来的方案比最优解差了20%。后来才明白——贪心算法需要问题本身具有「贪心选择性质」和「最优子结构」。
贪心算法的两个关键性质：
- 贪心选择性质：每一步的局部最优能导向全局最优
- 最优子结构：子问题的最优解能构成原问题的最优解
说白了，就是问题本身得「配合」贪心。如果问题不满足这两个性质，贪心就会翻车。
活动选择问题
这是贪心算法的经典入门题。我当年面试时就被问过，还好提前练过。
问题描述：有一堆活动，每个活动有开始时间和结束时间。你只能同时参加一个活动，问最多能参加几个？
贪心策略很简单：每次选结束时间最早的那个。为什么？因为结束得越早，留给后面的时间就越多。
#include <stdio.h>
// 活动结构体
typedef struct {
int start;
int end;
} Activity;
// 按结束时间排序（这里假设已经排好序）
void greedy_activity_selection(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 activities[] = {
{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8},
{5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}
};
int n = sizeof(activities) / sizeof(activities[0]);
greedy_activity_selection(activities, n);
return 0;
}输出结果会选 {1,4}、{5,7}、{8,11} 这三个活动。你想想看，如果选了 {3,5} 会怎样？那就只能选两个了。所以贪心在这里确实管用。
我的经验：实际项目中，活动选择问题经常出现在会议室预订、任务调度等场景。我做过一个嵌入式任务调度器，用的就是类似思路——每次选截止时间最早的任务先执行。
哈夫曼编码
哈夫曼编码是数据压缩的经典算法。我记得第一次接触时觉得好神奇——同样的数据，怎么就能用更少的比特表示呢？
核心思想：出现频率高的字符用短编码，频率低的用长编码。这样整体长度就缩短了。
贪心体现在哪里？每次从频率集合中选两个最小的，合并成一个新节点。重复这个过程，直到只剩一个节点——这就是哈夫曼树。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// 哈夫曼树节点
typedef struct {
char ch;
int freq;
int left, right;
} HuffmanNode;
// 选择两个最小频率的节点
void select_two_min(HuffmanNode nodes[], int n, int *min1, int *min2) {
*min1 = -1;
*min2 = -1;
for (int i = 0; i < n; i++) {
if (nodes[i].freq == -1) continue; // 已合并
if (*min1 == -1 || nodes[i].freq < nodes[*min1].freq) {
*min2 = *min1;
*min1 = i;
} else if (*min2 == -1 || nodes[i].freq < nodes[*min2].freq) {
*min2 = i;
}
}
}
void build_huffman_tree(HuffmanNode nodes[], int n) {
int total = n;
while (1) {
int min1, min2;
select_two_min(nodes, total, &min1, &min2);
if (min2 == -1) break; // 只剩一个节点
// 合并两个最小节点
nodes[total].ch = '#';
nodes[total].freq = nodes[min1].freq + nodes[min2].freq;
nodes[total].left = min1;
nodes[total].right = min2;
// 标记已合并
nodes[min1].freq = -1;
nodes[min2].freq = -1;
total++;
}
}
int main() {
// 初始化5个字符及其频率
HuffmanNode nodes[MAX] = {
{'a', 5, -1, -1},
{'b', 9, -1, -1},
{'c', 12, -1, -1},
{'d', 13, -1, -1},
{'e', 16, -1, -1}
};
build_huffman_tree(nodes, 5);
printf("哈夫曼树构建完成\n");
printf("根节点频率: %d\n", nodes[9].freq); // 总频率
return 0;
}避坑指南：我曾经在实现哈夫曼编码时，忘记处理频率相同的字符。结果编码表不稳定，解压时数据全乱了。后来加了个稳定排序才解决——频率相同时按字符顺序排。
哈夫曼编码的压缩率取决于数据分布。如果所有字符频率差不多，压缩效果就不明显。但如果有些字符出现特别频繁——比如英文中的 'e'——那压缩效果就很可观了。
找零问题
找零问题可能是最直观的贪心例子了。你去便利店买东西，收银员怎么给你找零？肯定是先给大面额的，再给小面额的。
比如要找 36 元，有 25、10、5、1 四种面额。贪心策略：先拿一个 25，再拿一个 10，再拿一个 1。搞定。
#include <stdio.h>
void coin_change(int amount, int coins[], int n) {
printf("找零 %d 元:\n", amount);
for (int i = 0; i < n; i++) {
int count = amount / coins[i];
if (count > 0) {
printf(" 使用 %d 个 %d 元\n", count, coins[i]);
amount -= count * coins[i];
}
}
}
int main() {
int coins[] = {25, 10, 5, 1};
int n = sizeof(coins) / sizeof(coins[0]);
coin_change(36, coins, n);
return 0;
}输出：
找零 36 元:
使用 1 个 25 元
使用 1 个 10 元
使用 1 个 1 元但要注意：贪心找零不是所有货币体系都适用。比如面额是 {1, 3, 4}，要找 6 元。贪心会选 4+1+1（3枚），但最优解是 3+3（2枚）。
所以用贪心前，先确认货币面额是否满足「规范」——通常人民币、美元这种标准货币体系是没问题的。
贪心算法的适用场景
我总结了一下，贪心算法适合这几类问题：
- 活动安排：选结束时间最早的
- 哈夫曼编码：选频率最小的合并
- 找零问题：选面额最大的
- 最小生成树：Prim 和 Kruskal 都是贪心
- 单源最短路径：Dijkstra 也是贪心
这些问题的共同点是什么？局部最优就是全局最优。如果你发现一个问题可以「拆成子问题，且子问题之间互不影响」，那贪心就值得一试。
我的建议：遇到新问题时，先试试贪心。如果不行，再考虑动态规划。贪心的实现成本低，调试也容易。我很多项目里都是先用贪心跑一版，性能不够再换更复杂的算法。
贪心 vs 动态规划
很多人分不清贪心和动态规划。我简单说下区别：
| 对比项 | 贪心算法 | 动态规划 |
|---|---|---|
| 决策方式 | 只看当前 | 考虑所有可能 |
| 子问题 | 只解决一个 | 解决所有子问题 |
| 时间复杂度 | 通常 O(n) 或 O(n log n) | 通常 O(n²) 或更高 |
| 最优性 | 不保证全局最优 | 保证全局最优 |
说白了，贪心是「快但可能不准」，动态规划是「准但慢」。选哪个，看你项目对精度的要求。
本章小结
贪心算法，核心就是「每一步选最好的」。活动选择、哈夫曼编码、找零问题，都是经典应用。
我个人觉得，贪心算法是性价比最高的算法之一——代码短、思路清晰、运行快。但一定要记住：不是所有问题都能用贪心。用之前，先确认问题是否满足贪心选择性质和最优子结构。
嗯，这一章就到这里。下一章我们聊聊动态规划——那个比贪心更「稳」的家伙。