引言
平时购物找钱时，为了使找回零钱的硬币数最少，从最大面值的币种开始，按递减的顺序考虑币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就贪心算法。这种方法在这里总是最优的，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。
如果面值分别为1,5,11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应该找1个11单位的硬币和4个1单位的硬币，总共找回5个硬币。但最优的解答是3个5单位面值硬币。
贪心算法并不是一个具体的算法，而是一种算法的思想，或者说是解决问题一种思路。
永远没有最好的算法，只有最适合的算法，我们选用贪心算法的原因就是因为它能够满足当前的需要并且比其他算法更加简单。
概念
贪心算法并不是整体最优考虑，它所做出的选择只是在某种意义上的局部最优（总是做出在当前看来是最好的选择）。这种局部最优选择并不能保证总能获得全局最优解，但它通常可以获得较好的近似最优解。
贪心算法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出选择，不管将来有什么结果，这个选择不会改变。
贪心算法一般在开始策略选择前会进行排序，排好序后就进行最优化选择。
基本思想
重要特性
- 最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
- 贪心选择性质：指问题的整体最优解可以通过一系列局部最优的选择。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。既贪心选择来得到。这是贪心算法和动态规划法的主要区别。证明一个问题具有贪心选择性质也是贪心法的一个难点。
（关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。）
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。存在问题
