贪心算法
有人说贪心算法很简单，你我其实都很贪，根本不用学；
有人说贪心算法很复杂，这世上会贪的人太多了，哪轮得到你我？
概念
贪心是一种在每次决策时采取当前意义下最优策略的算法。
它是从问题的初始解出发，按照当前最佳的选择，把问题归纳为更小的相似的子问题，并使子问题最优，再由子问题来推导出全局最优解。
引例
- 现有 10 元、5 元、2 元、1 元四种纸币，使用的张数不限，需要用这四种纸币凑成 p 元钱，怎样用最少的张数达到此要求。
此题我们很容易就想到了贪心的算法，即每次尽量选面值大的纸币。
在 p=14 时，贪心算法的结果为 14=10+2+2+1，这种情况下贪心策略是对的。
- 现有 10 元、7 元、2 元、1 元四种纸币，使用的张数不限，需要用这四种纸币凑成 p 元钱，怎样用最少的张数达到此要求。
在 p=14 时，贪心算法的结果为 14=10+2+2，而最优结果为14=7+7，贪心显然是不对的。
- 在一个 N×M 的方格阵中，每一格子赋予一个数值，规定每次
移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的数字之和最大。
我们以 2×3 的矩阵为例：
若按贪心策略求解，所得路径为：1→3→4→6；
若按动态规划求解，所得路径为：1→2→10→6。
不是所有的问题都可以用贪心解决。
适用要求
问题的整体最优解可以由局部最优性导出。
a) 最优子结构性质
问题可以分解为若干个规模较小的相同问题，一个问题的最优
解包含其子问题的最优解。
b) 无后效性
某个状态以后的过程不会影响以前的状态，只与当前状态有关。
贪心与其他算法的区别
? 1.贪心与递推：与递推不同的是，贪心法中推进的每一步不是
依据某一固定的递推式，而是当前看似最佳的贪心决策，不断
的将问题归纳为更加小的相似的子问题。所以归纳、分析、选
择正确合适的贪心策略，是正确解决贪心问题的关键。
? 2.贪心与动态规划：与动态规划不同的是，贪心是鼠目寸光；
动态规划是统揽全局
? 动态规划是自底向上求出各子问题的解，最后汇集子问题的解
从而得出问题的全局最优解。
? 贪心算法是自顶向下，以迭代的方法一步一步做出贪心选择，从
而把问题简化成规模更小的问题。
基本思路
a) 猜想贪心策略
b) 尝试构造**例：如果发现反例说明贪心策略错误，调整思路
c) 尝试用数学归纳法、反证法、邻项交换等方法证明贪心策略
反证法：对于当前的贪心策略，否定当前的选择，看看是否能
得到最优解，如果不能得到，说明当前贪心策略是正确的；否则，当前策略不正确，不可用。
邻项交换：在任意局面下，任何对局部最优策略的微小改变都
会造成整体结果变差。经常用于以“排序”为贪心策略的证明。
总结
贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。
当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
用贪心思想解决问题的关键在于选择正确的策略。
一般不要求严格证明每一道题的贪心算法的正确性。
最好能进行简单的推理和验算。
手动构造一些样例是很好的验证方法和改进贪心策略的手段，如果发现有反例，那么当前策略一定是错的。