什么是 C++ 贪心算法？
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法策略。
简单来说，贪心算法就像我们平时说的“只顾眼前利益”——每一步都选看起来最好的，不去考虑长远影响。虽然这种策略不一定总能得到全局最优解，但对于很多问题，贪心算法确实能高效地找到最优解。
贪心算法的特点
- 局部最优选择：每一步都选择当前看起来最好的选项。
- 不可回溯：一旦做出选择，就不会再回头改变。
- 高效：通常时间复杂度较低，因为不需要考虑所有可能性。
- 不一定全局最优：贪心算法得到的不一定是全局最优解，需要证明其正确性。
贪心算法的适用场景
贪心算法适用于具有“贪心选择性质”和“最优子结构”的问题：
- 活动选择问题：选择最多的互不冲突的活动。
- 找零钱问题：用最少的硬币凑出指定金额（硬币面额满足特定条件时）。
- 哈夫曼编码：数据压缩中的最优前缀编码。
- 最小生成树：Prim 算法和 Kruskal 算法。
- 单源最短路径：Dijkstra 算法。
贪心算法的基本步骤
- 建立数学模型：将问题抽象化。
- 选择贪心策略：确定每一步如何选择“最优”选项。
- 证明贪心选择性质：证明局部最优选择能导致全局最优解。
- 实现算法：编写代码实现。
- 分析复杂度：评估时间复杂度和空间复杂度。
简单示例：找零钱问题
假设我们有面额为 1、5、10、25 的硬币，要找出 41 分钱，如何使用最少的硬币？
贪心策略：每次选择面额最大的硬币，且不超过剩余金额。
#include <iostream> #include <vector> using namespace std; int main() { vector<int> coins = {25, 10, 5, 1}; // 硬币面额，从大到小排序 int amount = 41; // 要找的金额 int count = 0; // 硬币数量 cout << "找零 " << amount << " 分：" << endl; for (int coin : coins) { while (amount >= coin) { amount -= coin; count++; cout << "使用一枚 " << coin << " 分硬币，剩余 " << amount << " 分" << endl; } } cout << "总共使用 " << count << " 枚硬币" << endl; return 0; }贪心算法的优缺点
| 优点 | 缺点 |
|---|---|
| 1. 简单易懂，容易实现 | 1. 不一定能得到全局最优解 |
| 2. 运行效率高，时间复杂度低 | 2. 需要证明正确性，有时证明较难 |
| 3. 适用于实时系统 | 3. 适用范围有限，不是所有问题都适用 |
如何判断是否能用贪心算法？
可以问自己两个问题：
- 贪心选择性质：每一步的局部最优选择能导致全局最优解吗？
- 最优子结构：问题的最优解包含子问题的最优解吗？
如果两个问题的答案都是“是”，那么这个问题很可能适合用贪心算法解决。
总结
贪心算法是一种简单高效的算法设计策略，它通过每一步的局部最优选择来尝试达到全局最优。虽然它不一定适用于所有问题，但对于满足贪心选择性质和最优子结构的问题，贪心算法往往是首选方案。
学习贪心算法时，要多做练习，理解各种经典问题的贪心策略，并学会证明贪心算法的正确性。
