C语言中的贪心算法
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前最优解的算法，希望通过局部最优解的选择，最终得到全局最优解。它常用于解决最优化问题，如最小生成树、最短路径等。本文将从理论到实践，逐步引导初学者掌握贪心算法在 C 语言中的实现。
什么是贪心算法？
贪心算法的核心是 贪心选择性质 和 最优子结构：
- 贪心选择性质：每次选择当前看起来最优的解。
- 最优子结构：问题的最优解可以通过子问题的最优解合并得到。
举个例子：假如你需要用最少的硬币找零，每次选择最大面值的硬币就是贪心的思路。
贪心算法的适用场景
贪心算法并不总是能找到全局最优解，适用场景包括：
- 最小生成树问题（如 Prim、Kruskal 算法）
- 活动选择问题
- 最短路径问题（如 Dijkstra 算法，虽然不是纯贪心，但核心思想类似）
贪心算法的实现步骤
以下是实现贪心算法的通用步骤：
- 分析问题是否满足贪心选择性质和最优子结构。
- 排序：根据特定规则对问题的元素进行排序（通常需要一个比较函数）。
- 逐步选择：从头开始，选择符合条件的元素，直到满足目标。
- 验证结果：确保结果满足问题的要求。
示例：活动选择问题
问题描述
给定一组活动，每个活动有一个开始时间和结束时间。你需要选择尽可能多的活动，且这些活动之间不能重叠。
贪心思路
- 按活动的结束时间升序排序（结束得越早，留给后续活动的时间越多）。
- 依次选择每个活动，如果它的开始时间不早于上一个已选活动的结束时间，则选择它。
C语言实现
以下是活动选择问题的 C 语言实现代码：
#include <stdio.h>
#include <stdlib.h>
// 定义活动结构体
typedef struct {
int start;
int end;
} Activity;
// 比较函数，用于按结束时间排序
int compare(const void *a, const void *b) {
Activity *activity1 = (Activity *)a;
Activity *activity2 = (Activity *)b;
return activity1->end - activity2->end;
}
// 贪心算法选择活动
void selectActivities(Activity activities[], int n) {
// 按结束时间排序
qsort(activities, n, sizeof(Activity), compare);
printf("选择的活动如下：\n");
int lastEndTime = 0;
for (int i = 0; i < n; i++) {
if (activities[i].start >= lastEndTime) {
printf("活动[%d]: 开始时间 = %d, 结束时间 = %d\n", i + 1, activities[i].start, activities[i].end);
lastEndTime = activities[i].end;
}
}
}
int main() {
Activity activities[] = {
{1, 3},
{2, 5},
{4, 6},
{6, 7},
{5, 9},
{8, 9}
};
int n = sizeof(activities) / sizeof(activities[0]);
selectActivities(activities, n);
return 0;
}
代码分析
- 数据结构：用
struct定义活动的开始和结束时间。 - 排序：用
qsort对活动按结束时间升序排列。 - 贪心选择：逐一遍历排序后的活动，如果活动的开始时间不与上一次选择的活动冲突，就将其加入结果。
输入输出示例
输入活动：
- 活动1：开始时间=1，结束时间=3
- 活动2：开始时间=2，结束时间=5
- 活动3：开始时间=4，结束时间=6
- 活动4：开始时间=6，结束时间=7
- 活动5：开始时间=5，结束时间=9
- 活动6：开始时间=8，结束时间=9
输出活动：
选择的活动如下：
活动[1]: 开始时间 = 1, 结束时间 = 3
活动[3]: 开始时间 = 4, 结束时间 = 6
活动[4]: 开始时间 = 6, 结束时间 = 7
活动[6]: 开始时间 = 8, 结束时间 = 9
总结
- 贪心算法的核心是找到局部最优解，逐步逼近全局最优解。
- 关键在于分析问题是否适合贪心策略，排序规则是实现的基础。
- 通过活动选择问题，初学者可以掌握贪心算法的基本思想。
尝试多练习一些经典的贪心问题，如背包问题、最短路径问题等，你会发现贪心算法是一种高效且优雅的解决问题方法！