第十八章 贪心算法：贪心策略原理、活动选择问题、分数背包、哈夫曼编码
贪心算法，说白了就是“每一步都选当前最好的”。
听起来很简单对吧？但实际用起来，坑不少。我刚开始学的时候，总觉得贪心就是“局部最优等于全局最优”，结果写出来的代码经常翻车。后来才明白——贪心不是万能药，它只适用于那些“局部最优能推导出全局最优”的问题。
18.1 贪心策略的核心原理
贪心算法的核心就一句话：在每一步选择中，都采取当前状态下最优的选择，从而希望最终得到全局最优解。
但这里有个关键前提——贪心选择性质。什么意思？就是说，你每一步做的局部最优选择，不会影响后续的选择空间，而且最终能拼出全局最优。
我举个例子你就明白了。假设你要从一堆硬币里凑出某个金额，每次拿最大面额的硬币。如果硬币面额是 1、5、10、25，那贪心没问题。但如果面额是 1、3、4，你要凑 6 块钱——贪心会先拿 4，再拿 1，再拿 1，总共 3 枚。但最优解其实是 3+3，只要 2 枚。看到了吧？贪心在这里就失效了。
贪心算法的两个关键性质：
- 贪心选择性质：局部最优能推导出全局最优
- 最优子结构性质：问题的最优解包含子问题的最优解
我个人习惯，拿到一个问题先问自己三个问题：
- 这个问题能不能用贪心？
- 如果贪心，每一步选什么？
- 选了之后，剩下的问题是不是和原问题结构一样？
如果三个答案都是肯定的，那贪心大概率能行。
18.2 活动选择问题
这是贪心算法的经典入门题。场景是这样的：你有一个会议室，一堆活动要安排，每个活动有开始时间和结束时间。问最多能安排多少个活动？
贪心策略很简单：每次选结束时间最早的那个活动。为什么？因为结束时间越早，留给后面的时间就越多。
我当年第一次写这个算法时，犯了个低级错误——按开始时间排序。结果选了一堆早开始但拖很久的活动，后面全排不上了。后来才意识到，按结束时间排序才是正道。
避坑指南：我曾经在项目里用贪心排会议，结果忘了处理“结束时间相同”的情况。后来加了个按开始时间二次排序，才稳定下来。
来看代码实现：
#include <stdio.h>
#include <stdlib.h>
// 活动结构体
typedef struct {
int start;
int end;
} Activity;
// 按结束时间排序
int cmp(const void* a, const void* b) {
return ((Activity*)a)->end - ((Activity*)b)->end;
}
// 贪心选择活动
void selectActivities(Activity arr[], int n) {
qsort(arr, n, sizeof(Activity), cmp);
printf("选中的活动：\n");
int lastEnd = -1;
for (int i = 0; i < n; i++) {
if (arr[i].start >= lastEnd) {
printf("(%d, %d)\n", arr[i].start, arr[i].end);
lastEnd = arr[i].end;
}
}
}
int main() {
Activity activities[] = {{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(activities) / sizeof(activities[0]);
selectActivities(activities, n);
return 0;
}这段代码的时间复杂度是 O(n log n)，主要花在排序上。选活动本身是 O(n)。
18.3 分数背包问题
背包问题有两个版本：0-1 背包和分数背包。0-1 背包不能用贪心（得用动态规划），但分数背包可以。
分数背包允许你拿物品的一部分。比如一个金条重 10 公斤，你可以只拿 3 公斤。那贪心策略就很简单了：每次选单位重量价值最高的物品。
我记得有一次做资源分配项目，要把有限的带宽分配给不同的服务。每个服务有优先级和带宽需求，但可以只分配一部分。这不就是分数背包吗？直接用贪心，按优先级/带宽比排序，先给高的分配。
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int weight;
int value;
double ratio; // 单位重量价值
} Item;
int cmp(const void* a, const void* b) {
double r1 = ((Item*)a)->ratio;
double r2 = ((Item*)b)->ratio;
if (r1 > r2) return -1;
if (r1 < r2) return 1;
return 0;
}
double fractionalKnapsack(Item items[], int n, int capacity) {
qsort(items, n, sizeof(Item), cmp);
double totalValue = 0.0;
int remaining = capacity;
for (int i = 0; i < n && remaining > 0; i++) {
if (items[i].weight <= remaining) {
// 全拿
totalValue += items[i].value;
remaining -= items[i].weight;
} else {
// 拿一部分
totalValue += items[i].ratio * remaining;
remaining = 0;
}
}
return totalValue;
}
int main() {
Item items[] = {{10, 60, 6.0}, {20, 100, 5.0}, {30, 120, 4.0}};
int n = 3, capacity = 50;
printf("最大价值：%.2f\n", fractionalKnapsack(items, n, capacity));
return 0;
}注意：分数背包和 0-1 背包是两码事。0-1 背包不能贪心，必须用动态规划。我见过有人面试时把两者搞混，直接写贪心，结果被面试官问住了。
18.4 哈夫曼编码
哈夫曼编码是数据压缩领域的经典算法。它的核心思想是：出现频率高的字符用短编码，频率低的用长编码。
贪心策略体现在哪里？每次从所有节点中选两个频率最小的合并，直到只剩一棵树。这就是典型的“每次选最优”的贪心思路。
我当年做嵌入式项目时，需要把传感器数据通过串口传输。数据量大了之后，传输速度跟不上。后来用哈夫曼编码压缩了一下，传输量直接降了 40%。嗯，效果立竿见影。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
// 哈夫曼树节点
typedef struct Node {
char ch;
int freq;
struct Node *left, *right;
} Node;
// 最小堆
typedef struct {
Node* nodes[MAX];
int size;
} MinHeap;
// 创建节点
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;
}
// 交换节点
void swap(Node** a, Node** b) {
Node* temp = *a;
*a = *b;
*b = temp;
}
// 最小堆化
void minHeapify(MinHeap* heap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < heap->size && heap->nodes[left]->freq < heap->nodes[smallest]->freq)
smallest = left;
if (right < heap->size && heap->nodes[right]->freq < heap->nodes[smallest]->freq)
smallest = right;
if (smallest != idx) {
swap(&heap->nodes[idx], &heap->nodes[smallest]);
minHeapify(heap, smallest);
}
}
// 提取最小节点
Node* extractMin(MinHeap* heap) {
Node* node = heap->nodes[0];
heap->nodes[0] = heap->nodes[heap->size - 1];
heap->size--;
minHeapify(heap, 0);
return node;
}
// 插入节点
void insertMinHeap(MinHeap* heap, Node* node) {
heap->size++;
int i = heap->size - 1;
while (i > 0 && node->freq < heap->nodes[(i - 1) / 2]->freq) {
heap->nodes[i] = heap->nodes[(i - 1) / 2];
i = (i - 1) / 2;
}
heap->nodes[i] = node;
}
// 构建哈夫曼树
Node* buildHuffmanTree(char chars[], int freqs[], int n) {
MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
heap->size = 0;
for (int i = 0; i < n; i++)
insertMinHeap(heap, createNode(chars[i], freqs[i]));
while (heap->size > 1) {
Node* left = extractMin(heap);
Node* right = extractMin(heap);
Node* parent = createNode('$', left->freq + right->freq);
parent->left = left;
parent->right = right;
insertMinHeap(heap, parent);
}
return extractMin(heap);
}
// 打印编码
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");
}
}
int main() {
char chars[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int freqs[] = {5, 9, 12, 13, 16, 45};
int n = 6;
Node* root = buildHuffmanTree(chars, freqs, n);
int arr[MAX], top = 0;
printf("哈夫曼编码：\n");
printCodes(root, arr, top);
return 0;
}这段代码实现了完整的哈夫曼编码过程。核心就是那个 while 循环——每次从堆里取两个最小的，合并后再放回去。这就是贪心。
18.5 知识体系总览
下面这张图把本章的核心知识点串起来了。你仔细看看，会发现贪心算法的套路其实很固定。
18.6 贪心算法的适用场景总结
学完这三个经典问题，你应该能感觉到贪心算法的套路了。我总结一下：
| 问题类型 | 贪心策略 | 时间复杂度 | 是否最优 |
|---|---|---|---|
| 活动选择 | 按结束时间升序 | O(n log n) | 是 |
| 分数背包 | 按单位价值降序 | O(n log n) | 是 |
| 哈夫曼编码 | 每次合并最小频率 | O(n log n) | 是 |
| 0-1 背包 | 贪心无效 | — | 否 |
记住：贪心算法不是万能的。遇到问题先判断是否满足贪心选择性质。如果不确定，试试动态规划——虽然慢，但至少不会错。
好了，这一章就讲到这里。贪心算法的核心就这些——选好策略，证明它有效，然后写代码。下次你遇到类似问题，不妨先想想：能不能贪心？
公众号:蓝海资料掘金营，微信deep3321