基础算法：贪心算法
常用的基础算法之一，用于求最优解，但不一定能得到全局最优解
0x00 算法概述
贪心算法是在求解问题的时候，总是选择当前最优的解，不考虑全局最优解。
选择当前最优的解的方法称为贪心策略，贪心策略必须保证拆分的子问题必须是无后效性的（当前状态不会影响之前的状态）。
0x01 解题步骤
- 分析问题，抽象成数学模型
- 将问题拆分成多个子问题（子问题必须是无后效性的）
- 求解每一个子问题，得到子问题的局部最优解
- 合并子问题的最优解，得出全局解
贪心算法的核心就是找贪心策略，然后证明贪心策略中子问题的最优解一定会得到全局最优解。
0x02 实现方式
适用场景：
- 单源最短路经问题
- 最小生成树问题
- 可任意分割的背包问题。如果不可以任意分割，就需要用动态规划求解。
- 某些情况下，即使贪心算法不能得到整体最优解，但其最终结果近似于最优解。
贪心算法的实现很简单，只要能找到贪心策略，代码很容易写出来。
参考：