贪心算法的核心思想
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优解的算法策略。其目标是通过一系列局部最优的选择，最终达到全局最优的结果。
这种策略简单却充满智慧，常用于解决看似复杂的问题。然而，它并非万能钥匙，只有在满足特定条件时才能确保得到最优解。
适用条件
要使用贪心算法保证全局最优，问题必须同时具备以下两个性质：
- 贪心选择性质：局部最优解可以构成全局最优解。即做出局部最优决策的过程中，不会错过最终的最优解。
- 最优子结构：问题的最优解包含了子问题的最优解。大问题的最优解可以通过合并其子问题的最优解获得。
经典应用场景
虽然不能解决所有问题，但在某些经典场景中，贪心算法能以高效的方式提供满意的答案：
- 活动选择问题：给定一组活动的开始和结束时间，选择互不重叠的活动数量最大化。策略是每次选择结束时间最早的活动。
- 最小生成树问题：在图中选择边使图连通且权值和最小。策略是每次选择当前权值最小的边。
- 背包问题（贪心近似）：物品有重量和价值，选择物品使总价值最大。策略是优先选择单位重量价值最大的物品。
实战：活动选择问题实现
为了更直观地理解，我们通过'活动选择问题'来展示具体实现。目标是选择尽可能多的活动，使得它们之间没有重叠。
算法思路
- 将活动按结束时间从小到大排序。
- 遍历排序后的活动，如果当前活动的开始时间大于等于上一个被选活动的结束时间，则选择该活动。
- 更新最后结束时间，继续遍历。
这个策略之所以有效，是因为结束时间越早，留给后续活动的时间空间就越大。
代码实现
以下是基于 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;
}
// 活动选择函数，返回选择的活动索引
void activity_selection( start[], finish[], n) {
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);
;
}
