青少年编程与数学 02-018 C++数据结构与算法 16课题、贪心算法

课题摘要：
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法。贪心算法并不总是能得到最优解，但它在很多问题上都能得到较好的近似解，并且通常具有较高的效率。

---

一、贪心算法的基本概念

定义

贪心算法在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的。这种“最优”通常是根据某种局部标准来衡量的。

组成部分

1. 贪心选择性质：问题的整体最优解可以通过一系列局部最优的选择来达到。这是贪心算法可行的基本要素。
2. 最优子结构：问题的最优解包含其子问题的最优解。贪心算法通过分解问题为更小的子问题来逐步构建全局最优解。
3. 贪心策略：一种用于选择局部最优解的策略，通常基于某种特定的规则或标准。

二、贪心算法的工作原理

1. 贪心选择：在每一步选择中，根据某种贪心策略选择当前状态下最优的选项。例如，在找零问题中，每次选择面值最大的硬币。
2. 构建解：通过一系列的贪心选择逐步构建解。每一步的选择都是基于当前状态的最优选择，而不考虑后续步骤。
3. 验证：在某些情况下，需要验证通过贪心选择得到的解是否满足问题的约束条件。如果满足，则该解是全局最优解；如果不满足，则需要重新考虑贪心策略。

三、贪心算法的优点

1. 简单直观：贪心算法的逻辑通常比较简单，容易理解和实现。
2. 效率高：贪心算法通常具有较高的效率，因为它不需要像动态规划那样存储大量的子问题解。
3. 适用性广：贪心算法可以应用于多种问题，尤其是在组合优化问题中。

四、贪心算法的缺点

1. 不能保证全局最优：贪心算法只能保证在每一步选择中是局部最优的，但不能保证最终结果是全局最优的。例如，在某些背包问题中，贪心算法可能无法找到最优解。
2. 适用范围有限：贪心算法只能应用于具有贪心选择性质和最优子结构的问题。对于不满足这些条件的问题，贪心算法可能无法得到正确的解。

五、贪心算法的应用实例

（一）找零问题

问题描述：

给定一组硬币面值和一个金额，求用最少的硬币数凑成该金额。

贪心策略：

每次选择面值最大的硬币。

示例代码：

#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;
}

解释：

通过选择权重最小的边，逐步构建最小生成树。

六、总结

贪心算法是一种简单而高效的算法设计策略，适用于具有贪心选择性质和最优子结构的问题。它通过在每一步选择中采取当前状态下最优的选择，逐步构建解。虽然贪心算法不能保证总是得到全局最优解，但在很多实际问题中都能得到较好的近似解。在使用贪心算法时，需要仔细分析问题的性质，确保贪心策略的有效性。