引言
在计算机科学中，贪心算法（Greedy Algorithm）是一种直观且高效的解题策略。它不追求回溯或复杂的动态规划，而是每一步都做出当前看来最优的选择，期望通过局部的累积达到全局的最优解。
这种策略简单却充满智慧，常用于解决调度、路径规划等看似复杂的问题。当然，正如没有万能钥匙一样，贪心算法也有其严格的适用边界，只有在满足特定条件时，它才能展现出真正的威力。
核心思想：局部最优与全局最优
贪心算法的核心可以概括为：在每一个步骤中，我们都做出当前最优的选择，期待最后能获得最优的整体解。
贪心算法的执行步骤
- 问题分解：将原问题拆解为若干个子问题。
- 贪心选择：在每个子问题中，选择一个局部最优的解。
- 问题求解：通过局部最优的选择构建全局最优解。
- 验证最优性：检查贪心选择是否真的能带来全局最优解。
适用条件
贪心算法并非适用于所有问题，其成功依赖于两个关键性质：
贪心选择性质：局部最优解可以构成全局最优解。即，做出局部最优决策的过程中，并不会错过最终最优解。
最优子结构：问题的最优解包含了子问题的最优解。换句话说，大问题的最优解可以通过合并其子问题的最优解获得。
只有在满足这两个条件时，贪心算法才能保证找到全局最优解。
经典应用：活动选择问题
为了更具体地理解贪心算法的应用，我们以经典的'活动选择问题'为例。这是一个非常典型的场景，展示了如何通过简单的排序策略解决资源冲突。
问题描述 假设有多个活动，每个活动都有一个开始时间和结束时间。我们希望选择尽可能多的活动，使得这些活动之间没有重叠。
贪心策略 我们可以根据活动的结束时间进行排序，每次选择结束时间最早的活动，并确保它与之前的活动不重叠。这个策略之所以有效，是因为每次选择结束时间最早的活动能够为后续的活动留下最多的时间空间。
代码实现 下面是一个基于 C 语言的实现示例。在实际编写时，注意结构体的定义和比较函数的逻辑。
#include <stdio.h>
#include <stdlib.h>
// 结构体定义，表示每个活动的开始时间和结束时间
typedef struct {
int start;
int finish;
int index;
} Activity;
// 比较函数，用于根据活动的结束时间进行排序
int compare(const void *a, *b) {
((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);
;
}
