算法之貪心算法

貪心算法

貪心算法
- 核心思想
- 常見應用場景
- 典型案例
- - 案例一：找零問題
  - 案例二：活動選擇問題
  - 案例三：貨倉選址問題
- 貪心算法的應用詳解
- - 霍夫曼編碼
  - 最小生成樹
  - Dijkstra最短路徑算法
- 總結

貪心算法

核心思想

貪心算法（Greedy Algorithm）是一種在每一步選擇中都采取在當前狀態下最優的選擇，從而希望以這種方式能夠達到全局最優解的一種算法思想。貪心算法并不總是能得到全局最優解，但在一些問題中，它能產生出足夠好的解，而且相對簡單高效。

貪心算法的基本思想是通過一系列局部最優的選擇，希望最終達到全局最優。在每一步，貪心算法會選擇當前狀態下的最優解，而不考慮當前選擇對以后的影響。這與動態規劃的思想不同，動態規劃考慮到每一步的選擇對于整體解的影響，而做出相應的決策。

貪心算法通常適用于滿足兩個條件的問題：

最優子結構性質： 當一個問題的最優解包含其子問題的最優解時，稱該問題具有最優子結構性質。
貪心選擇性質： 通過局部最優選擇，期望能夠達到全局最優。

一旦一個問題可以通過貪心算法求解，那么貪心算法一般會比其他算法更加高效。然而，需要注意的是，并非所有問題都滿足貪心選擇性質和最優子結構性質。

常見應用場景

霍夫曼編碼：用于數據壓縮，為高頻字符分配短編碼、低頻字符分配長編碼，減少整體數據量。
活動選擇問題：選擇一組互不相容的活動，使得參與的活動數最大。
最小生成樹：如Kruskal和Prim算法，用于在加權連通圖中找到權值之和最小的生成樹。
Dijkstra最短路徑算法：求解單源最短路徑問題，從起始點開始，每次遍歷到距離最近且未訪問過的頂點的鄰接節點。
貨倉選址問題：在一維數軸上為多個商店選擇貨倉位置，使得總距離最小。

在使用貪心算法時，必須確保貪心選擇的局部最優解能夠推導出全局最優解，否則可能得不到最優解。

典型案例

案例一：找零問題

問題描述：假設你是柜臺售貨員，需要給客戶找零n元錢。你擁有無限數量的1元、2元、5元、10元、20元、50元面額的硬幣/紙幣。如何用最少數量的硬幣/紙幣來找零？

貪心策略：每次盡量用面額最大的硬幣來找零。

示例：

假設要找零的金額為 n = 36 元。

可用的硬幣面額為 1、2、5、10、20 和 50。

首先，找零最大的面額，即 50 元。但由于 50 元大于 36 元，所以不能使用。
接下來，盡量使用次大面額的硬幣，即 20 元。36 元中能用一個 20 元，剩下 16 元。
然后使用次次大面額的硬幣，即 10 元。16 元中能用一個 10 元，剩下 6 元。
繼續使用 5 元的硬幣，6 元中能用一張 5 元，剩下 1 元。
最后，用 1 元的硬幣找零 1 元。

這樣，用 20 元、10 元、5 元和 1 元的硬幣一共找零 36 元，共需要 4 枚硬幣，是最少數量的硬幣。

在這個案例中，貪心算法的貪心策略是每次都選擇當前情況下的最優解，即選擇當前可用的最大面額的硬幣。這種策略在這個特定問題中得到了最優解。但需要指出的是，對于不同的面額組合和要求找零的金額，貪心算法并不總是能夠得到最優解。

代碼實現：

#include <stdio.h>
void findChange(int amount) {int money[] = { 50, 20, 10, 5, 2, 1 };int num = sizeof(money) / sizeof(money[0]);printf("找零 %d :\n", amount);for (int i = 0; i < num; ++i) {int current = money[i];int numNotes = amount / current;if (numNotes > 0) {printf("%d 張 %d 塊\n", numNotes, current);amount = amount % current;}}
}
int main() {int amount = 46;findChange(amount);return 0;
}

復雜度分析：

時間復雜度：O(1)，因為面額種類有限。
空間復雜度：O(1)。

注意：對于某些面額組合，貪心算法不一定能得到最優解。

案例二：活動選擇問題

問題描述：有n個活動，每個活動有開始時間和結束時間，要求選擇最多數量的互不重疊活動。

貪心策略：每次選擇結束時間最早且不與已選活動沖突的活動。

偽代碼：

1. 按活動結束時間從小到大排序
2. 依次選擇與已選活動不沖突的下一個活動

代碼實現：

