贪心算法原理
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优的选择（局部最优），从而期望得到全局最优解的算法策略。
基本原理
一般应用于求解最优化问题，在每个子结构处求解局部最优解。如果证明所有局部最优解的集合恰好构成全局最优解，则可用贪心法求得整体最优解。
与动态规划的对比
贪心法对优化子结构有更强的要求，与动态规划能解决的问题有所重叠也有所区分。各自都存在只有一种算法可解的问题，不存在谁包含谁的关系。
适用条件
- 贪心选择性质：通过局部最优选择可以得到全局最优解
- 最优子结构：问题的最优解包含子问题的最优解
链接到
- 上一个知识点：无（本章第一个知识点）
- 下一个知识点：3.2 活动选择问题