C语言实现贪心算法

一、贪心算法核心思想

特征：在每一步选择中都采取当前状态下最优（局部最优）的选择，从而希望导致全局最优解
适用场景：需要满足贪心选择性质和最优子结构性质

---

二、经典贪心算法示例

1. 活动选择问题

目标：在给定时间段内安排最多的互不冲突的活动
策略：每次选择结束时间最早的活动

#include <stdio.h>
#include <stdlib.h>// 活动结构体定义
typedef struct {int start;int end;
} Activity;// 比较函数：按结束时间升序排序
int compare(const void *a, const void *b) {Activity *actA = (Activity*)a;Activity *actB = (Activity*)b;return actA->end - actB->end;
}void activitySelection(Activity activities[], int n) {// 按结束时间排序qsort(activities, n, sizeof(Activity), compare);printf("选中活动序列:\n");int lastEnd = 0;for(int i=0; i<n; i++) {if(activities[i].start >= lastEnd) {printf("[%d-%d] ", activities[i].start, activities[i].end);lastEnd = activities[i].end;}}
}int main() {Activity acts[] = {{1,3}, {2,5}, {3,7}, {5,9}, {8,10}};int n = sizeof(acts)/sizeof(acts[0]);activitySelection(acts, n);  // 输出：[1-3] [3-7] [8-10]return 0;
}

---

2. 找零钱问题

目标：用最少的硬币数量组成指定金额（假设硬币系统为规范系统，如人民币）
策略：每次选择当前可用的最大面值硬币

#include <stdio.h>void coinChange(int coins[], int n, int amount) {printf("找零%d元的方案：\n", amount);for(int i=0; i<n; i++) {while(amount >= coins[i]) {printf("%d元 ", coins[i]);amount -= coins[i];}}if(amount > 0) printf("\n剩余%d元无法找零", amount);
}int main() {int coins[] = {100, 50, 20, 10, 5, 1}; // 降序排列int amount = 176;coinChange(coins, 6, amount);  // 输出：100元 50元 20元 5元 1元return 0;
}

---

3. 霍夫曼编码（核心部分）

目标：生成最优前缀编码，实现数据压缩
策略：每次合并频率最小的两个节点

#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_HT 100// 霍夫曼树节点
struct MinHeapNode {char data;unsigned freq;struct MinHeapNode *left, *right;
};// 最小堆结构
struct MinHeap {unsigned size;unsigned capacity;struct MinHeapNode** array;
};// 创建新节点
struct MinHeapNode* newNode(char data, unsigned freq) {struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));temp->left = temp->right = NULL;temp->data = data;temp->freq = freq;return temp;
}// 核心构建函数（完整实现需要约150行代码，此处展示核心逻辑）
void buildHuffmanTree(char data[], int freq[], int size) {// 1. 创建最小堆并初始化// 2. 循环执行以下操作直到堆中只剩一个节点：//    a. 提取两个最小频率节点//    b. 创建新内部节点，频率为两者之和//    c. 将新节点插入堆// 3. 剩余节点即为霍夫曼树的根
}

---

三、贪心算法特性对比

问题类型	适用性	时间复杂度	空间复杂度	是否需要排序
活动选择问题	✅	O(n log n)	O(1)	需要
找零问题	✅	O(n)	O(1)	需要
单源最短路径	✅	O(V²)	O(V)	不需要
背包问题（分数）	✅	O(n log n)	O(1)	需要

---

四、贪心算法的局限性

1. 局部最优 ≠ 全局最优：如旅行商问题（TSP）无法用纯贪心解法
2. 需要严格证明：必须证明贪心选择性质和最优子结构
3. 依赖问题特性：仅适用于特定类型的问题

---

五、应用场景推荐

• 任务调度优化
• 最小生成树（Prim/Kruskal算法）
• 文件压缩（霍夫曼编码）
• 网络路由（Dijkstra算法）
• 集合覆盖问题（近似解）

---

六、练习建议

1. 实现完整的霍夫曼编码程序
2. 解决区间覆盖问题（如：用最少的区间覆盖指定线段）
3. 尝试解决「加油站绕行」问题（LeetCode 134）
4. 学习如何证明贪心算法的正确性（数学归纳法、交换论证法）