贪心

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法策略。

贪心算法的特点

1. 局部最优选择：每一步都做出在当前看来最好的选择
2. 不可回退：一旦做出选择，就不能返回重新选择
3. 简单高效：实现相对简单，执行效率通常较高

贪心算法的应用场景

1. 找零钱问题
2. 活动选择问题
3. 区间调度问题
4. 最小生成树（Prim算法、Kruskal算法）
5. 哈夫曼编码

贪心算法的解题步骤

1. 将问题分解为若干个子问题
2. 找出适合的贪心策略
3. 求解每个子问题的最优解
4. 将局部最优解堆叠成全局最优解

贪心算法的优缺点

优点

• 简单直观
• 解题速度快
• 适用于子问题相对独立的场景

缺点

• 不能保证求得的最后解是最优的
• 不能用来解决所有问题

注意事项

1. 使用贪心算法前，需要证明贪心策略的正确性
2. 贪心算法不是对所有问题都适用
3. 有时贪心算法可能只能得到近似最优解