貪心算法詳解及C++實現

1. 什么是貪心算法

貪心算法（Greedy Algorithm）是一種在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是全局最好或最優的算法策略。

貪心算法與動態規劃不同在于它對每個子問題的解決方案都做出選擇，不能回退。動態規劃則會保存以前的運算結果，并根據以前的結果對當前進行選擇，有回退功能。

2. 貪心算法的基本要素

貪心算法適用的問題通常具有以下兩個性質：

1. 貪心選擇性質：所求問題的整體最優解可以通過一系列局部最優的選擇來達到。
2. 最優子結構：問題的最優解包含其子問題的最優解。

3. 貪心算法的基本步驟

1. 建立數學模型來描述問題
2. 把求解的問題分成若干個子問題
3. 對每個子問題求解，得到子問題的局部最優解
4. 把子問題的解合并成原問題的一個解

4. 經典貪心算法問題

4.1 找零錢問題

問題描述：假設有不同面額的硬幣 coins = [1, 2, 5, 10, 20, 50, 100]，我們需要用最少數量的硬幣來找零 n 元。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<int> coinChange(int amount, vector<int>& coins) {sort(coins.rbegin(), coins.rend()); // 從大到小排序vector<int> result;for (int coin : coins) {while (amount >= coin) {amount -= coin;result.push_back(coin);}}if (amount != 0) {cout << "無法正好找零" << endl;return {};}return result;
}int main() {vector<int> coins = {1, 2, 5, 10, 20, 50, 100};int amount = 93;vector<int> result = coinChange(amount, coins);cout << "找零" << amount << "元需要的硬幣為：";for (int coin : result) {cout << coin << " ";}cout << endl;return 0;
}

4.2 活動選擇問題

問題描述：給定一組活動，每個活動都有一個開始時間和結束時間，選擇最大的互不沖突的活動集合。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;struct Activity {int start;int end;
};bool compareActivity(Activity a, Activity b) {return a.end < b.end;
}vector<Activity> selectActivities(vector<Activity>& activities) {sort(activities.begin(), activities.end(), compareActivity);vector<Activity> selected;selected.push_back(activities[0]);int lastEnd = activities[0].end;for (int i = 1; i < activities.size(); i++) {if (activities[i].start >= lastEnd) {selected.push_back(activities[i]);lastEnd = activities[i].end;}}return selected;
}int main() {vector<Activity> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7},{3, 8}, {5, 9}, {6, 10}, {8, 11},{8, 12}, {2, 13}, {12, 14}};vector<Activity> result = selectActivities(activities);cout << "選擇的活動序列為：" << endl;for (Activity act : result) {cout << "[" << act.start << ", " << act.end << "] ";}cout << endl;return 0;
}

4.3 霍夫曼編碼

問題描述：霍夫曼編碼是一種用于無損數據壓縮的貪心算法，通過給出現頻率高的字符較短的編碼，出現頻率低的字符較長的編碼，來達到壓縮數據的目的。

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>using namespace std;struct HuffmanNode {char ch;int freq;HuffmanNode *left, *right;HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};struct compare {bool operator()(HuffmanNode* l, HuffmanNode* r) {return l->freq > r->freq;}
};void encode(HuffmanNode* root, string str, unordered_map<char, string> &huffmanCode) {if (root == nullptr) return;if (!root->left && !root->right) {huffmanCode[root->ch] = str;}encode(root->left, str + "0", huffmanCode);encode(root->right, str + "1", huffmanCode);
}void buildHuffmanTree(string text) {unordered_map<char, int> freq;for (char ch : text) {freq[ch]++;}priority_queue<HuffmanNode*, vector<HuffmanNode*>, compare> pq;for (auto pair : freq) {pq.push(new HuffmanNode(pair.first, pair.second));}while (pq.size() != 1) {HuffmanNode *left = pq.top(); pq.pop();HuffmanNode *right = pq.top(); pq.pop();int sum = left->freq + right->freq;HuffmanNode *node = new HuffmanNode('\0', sum);node->left = left;node->right = right;pq.push(node);}HuffmanNode* root = pq.top();unordered_map<char, string> huffmanCode;encode(root, "", huffmanCode);cout << "霍夫曼編碼表：" << endl;for (auto pair : huffmanCode) {cout << pair.first << " : " << pair.second << endl;}string encodedStr;for (char ch : text) {encodedStr += huffmanCode[ch];}cout << "編碼后的字符串：" << encodedStr << endl;
}int main() {string text = "hello world";cout << "原始字符串：" << text << endl;buildHuffmanTree(text);return 0;
}

5. 貪心算法的優缺點

優點：

1. 簡單易懂，容易實現
2. 運行效率高，時間復雜度通常較低
3. 可以作為其他算法的輔助算法

缺點：

1. 不能保證得到全局最優解
2. 適用范圍有限，只有部分問題能用貪心算法解決
3. 需要證明其正確性，有時證明較復雜

6. 貪心算法的應用場景

1. 最小生成樹（Prim和Kruskal算法）
2. 最短路徑問題（Dijkstra算法）
3. 數據壓縮（霍夫曼編碼）
4. 任務調度問題
5. 集合覆蓋問題

7. 總結

貪心算法是一種簡單而有效的算法設計技術，適用于具有貪心選擇性質和最優子結構的問題。雖然它不能解決所有優化問題，但在適用的情況下，它通常能提供高效且簡單的解決方案。理解貪心算法的原理和應用場景，對于算法學習和問題解決能力的提升都有很大幫助。

在實際應用中，我們需要仔細分析問題是否適合使用貪心算法，并驗證其正確性。當貪心算法不能得到全局最優解時，可能需要考慮動態規劃等其他方法。