一、貪心算法核心思想
特征：在每一步選擇中都采取當前狀態下最優（局部最優）的選擇，從而希望導致全局最優解
適用場景：需要滿足貪心選擇性質和最優子結構性質
二、經典貪心算法示例
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(V2) | O(V) | 不需要 |
| 背包問題（分數） | ? | O(n log n) | O(1) | 需要 |
四、貪心算法的局限性
- 局部最優 ≠ 全局最優：如旅行商問題（TSP）無法用純貪心解法
- 需要嚴格證明：必須證明貪心選擇性質和最優子結構
- 依賴問題特性：僅適用于特定類型的問題
五、應用場景推薦
- 任務調度優化
- 最小生成樹（Prim/Kruskal算法）
- 文件壓縮（霍夫曼編碼）
- 網絡路由（Dijkstra算法）
- 集合覆蓋問題（近似解）
六、練習建議
- 實現完整的霍夫曼編碼程序
- 解決區間覆蓋問題（如：用最少的區間覆蓋指定線段）
- 嘗試解決「加油站繞行」問題（LeetCode 134）
- 學習如何證明貪心算法的正確性（數學歸納法、交換論證法）
