青少年編程與數學 02-018 C++數據結構與算法 16課題、貪心算法
- 一、貪心算法的基本概念
- 定義
- 組成部分
- 二、貪心算法的工作原理
- 三、貪心算法的優點
- 四、貪心算法的缺點
- 五、貪心算法的應用實例
- (一)找零問題
- 問題描述:
- 貪心策略:
- 示例代碼:
- 解釋:
- (二)活動安排問題
- 問題描述:
- 貪心策略:
- 示例代碼:
- 解釋:
- (三)霍夫曼編碼
- 問題描述:
- 貪心策略:
- 示例代碼:
- 解釋:
- (四)最小生成樹(Kruskal算法)
- 問題描述:
- 貪心策略:
- 示例代碼:
- 解釋:
- 六、總結
課題摘要:
貪心算法(Greedy Algorithm)是一種在每一步選擇中都采取當前狀態下最優(即最有利)的選擇,從而希望導致結果是全局最優的算法。貪心算法并不總是能得到最優解,但它在很多問題上都能得到較好的近似解,并且通常具有較高的效率。
一、貪心算法的基本概念
定義
貪心算法在每一步選擇中都采取當前狀態下最優的選擇,從而希望導致結果是全局最優的。這種“最優”通常是根據某種局部標準來衡量的。
組成部分
- 貪心選擇性質:問題的整體最優解可以通過一系列局部最優的選擇來達到。這是貪心算法可行的基本要素。
- 最優子結構:問題的最優解包含其子問題的最優解。貪心算法通過分解問題為更小的子問題來逐步構建全局最優解。
- 貪心策略:一種用于選擇局部最優解的策略,通常基于某種特定的規則或標準。
二、貪心算法的工作原理
- 貪心選擇:在每一步選擇中,根據某種貪心策略選擇當前狀態下最優的選項。例如,在找零問題中,每次選擇面值最大的硬幣。
- 構建解:通過一系列的貪心選擇逐步構建解。每一步的選擇都是基于當前狀態的最優選擇,而不考慮后續步驟。
- 驗證:在某些情況下,需要驗證通過貪心選擇得到的解是否滿足問題的約束條件。如果滿足,則該解是全局最優解;如果不滿足,則需要重新考慮貪心策略。
三、貪心算法的優點
- 簡單直觀:貪心算法的邏輯通常比較簡單,容易理解和實現。
- 效率高:貪心算法通常具有較高的效率,因為它不需要像動態規劃那樣存儲大量的子問題解。
- 適用性廣:貪心算法可以應用于多種問題,尤其是在組合優化問題中。
四、貪心算法的缺點
- 不能保證全局最優:貪心算法只能保證在每一步選擇中是局部最優的,但不能保證最終結果是全局最優的。例如,在某些背包問題中,貪心算法可能無法找到最優解。
- 適用范圍有限:貪心算法只能應用于具有貪心選擇性質和最優子結構的問題。對于不滿足這些條件的問題,貪心算法可能無法得到正確的解。
五、貪心算法的應用實例
(一)找零問題
問題描述:
給定一組硬幣面值和一個金額,求用最少的硬幣數湊成該金額。
貪心策略:
每次選擇面值最大的硬幣。
示例代碼:
#include <iostream>
#include <vector>
#include <algorithm>int coin_change(const std::vector<int>& coins, int amount) {std::vector<int> sorted_coins = coins;std::sort(sorted_coins.rbegin(), sorted_coins.rend());int count = 0;for (int coin : sorted_coins) {while (amount >= coin) {amount -= coin;count++;}}return amount == 0 ? count : -1;
}
解釋:
每次選擇面值最大的硬幣,直到金額為0。
(二)活動安排問題
問題描述:
給定一組活動的開始時間和結束時間,求最多可以安排多少個不沖突的活動。
貪心策略:
每次選擇結束時間最早的活動。
示例代碼:
#include <iostream>
#include <vector>
#include <algorithm>int activity_selection(const std::vector<int>& start, const std::vector<int>& finish) {std::vector<std::pair<int, int>> activities;for (size_t i = 0; i < start.size(); ++i) {activities.emplace_back(start[i], finish[i]);}std::sort(activities.begin(), activities.end(), [](const auto& a, const auto& b) {return a.second < b.second;});int count = 0;int last_finish = 0;for (const auto& activity : activities) {if (activity.first >= last_finish) {count++;last_finish = activity.second;}}return count;
}
解釋:
每次選擇結束時間最早的活動,確保后續活動不沖突。
(三)霍夫曼編碼
問題描述:
給定一組字符及其頻率,求一種最優的編碼方式,使得編碼后的字符串長度最短。
貪心策略:
每次選擇頻率最小的兩個字符合并。
示例代碼:
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>struct Node {char ch;int freq;Node* left;Node* right;Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};struct Compare {bool operator()(Node* left, Node* right) {return left->freq > right->freq;}
};void build_codes(Node* root, const std::string& prefix, std::unordered_map<char, std::string>& codes) {if (!root) return;if (root->ch != '\0') {codes[root->ch] = prefix;}build_codes(root->left, prefix + "0", codes);build_codes(root->right, prefix + "1", codes);
}std::unordered_map<char, std::string> huffman_encoding(const std::unordered_map<char, int>& frequencies) {std::priority_queue<Node*, std::vector<Node*>, Compare> pq;for (const auto& entry : frequencies) {pq.push(new Node(entry.first, entry.second));}while (pq.size() > 1) {Node* left = pq.top(); pq.pop();Node* right = pq.top(); pq.pop();Node* merged = new Node('\0', left->freq + right->freq);merged->left = left;merged->right = right;pq.push(merged);}std::unordered_map<char, std::string> codes;build_codes(pq.top(), "", codes);return codes;
}int main() {std::unordered_map<char, int> frequencies = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};auto codes = huffman_encoding(frequencies);for (const auto& entry : codes) {std::cout << entry.first << ": " << entry.second << std::endl;}return 0;
}
解釋:
通過構建霍夫曼樹,為每個字符分配最優的編碼。
(四)最小生成樹(Kruskal算法)
問題描述:
給定一個加權無向圖,求一個最小生成樹。
貪心策略:
每次選擇權重最小的邊,確保不形成環。
示例代碼:
#include <iostream>
#include <vector>
#include <algorithm>class UnionFind {
public:UnionFind(int n) : parent(n) {for (int i = 0; i < n; ++i) {parent[i] = i;}}int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}void union_sets(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {parent[rootX] = rootY;}}private:std::vector<int> parent;
};std::vector<std::tuple<int, int, int>> kruskal(const std::vector<std::tuple<int, int, int>>& edges, int n) {std::vector<std::tuple<int, int, int>> mst;UnionFind uf(n);std::vector<std::tuple<int, int, int>> sorted_edges(edges.begin(), edges.end());std::sort(sorted_edges.begin(), sorted_edges.end(), [](const auto& a, const auto& b) {return std::get<2>(a) < std::get<2>(b);});for (const auto& edge : sorted_edges) {int u = std::get<0>(edge);int v = std::get<1>(edge);int weight = std::get<2>(edge);if (uf.find(u) != uf.find(v)) {uf.union_sets(u, v);mst.push_back(edge);}}return mst;
}int main() {std::vector<std::tuple<int, int, int>> edges = {{0, 1, 2}, {1, 2, 3}, {2, 3, 1}, {3, 0, 4}, {0, 2, 5}};int n = 4;auto mst = kruskal(edges, n);for (const auto& edge : mst) {std::cout << std::get<0>(edge) << " - " << std::get<1>(edge) << " : " << std::get<2>(edge) << std::endl;}return 0;
}
解釋:
通過選擇權重最小的邊,逐步構建最小生成樹。
六、總結
貪心算法是一種簡單而高效的算法設計策略,適用于具有貪心選擇性質和最優子結構的問題。它通過在每一步選擇中采取當前狀態下最優的選擇,逐步構建解。雖然貪心算法不能保證總是得到全局最優解,但在很多實際問題中都能得到較好的近似解。在使用貪心算法時,需要仔細分析問題的性質,確保貪心策略的有效性。