C语言中的贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前最优解的算法，希望通过局部最优解的选择，最终得到全局最优解。它常用于解决最优化问题，如最小生成树、最短路径等。本文将从理论到实践，逐步引导初学者掌握贪心算法在 C 语言中的实现。

---

什么是贪心算法？

贪心算法的核心是 贪心选择性质 和 最优子结构：

1. 贪心选择性质：每次选择当前看起来最优的解。
2. 最优子结构：问题的最优解可以通过子问题的最优解合并得到。

举个例子：假如你需要用最少的硬币找零，每次选择最大面值的硬币就是贪心的思路。

---

贪心算法的适用场景

贪心算法并不总是能找到全局最优解，适用场景包括：

• 最小生成树问题（如 Prim、Kruskal 算法）
• 活动选择问题
• 最短路径问题（如 Dijkstra 算法，虽然不是纯贪心，但核心思想类似）

---

贪心算法的实现步骤

以下是实现贪心算法的通用步骤：

1. 分析问题是否满足贪心选择性质和最优子结构。
2. 排序：根据特定规则对问题的元素进行排序（通常需要一个比较函数）。
3. 逐步选择：从头开始，选择符合条件的元素，直到满足目标。
4. 验证结果：确保结果满足问题的要求。

---

示例：活动选择问题

问题描述

给定一组活动，每个活动有一个开始时间和结束时间。你需要选择尽可能多的活动，且这些活动之间不能重叠。

贪心思路

1. 按活动的结束时间升序排序（结束得越早，留给后续活动的时间越多）。
2. 依次选择每个活动，如果它的开始时间不早于上一个已选活动的结束时间，则选择它。

---

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;
}

---

代码分析

1. 数据结构：用 struct 定义活动的开始和结束时间。
2. 排序：用 qsort 对活动按结束时间升序排列。
3. 贪心选择：逐一遍历排序后的活动，如果活动的开始时间不与上一次选择的活动冲突，就将其加入结果。

---

输入输出示例

输入活动：

• 活动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

---

总结

1. 贪心算法的核心是找到局部最优解，逐步逼近全局最优解。
2. 关键在于分析问题是否适合贪心策略，排序规则是实现的基础。
3. 通过活动选择问题，初学者可以掌握贪心算法的基本思想。

尝试多练习一些经典的贪心问题，如背包问题、最短路径问题等，你会发现贪心算法是一种高效且优雅的解决问题方法！