初学贪心算法

一、基本概念

1. 核心思想
   局部最优 → 全局最优（通过每一步的贪心选择，希望达到全局最优解）

2. 适用条件
   贪心选择性质：每一步的局部最优选择能导致全局最优解。
   最优子结构：问题的最优解包含子问题的最优解。

3. 与动态规划的区别
   贪心算法不回溯，一旦做出选择就不再改变。
   动态规划会保存子问题的解，通常用于有重叠子问题和最优子结构，但贪心选择不成立的情况

二、经典问题类型与示例

1.区间问题

• 区间调度（最大不相交区间）
  按结束时间排序，每次选择结束最早且不与已选区间重叠的区间。
• 区间覆盖
  选择覆盖起点且结束最远的区间，逐步推进。

2.分配问题

• 分配饼干
  将最小的饼干分配给胃口最小的孩子。
• 任务调度
  按结束时间或耗时排序贪心。

3.背包问题（部分背包）

• 按价值/重量比降序贪心选择（仅适用于物品可分割的情况）。

4.哈夫曼编码

• 每次合并频率最小的两个节点，构造最优前缀码。

5.最短路径（Dijkstra算法）

• 每次选择当前距离起点最近的节点，更新邻接节点距离。

6.最小生成树

• Prim算法：每次添加距离当前树最近的节点。
• Kruskal算法：按边权从小到大添加，使用并查集避免环。

7.硬币找零问题

• 在硬币面额具备贪心性质时（如人民币1、5、10元），从大到小选择。
• 注意：并非所有面额体系都适用贪心（如{1, 3, 4}元找6元，贪心选4+1+1不如3+3）

三、贪心算法的局限性

1. 不保证全局最优
   如果问题不具备贪心选择性质，贪心可能得到次优解（如一般背包问题不可分割时）。

2. 需要问题具有特定结构
   必须仔细分析问题是否满足贪心条件。

3. 证明困难
   有时贪心策略看似显然，但严格证明复杂