一、什么是贪心算法

定义：

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。[1]

贪心算法就是将目标问题拆解为若干个子问题，然后再在每个子问题中选择当前子问题的最优解，从而由局部最优，达到全局最优的目的。也就是说，贪心算法不会直接从整体考虑问题，而是只专注于当前问题。

例1：

背包问题：

给定n种物品（可拆分）和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

二、算法特点

贪心算法简单高效，目的明确，可以省去寻找全局最优解时很多不必要的穷举步骤，但也导致了其具有一定的局限性，在处理有些问题时并不总能给出最优解。

例2：

0-1背包问题：

给定n种物品（不可拆分）和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

例2中的问题与例1类似，只是0-1背包问题中不能只选择物体的一部分，这将导致我们的贪心算法思想失效，原因是在这种情况下使用贪心算法思想，无法保证最终能将背包装满，部分闲置背包的空间使每公斤背包空间的价值降低，这时应比较选择该物品和不选择该物品所导致的最终方案结果，然后再做出选择，这将引发出更多互相重叠的子问题，要解决此类问题就得使用动态规划算法。实际上例1和例2经常用来作为贪心算法和动态规划算法的比较。

所以我们在解题时，首先要考虑的是贪心算法是否适用，一般地，当我们遇到一个子问题的选择会影响，其它子问题的选择时，贪心算法不适用。

例3：

在一个有权图中，我们从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）。[2]

（图源：极客时间-数据结构与算法之美专栏）

面对此问题，贪心算法的思路是，每次都选择当前顶点到下一顶点最近（权重最小）的边，直到到达顶点T。按照此思路，求出的最短路径为：S->A->E->T，路径长度为1+4+4=9。但这并不是最短路径，该题中的最短路径为：S->B->D->T,路径长度为2+2+2=6.

三、使用方法

例1的解题思路很明显，针对一组数据，我们定义了限制值（例中的背包容量）和期望值（例中要求总价值更高），希望从中选择几组数据，在满足限制值的同时，期望值最大。

具体的求解步骤可以是：

1.将目标问题分解为若干子问题；

2.找出合适的贪心策略（在对限制值消耗最小的情况下，对期望值贡献最大的选择）；

3.求解每一个子问题的最优解；

4.将局部最优解堆叠程全局最优解；

四、相关题目

例4：

分发饼干：

问题描述：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

1.你可以假设胃口值为正。

2.一个小朋友最多只能拥有一块饼干。[3]

解题思路：

1.尽量先满足胃口值小的孩子，因为这样的孩子容易满足。2.进行条件1时，尽可能选用尺寸小的，这样大尺寸饼干可以用来满足胃口值大的孩子。

这道题的贪心思想非常明显，就是要尽可能地满足更多的孩子，而胃口值小的孩子是容易满足的，反之胃口值大的孩子很难满足，所以在抉择上尽可能满足前者、饿着后者，因为它们对我们的期望值贡献是一样的。

所以综上可以得到解题思路，首先将胃口值和饼干尺寸由小至大排序。设定一个计数器child，用来记得到满足的孩子个数，再维护一个饼干指针cookies。如果饼干尺寸可以满足孩子胃口值，即g[child]<=s[cookies]，就将child、cookies分别加一(向后移动一位)，否则只将cookies向后移动一位。因为孩子的胃口值是由小到大的，若不满足当前的胃口值更不会满足之后的。

int findContentChildren(int* g, int gSize, int* s, int sSize)
{
    BubbleSort(g, gSize);//冒泡排序，将孩子的胃口值从小到大排序，函数的实现这里省略
    BubbleSort(s, sSize);
    int child=0;
    int cookies=0; //cookies标记分配到第几块饼干
		while (child < gSize || cookies < sSize)
    {
      if (g[child] <= s[cookies])
      {
      	child += 1;
      }
      cookies += 1;
    }
    return child;
}

时间复杂度：

两次排序+一次循环，这里使用的冒泡排序,所以$T(n)=O(n^2)+O(n^2)+O(n)=O(n^2)$;若使用其它高效的排序（如快排），时间复杂度可降低。

五、总结

贪心算法是一种很高效的算法思想，但它的适用场景其实有限制。贪心算法思想更多的是用来指导设计基础算法。比如最小生成树算法、单源最短路径算法、以及Huffman编码，都用到了贪心算法的思想。在使用时要注意其局限性，由于贪心算法问题并没有固定的贪心策略，所以最关键的点就是找到目标问题所适用的贪心策略。·

引用来源：

[1] 贪心算法 - 维基百科

[2]37 | 贪心算法：如何用贪心算法实现Huffman压缩编码？- 极客时间

[3]455.分发饼干-力扣

[4]435.无重叠区间-力扣

封面：Pixabay License