贪心算法
贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
基本要素
贪心选择
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别(贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。)。
贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。
通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。
然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。
上述过程可以简化为：
1、创建数学模型来描述问题。
2、把求解的问题分成若干个子问题。
3、对每一子问题求解，得到子问题的局部最优解。
4、把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：
从问题的某一初始解出发；while 能朝给定总目标前进一步 do，求出可行解的一个解元素；
最后，由所有解元素组合成问题的一个可行解。
贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。
动态规划主要运用于二维或三维问题，而贪心一般是一维问题。
常见应用场景
1、区间调度问题
2、背包问题
如上最终的结果并不是最优解，在这个案例中贪婪算法并无法得出最优解，只能得到近似最优解,也算是该算法的局限性之一。
该类问题中需要得到全局最优解的话可以采取动态规划算法。
