引言
在计算机科学中，贪心算法（Greedy Algorithm）是一种解决最优化问题的常用策略。它的核心逻辑很简单：在每一步决策时，都选择当前看起来最优的方案，期望通过一系列局部最优的选择最终达到全局最优。
这种策略简单高效，但并非万能。它只在特定条件下才能保证得到全局最优解。本文将深入探讨贪心算法的原理、适用条件，并通过经典的'活动选择问题'进行代码实战。
核心思想：局部最优与全局最优
贪心算法的本质可以概括为：在每一步都做出当前状态下的最佳选择。它不需要回溯，也不依赖对未来情况的完全预测，而是专注于眼前的利益最大化。
要成功应用贪心算法，问题必须满足两个关键性质：
- 贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择来达到。也就是说，当前的选择不会影响后续的最优性。
- 最优子结构：当一个问题的最优解包含其子问题的最优解时，称该问题具有最优子结构性质。
只有同时满足这两个条件，贪心策略才能确保最终结果的正确性。
经典应用场景
虽然贪心算法不能解决所有问题，但在以下场景中表现优异：
- 活动选择问题：在互不冲突的前提下，安排尽可能多的活动。
- 最小生成树问题：如 Prim 算法和 Kruskal 算法，构建权值和最小的连通图。
- 霍夫曼编码：用于数据压缩，构建最优前缀码。
- 背包问题（贪心近似）：当物品可分割时，按单位价值排序选取。
实战：活动选择问题
问题描述
给定一组活动，每个活动都有开始时间和结束时间。目标是选择尽可能多的活动，使得它们的时间区间互不重叠。
策略分析
直觉上，为了让剩下的时间能容纳更多活动，我们应该优先选择结束时间最早的活动。这样能为后续活动留出最多的时间窗口。这就是典型的贪心策略。
代码实现
下面使用 C 语言实现这一逻辑。我们定义一个结构体来存储活动信息，利用 qsort 按结束时间排序，然后遍历选择兼容的活动。
#include <stdio.h>
#include <stdlib.h>
// 定义活动结构体
typedef struct {
int start;
int finish;
int index;
} Activity;
// 比较函数：按结束时间升序排序
int compare(const void *a, const void *b) {
return ((Activity *)a)->finish - ((Activity *)b)->finish;
}
// 活动选择主函数
{
Activity activities[n];
( i = ; i < n; i++) {
activities[i].start = start[i];
activities[i].finish = finish[i];
activities[i].index = i;
}
qsort(activities, n, (Activity), compare);
();
last_end_time = ;
( i = ; i < n; i++) {
(activities[i].start >= last_end_time) {
(, activities[i].index);
last_end_time = activities[i].finish;
}
}
();
}
{
start[] = {, , , , , };
finish[] = {, , , , , };
n = (start) / (start[]);
activity_selection(start, finish, n);
;
}