#include <stdio.h>
#include <stdlib.h>// 定義活動結構體，包含開始時間和結束時間
typedef struct {int start;  // 活動開始時間int end;    // 活動結束時間int index;  // 活動編號（可選，用于標識活動）
} Activity;// 比較函數，用于按活動結束時間排序
int cmp(const void *a, const void *b) {return ((Activity*)a)->end - ((Activity*)b)->end;
}// 貪心算法選擇活動函數
void selectActivities(Activity acts[], int n) {// 按活動結束時間從小到大排序qsort(acts, n, sizeof(Activity), cmp);// 選擇第一個活動（結束時間最早的活動）int count = 0;  // 記錄選擇的活動數量int lastEnd = -1;  // 上一個選擇的活動的結束時間，初始為-1printf("選擇的活動：\n");for (int i = 0; i < n; ++i) {// 如果當前活動的開始時間大于等于上一個選擇的活動的結束時間，則選擇該活動if (acts[i].start >= lastEnd) {count++;printf("活動%d: [%d, %d]\n", acts[i].index, acts[i].start, acts[i].end);lastEnd = acts[i].end;  // 更新最后選擇的活動的結束時間}}printf("共選擇了 %d 個活動\n", count);
}// 主函數，演示活動選擇問題
int main() {// 示例活動集合，每個活動有開始時間、結束時間和編號Activity activities[] = {{1, 4, 1},   // 活動1：開始時間1，結束時間4{3, 5, 2},   // 活動2：開始時間3，結束時間5{0, 6, 3},   // 活動3：開始時間0，結束時間6{5, 7, 4},   // 活動4：開始時間5，結束時間7{3, 9, 5},   // 活動5：開始時間3，結束時間9{5, 9, 6},   // 活動6：開始時間5，結束時間9{6, 10, 7},  // 活動7：開始時間6，結束時間10{8, 11, 8},  // 活動8：開始時間8，結束時間11{8, 12, 9},  // 活動9：開始時間8，結束時間12{2, 14, 10}, // 活動10：開始時間2，結束時間14{12, 16, 11} // 活動11：開始時間12，結束時間16};int n = sizeof(activities) / sizeof(activities[0]);printf("共有 %d 個活動\n\n", n);// 調用貪心算法選擇活動selectActivities(activities, n);return 0;
}

復雜度分析：

時間復雜度：O(nlogn)，主要是排序的時間復雜度。
空間復雜度：O(1)，除了存儲活動的數組外，只需要常數級的額外空間。

貪心策略正確性證明：

活動選擇問題的貪心策略是選擇結束時間最早的活動，這一策略的正確性可以通過反證法證明：

假設最優解集合為S，包含k個活動，按結束時間排序后為{a?, a?, …, a?}。如果a?不是所有活動中結束時間最早的活動，那么存在活動b，其結束時間早于a?。

我們可以用b替換S中的a?，得到新的解集合S’ = {b, a?, …, a?}。由于b的結束時間早于a?，b不會與a?, …, a?沖突，因此S’也是一個可行解，且|S’| = |S|。這說明選擇結束時間最早的活動不會導致最優解的丟失。

通過歸納法，可以證明每次選擇當前結束時間最早的、與已選活動不沖突的活動，最終能得到最優解。

應用場景：

活動選擇問題在實際中有廣泛應用，例如：

會議室安排：在有限的會議室中安排盡可能多的會議
課程表設計：在固定教室中安排盡可能多的課程
任務調度：在單處理器上安排盡可能多的任務

案例三：貨倉選址問題

問題描述：在一條數軸上有N家商店，它們的坐標分別為A1～AN。現在需要在數軸上建立一家貨倉，每天清晨，從貨倉到每家商店都要運送一車商品。為了提高效率，求把貨倉建在何處，可以使得貨倉到每家商店的距離之和最小。

貪心策略：將貨倉建在所有商店坐標的中位數位置。

代碼實現：

#include <stdio.h>
#include <stdlib.h>// 比較函數，用于排序
int compare(const void* a, const void* b) {return (*(int*)a - *(int*)b);
}// 計算距離之和的函數
int sum(int warehouse, int* shops, int n) {int totalDistance = 0;for (int i = 0; i < n; ++i) {totalDistance += abs(warehouse - shops[i]);}return totalDistance;
}// 找到貨倉位置的函數
int find(int* shops, int n) {// 將商店坐標排序qsort(shops, n, sizeof(int), compare);// 中位數位置int warehousePosition = shops[n / 2];return warehousePosition;
}int main() {int n;printf("輸入商店的數量：");scanf("%d", &n);int* shops = (int*)malloc(n * sizeof(int));printf("輸入商店的坐標：");for (int i = 0; i < n; ++i) {scanf("%d", &shops[i]);}int pos = find(shops, n);int total = sum(pos, shops, n);printf("把貨倉建在坐標 %d 處，使得貨倉到每家商店的距離之和最小，為：%d\n", pos, total);free(shops);return 0;
}