贪心算法

每步选择当前最优（局部最优），期望积累得到全局最优。

核心特征

• 贪心选择性质：局部最优选择能导致全局最优
• 最优子结构：问题的最优解包含子问题的最优解

与动态规划对比

维度	贪心	动态规划
决策方式	每步仅做一次局部最优选择	考虑所有可能，存储中间结果
回溯	不可回溯	隐含遍历所有子问题组合
效率	更高（ 典型）	较低（依赖状态空间大小）
适用条件	需严格证明贪心选择性质	只需最优子结构

典型问题

• 找零问题：每次选面额最大的硬币
• 活动选择：每次选结束最早的活动
• Huffman 编码：每次合并频率最小的两个节点
• 最小生成树：Prim、Kruskal 算法