贪心算法
基本概念：
又称贪婪算法，登山算法，根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。在解的范围下，可以采用枚举和递归策略，找出所有的解，一一比较它们，最后找到最优解，但是当解的范围特别大时，蛮力枚举或递归搜索策略效率非常低，可能在短时间内无法找到问题的解。这时，可以考虑贪心算法选取那些最可能达解的情况来考虑。“贪婪”可以理解成以逐步的局部最优，达到最终的全局最优。
特征：
- 最优子结构性质：即当一个问题的最优解包含其子问题的最优解时，称此问题具有最优解子结构，也称此问题满足最优性原理。
- 贪心选择性质：指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。（后续讲的到的动态规划和贪心算法的区别：前者是自底向上，后者是自顶向下）
基本步骤：
- 从问题的某个初始解出发
- 采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模
- 将所有部分解综合起来，得到问题的最终解
借题理解
Case：用最少货币数找零
假设有面值 5元，2元，1元，5角，2角，1角的货币，需要找给顾客4元6角现金，但必须要求付出货币数量最少。
问题解：
首先我们要找零4元6角，我们面值最大的一张是5元，不符合要求，所以只能用2元一张，剩下2元6角，那么再取一张2元，只剩6角。虽然我们能够找3张2角解决，但是题目要求最少货币数。那只能找再找出一张面值不超过6角的货币，即5角。最后找到一张不超过1角的面值货币，即1角。因此，我们总共付出4张货币（2元两张，一张5角，一张1角）
问题总结：
在付款问题中，每一步的贪心选择中，在不超过应付金额的条件下，只能选择面值最大的货币，而不去考虑在后面看这种选择是否合理，而且它还不会改变决定，一旦选择了一张货币，就永远选定，也就是无后性
求解问题中应该考虑：
- 候选集合：为了构造问题的解决方案，有一个候选集合作为问题的可能解（即问题的最终解均取自候选集合）例如：在找零问题中，各种面值货币构成的候选集合（5元，2元，1元，5角，2角，1角）
- 解集合：随着贪心选择的进行，解集合不断扩展，直到构成一个满足问题的完整解。例如：以付出的货币构成解集合（只能用2元一张，剩下2元6角，那么再取一张2元，只剩6角。）
- 解决函数：检查解集合是否构成问题的完整解。例如：在找零问题中，解决函数是已付出货币金额恰好等于应付款
- 选择函数（核心）：即贪心策略，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如：贪心策略就是在候选集合中选择面值最大的货币
- 可行函数：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如：可行函数是每一步选择货币和已找零货币相加不超过找零总数（零4元6角）
总结
贪心算法其实在数据结构中也常见到：霍夫曼树，构造最小生成树的Prim算法和Kruskal算法。贪心算法没有固定的算法框架，核心在与贪心策略的选择，一定要注意的是选择的贪心策略要具有无后性（即某阶段的状态确定过后，不受这个状态以后的决策影响，也就是说某转态以后的过程不会影响到以前的状态） ，只与当前状态有关。因此，在使用贪心算法时，对所采用的贪心策略一定要仔细分析是否具有无后性。特别注意点：贪心算法是局部最优，最后的整体不一定最优的，和后面要说的动态规划有区别。但它通常能获得近似最优解。
