貪心算法（Greedy Algorithm）：通過局部最優達成全局最優的決策策略
貪心算法是一種通過每次選擇局部最優解來期望全局最優解的算法思想。它不考慮未來的影響，僅根據當前信息做出最優選擇，適用于具有貪心選擇性質和最優子結構的問題。與動態規劃相比，貪心算法更簡單高效，但適用范圍更窄。
一、貪心算法的核心要素
-
貪心選擇性質：全局最優解可通過一系列局部最優選擇（貪心選擇）達成。即每次選擇的局部最優解，最終能累積成全局最優解。
-
最優子結構：問題的最優解包含子問題的最優解（與動態規劃相同）。
關鍵區別：
- 貪心算法：自頂向下，每次做貪心選擇后，僅留下一個子問題需要解決。
- 動態規劃：自底向上或自頂向下，需考慮所有子問題并存儲其解。
二、經典應用：活動選擇問題
問題：有n個活動，每個活動有開始時間start[i]和結束時間end[i]，求最多能參加的不重疊活動數量。
貪心策略：每次選擇最早結束的活動，為剩余活動留出更多時間。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 活動結構：開始時間和結束時間
struct Activity {int start;int end;
};// 按結束時間排序
bool compare(const Activity& a, const Activity& b) {return a.end < b.end;
}// 選擇最多不重疊活動
int maxActivities(vector<Activity>& activities) {if (activities.empty()) return 0;// 1. 按結束時間排序（貪心選擇的前提）sort(activities.begin(), activities.end(), compare);int count = 1; // 至少選擇第一個活動int lastEnd = activities[0].end;// 2. 依次選擇不重疊的活動for (int i = 1; i < activities.size(); i++) {// 若當前活動開始時間 >= 上一個活動結束時間，可選擇if (activities[i].start >= lastEnd) {count++;lastEnd = activities[i].end;}}return count;
}int main() {vector<Activity> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}};cout << "最多可參加的活動數：" << maxActivities(activities) << endl; // 輸出4（如{1,4}, {5,7}, {8,11}, {12,16}）return 0;
}算法分析：
- 排序時間O(n log n)，選擇過程O(n)，總時間O(n log n)。
- 正確性：通過數學歸納法可證明，選擇最早結束的活動能獲得最優解。
三、經典應用：哈夫曼編碼（Huffman Coding）
問題：為字符設計變長編碼，出現頻率高的字符用短編碼，頻率低的用長編碼，實現數據壓縮（無歧義解碼）。
貪心策略：每次選擇頻率最低的兩個節點合并為新節點，重復至只剩一個節點（哈夫曼樹），路徑左0右1即為編碼。
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;// 哈夫曼樹節點
struct HuffmanNode {char data; // 字符（葉子節點）int freq; // 頻率HuffmanNode *left, *right;HuffmanNode(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
};// 優先隊列比較器（最小堆，頻率低的節點優先）
struct Compare {bool operator()(HuffmanNode* a, HuffmanNode* b) {return a->freq > b->freq; // 小頂堆（默認是大頂堆，需反向）}
};// 遞歸生成哈夫曼編碼
void generateCodes(HuffmanNode* root, string code, unordered_map<char, string>& codes) {if (!root) return;// 葉子節點：記錄編碼if (!root->left && !root->right) {codes[root->data] = code.empty() ? "0" : code; // 處理只有一個字符的情況return;}// 左子樹加"0"，右子樹加"1"generateCodes(root->left, code + "0", codes);generateCodes(root->right, code + "1", codes);
}// 構建哈夫曼樹并生成編碼
unordered_map<char, string> huffmanCoding(unordered_map<char, int>& freq) {// 1. 創建葉子節點，加入最小堆priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;for (auto& p : freq) {minHeap.push(new HuffmanNode(p.first, p.second));}// 2. 合并節點直至只剩一個根節點while (minHeap.size() > 1) {// 取出兩個頻率最低的節點HuffmanNode* left = minHeap.top(); minHeap.pop();HuffmanNode* right = minHeap.top(); minHeap.pop();// 合并為新節點（數據用特殊符號，頻率為兩者之和）HuffmanNode* merged = new HuffmanNode('$', left->freq + right->freq);merged->left = left;merged->right = right;minHeap.push(merged);}// 3. 生成編碼unordered_map<char, string> codes;generateCodes(minHeap.top(), "", codes);return codes;
}int main() {unordered_map<char, int> freq = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};auto codes = huffmanCoding(freq);cout << "哈夫曼編碼：" << endl;for (auto& p : codes) {cout << p.first << ": " << p.second << endl;}// 輸出示例（可能因實現細節略有不同）：// f: 0// c: 100// d: 101// a: 1100// b: 1101// e: 111return 0;
}算法分析：
- 時間復雜度O(n log n)（n個節點，每次堆操作O(log n)）。
- 正確性：哈夫曼編碼是最優前綴碼，總編碼長度最短。
四、經典應用：零錢兌換（貪心適用場景）
問題：用最少的硬幣湊出指定金額，硬幣面額為{25, 10, 5, 1}。
貪心策略：每次選擇最大面額的硬幣，直至金額為0。
int coinChangeGreedy(int amount, vector<int>& coins) {sort(coins.rbegin(), coins.rend()); // 面額從大到小排序int count = 0;for (int coin : coins) {while (amount >= coin) {amount -= coin;count++;}if (amount == 0) break;}return amount == 0 ? count : -1; // 無法湊出返回-1
}
局限性：僅適用于“大面額是小面額倍數”的情況（如美元硬幣）。對于{1, 3, 4}面額湊6，貪心會選4+1+1（3枚），但最優解是3+3（2枚），此時需用動態規劃。
五、貪心算法 vs 動態規劃
| 特性 | 貪心算法 | 動態規劃 |
|---|---|---|
| 決策方式 | 局部最優（僅看當前） | 全局最優（考慮所有子問題） |
| 子問題關系 | 貪心選擇后僅一個子問題 | 需解決多個重疊子問題 |
| 時間復雜度 | 通常更低（如O(n log n)） | 較高（如O(n2)或O(nW)） |
| 適用場景 | 具有貪心選擇性質的問題 | 所有具有最優子結構的問題 |
| 典型例子 | 活動選擇、哈夫曼編碼、最小生成樹 | 背包問題、LCS、最長遞增子序列 |
六、貪心算法的優缺點
優點：
- 實現簡單，時間效率高（通常為線性或線性對數級）。
- 空間開銷小（無需存儲子問題解）。
缺點：
- 適用范圍有限（僅能解決具有貪心選擇性質的問題）。
- 無法回溯，一旦做出選擇就無法更改，可能錯過全局最優解。
七、如何判斷問題是否適合貪心算法
-
嘗試構造反例：假設貪心策略不成立，能否找到反例？
例如：零錢兌換問題中，若存在非倍數面額，貪心可能失效。 -
證明貪心選擇性質：
假設全局最優解中不包含貪心選擇的元素，能否通過替換證明存在更優解？若不能，則貪心策略有效。 -
驗證最優子結構：問題的最優解包含子問題的最優解。
總結
貪心算法是一種直觀高效的算法思想，通過每次選擇局部最優解來逼近全局最優解。它特別適合解決資源分配、調度、編碼等具有貪心選擇性質的問題，如活動選擇、哈夫曼編碼、最小生成樹（Kruskal和Prim算法）等。
盡管貪心算法的適用范圍不如動態規劃廣泛，但其簡單性和高效性使其在許多場景中成為首選。掌握貪心算法的關鍵在于：
- 識別問題是否具有貪心選擇性質和最優子結構。
- 設計合理的貪心策略（如按結束時間排序、選最大面額等）。
- 通過數學證明或反例驗證策略的正確性。
在實際開發中，貪心算法常與其他算法結合使用（如貪心+動態規劃），以平衡效率和通用性。
)
