一、基本概念
核心思想
局部最优 → 全局最优（通过每一步的贪心选择，希望达到全局最优解）适用条件
贪心选择性质：每一步的局部最优选择能导致全局最优解。
最优子结构：问题的最优解包含子问题的最优解。与动态规划的区别
贪心算法不回溯，一旦做出选择就不再改变。
动态规划会保存子问题的解，通常用于有重叠子问题和最优子结构，但贪心选择不成立的情况
二、经典问题类型与示例
1.区间问题
- 区间调度（最大不相交区间）
按结束时间排序，每次选择结束最早且不与已选区间重叠的区间。 - 区间覆盖
选择覆盖起点且结束最远的区间，逐步推进。
2.分配问题
- 分配饼干
将最小的饼干分配给胃口最小的孩子。 - 任务调度
按结束时间或耗时排序贪心。
3.背包问题（部分背包）
- 按价值/重量比降序贪心选择（仅适用于物品可分割的情况）。
4.哈夫曼编码
- 每次合并频率最小的两个节点，构造最优前缀码。
5.最短路径（Dijkstra算法）
- 每次选择当前距离起点最近的节点，更新邻接节点距离。
6.最小生成树
- Prim算法：每次添加距离当前树最近的节点。
- Kruskal算法：按边权从小到大添加，使用并查集避免环。
7.硬币找零问题
- 在硬币面额具备贪心性质时（如人民币1、5、10元），从大到小选择。
- 注意：并非所有面额体系都适用贪心（如{1, 3, 4}元找6元，贪心选4+1+1不如3+3）
三、贪心算法的局限性
不保证全局最优
如果问题不具备贪心选择性质，贪心可能得到次优解（如一般背包问题不可分割时）。需要问题具有特定结构
必须仔细分析问题是否满足贪心条件。证明困难
有时贪心策略看似显然，但严格证明复杂
)
