贪心算法（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(n²)或O(nW)） |
| 适用场景 | 具有贪心选择性质的问题 | 所有具有最优子结构的问题 |
| 典型例子 | 活动选择、哈夫曼编码、最小生成树 | 背包问题、LCS、最长递增子序列 |
六、贪心算法的优缺点
优点：
- 实现简单，时间效率高（通常为线性或线性对数级）。
- 空间开销小（无需存储子问题解）。
缺点：
- 适用范围有限（仅能解决具有贪心选择性质的问题）。
- 无法回溯，一旦做出选择就无法更改，可能错过全局最优解。
七、如何判断问题是否适合贪心算法
-
尝试构造反例：假设贪心策略不成立，能否找到反例？
例如：零钱兑换问题中，若存在非倍数面额，贪心可能失效。 -
证明贪心选择性质：
假设全局最优解中不包含贪心选择的元素，能否通过替换证明存在更优解？若不能，则贪心策略有效。 -
验证最优子结构：问题的最优解包含子问题的最优解。
总结
贪心算法是一种直观高效的算法思想，通过每次选择局部最优解来逼近全局最优解。它特别适合解决资源分配、调度、编码等具有贪心选择性质的问题，如活动选择、哈夫曼编码、最小生成树（Kruskal和Prim算法）等。
尽管贪心算法的适用范围不如动态规划广泛，但其简单性和高效性使其在许多场景中成为首选。掌握贪心算法的关键在于：
- 识别问题是否具有贪心选择性质和最优子结构。
- 设计合理的贪心策略（如按结束时间排序、选最大面额等）。
- 通过数学证明或反例验证策略的正确性。
在实际开发中，贪心算法常与其他算法结合使用（如贪心+动态规划），以平衡效率和通用性。
)
