【greedy】在计算机科学与算法设计中，“Greedy”（贪心）是一种常见的策略，用于解决优化问题。它通过每一步选择当前状态下最优的局部解，期望最终得到全局最优解。虽然贪心算法并不总能保证正确性，但在许多实际问题中表现良好，且具有较高的效率。
一、贪心算法概述
贪心算法的核心思想是“每一步都做出当前条件下最优的选择”，而不考虑未来可能带来的影响。这种策略通常适用于以下类型的问题：
- 可以分解为多个步骤
- 每一步的选择不影响后续步骤的最优性
- 局部最优解能够导向全局最优解
贪心算法常用于如下场景：
- 图论中的最短路径问题（如Dijkstra算法）
- 最小生成树（如Prim和Kruskal算法）
- 任务调度问题
- 货币找零问题（当硬币系统满足贪心条件时）
二、贪心算法的优缺点
| 优点 | 缺点 |
| 算法简单，易于实现 | 无法保证全局最优解 |
| 时间复杂度低，运行速度快 | 对输入数据敏感，需满足特定条件 |
| 适合大规模数据处理 | 不适用于所有类型的问题 |
三、常见贪心算法实例
| 问题类型 | 算法名称 | 应用场景 | 是否适用贪心 |
| 最小生成树 | Kruskal算法 | 图的边权最小连接 | ✅ |
| 最小生成树 | Prim算法 | 图的边权最小连接 | ✅ |
| 单源最短路径 | Dijkstra算法 | 图中单点到其他点的最短路径 | ✅ |
| 货币找零 | 贪心算法 | 满足特定面值的货币系统 | ✅/❌ |
| 任务调度 | 任务选择算法 | 按截止时间或收益排序 | ✅ |
| 区间调度 | 区间调度算法 | 选择最多不重叠区间 | ✅ |
四、贪心算法的局限性
尽管贪心算法在许多情况下表现良好，但它并不适用于所有问题。例如：
- 背包问题：如果物品不能分割，则贪心算法无法得到最优解。
- 某些图问题：如旅行商问题（TSP），贪心算法可能给出较差的结果。
因此，在使用贪心算法前，需要仔细分析问题的性质，并验证其是否适用于该策略。
五、总结
贪心算法是一种基于“局部最优”的策略，适用于一些结构清晰、可分解的问题。它的优势在于实现简单、效率高，但其局限性也十分明显，尤其是在无法保证全局最优的情况下。因此，理解问题的本质并判断是否适合使用贪心算法，是成功应用该方法的关键。
