一、贪心算法：

1、概念：

每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

2、贪心算法解决问题的思路，并不一定能给出最优解：

在一个有权图中，从顶点S开始，找一条到顶点T的最短路径（路径中边的权值和最小）。贪心算法的解决思路是，每次都选择一条跟当前顶点相连的权最小的边，直到找到顶点T。按照这种思路，求出的最短路径是S->A->E->T，路径长度是1+4+4=9。这种贪心的选择方式，最终求的路径并不是最短路径，因为路径S->B->D->T才是最短路径，因为这条路径的长度是2+2+2=6。

在这个问题上，贪心算法不工作的主要原因是，前面的选择会影响后面的选择。如果第一步从顶点S走到顶点A，那接下来面对的顶点和边，跟第一步从顶点S走到顶点B，是完全不同的。所以，即便第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。

二、实战分析：

1、分糖果：

有 $m$ 个糖果和 $n$ 个孩子。现在要把糖果分给这些孩子吃，但是糖果少，孩子多（ $m<n$ ），所以糖果只能分配给一部分孩子。每个糖果的大小不等，这 $m$ 个糖果的大小分别是 $s_1$ ， $s_2$ ， $s_3$ ,……, $s_m$ 。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。假设这 $n$ 个孩子对糖果大小的需求分别是 $g_1$ ， $g_2$ ， $g_3$ ， ……， $g_n$ 。问题是，如何分配糖果，能尽可能满足最多数量的孩子？

把这个问题抽象成，从 $n$ 个孩子中，抽取一部分孩子分配糖果，让满足的孩子的个数（期望值）是最大的。这个问题的限制值就是糖果个数 $m$ 。
对于一个孩子来说，如果小的糖果可以满足，就没必要用更大的糖果，这样更大的就可以留给其他对糖果大小需求更大的孩子。另一方面，对糖果大小需求小的孩子更容易被满足，所以，可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子，对期望值的贡献是一样的。每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。

2、钱币找零：

假设有 $1元$ 、 $2元$ 、 $5元$ 、 $10元$ 、 $20元$ 、 $50元$ 、 $100元$ 这些面额的纸币，它们的张数分别是 $c_1$ 、 $c_2$ 、 $c_5$ 、 $c_10$ 、 $c_20$ 、 $c_50$ 、 $c_100$ 。现在要用这些钱来支付 $K$ 元，最少要用多少张纸币呢？

先用面值最大的来支付，如果不够，就继续用更小一点面值的，以此类推，最后剩下的用 $1元$ 来补齐。

3、区间覆盖：

假设有 $n$ 个区间，区间的起始端点和结束端点分别是 $[l_1, r_1]$ ， $[l_2, r_2]$ ， $[l_3, r_3]$ ， … $[l_n, r_n]$ 。从这 $n$ 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？

假设这 $n$ 个区间中最左端点是 $l_{min}$ ，最右端点是 $r_{max}$ 。这个问题就相当于选择几个不相交的区间，从左到右将 $[l_{min},r_{max}]$ 覆盖上。按照起始端点从小到大的顺序对这 $n$ 个区间排序，每次选择的时候，左端点跟前面的已经覆盖的区间不重合的，右端点又尽量小的，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间。这实际上就是一种贪心的选择方法。