重学数据结构与算法系列：一文讲透贪心算法

引言

人之初性本善，但是随着自身的经历、生活环境等因素的影响，人逐渐会生出贪嗔痴。实际上不光人有贪念，我们的算法也会有贪念，今天就和大家介绍下一个有贪念的算法模型——贪心算法，看看一个算法是怎么产生贪念的。

什么是贪心算法

在分析和求解某个问题时，在每一步的计算选择上都是最优的或者最好的，通过这种方式期望最终的计算的结果也是最优的。也就是说，算法通过先追求局部的最优解，从而寻求整体的最优解。

贪心算法的基本步骤：

1、首先定义问题，确定问题模型是不是适合使用贪心算法，即求解最值问题；

2、将求极值的问题进行拆解，然后对拆解后的每一个子问题进行求解，试图获得当前子问题的局部最优解；

3、所有子问题的局部最优解求解完成后，把这些局部最优解进行汇总合并，得到最终全局的最优解，那么这个最优解就是整个问题的最优解。

通过场景理解算法

概念性的算法描述可能大家都不太好理解，所以需要结合一些实际的场景来进行说明。这里以我们小时候的找零钱的例子来进行切入。虽然现在大家都用手机扫一扫进行支付，已经很久到没碰过钱了，但是并不妨碍找零问题 可帮助我们形象的理解贪心算法的实现过程。

假设你是一家小卖店的老板，你有各种面值大小的零钱，如1块钱、3块钱、5块钱。这个时候有个小朋友过来买东西，他要求你找的零钱要张数最小，这样他的口袋才能装得下。假设我们分别把零钱记为c[0]、c[1]、c[2] ......，小朋友拿来买零食的钱我们记为total。那么刚才说的小朋友希望获得最少张数零钱的需求我们就可以把他转化为一个编程求最优解的问题，即给定总数total，求解最少需要几个c相加的和等于给定的总数total。

例子1：

假设给定需要找的零钱为11，当前的零钱为1块、3块、5块。

输入：total=11，c[0]=1,c[1]=3,c[2]=5

输出：3

问题分析

通过提取问题中的关键词“最少”，我们可以明确此问题的实际上就是一个求解最值的问题，只要找到满足条件的最小零钱张数就可以解决找回最少零钱的问题了。想要找到最小的零钱张数，我们最先想到的方法就是进行穷举，列举出来所有可能的满足总数为11的零钱组合。

如下图所示，再在这些组合中找到使用零钱张数最少的组合再计算具体的张数，我们就可以获得最终的答案了。但是这显然不是一个好的解决思路。因为如果对应的total很大，我们穷举的结果将会爆发性增长。

那有没有更好的解决办法呢？这时候我们就可以考虑下贪心算法的实现了，找到满足要求的最小张数零钱。既然是找零钱，那么我们可以将问题转换为找到满足总数total的零钱最少需要几个步骤，实际上就是将问题拆分到每次找零钱的小步骤中，而贪心算法的核心就是需要在每个小步骤中贪心寻求局部最优解。

因此在找零钱的每个步骤中，都需要找到该步骤中对应的最优解零钱大小，接下来我们来一起看下贪心算法执行过程。这里假设各个面值的零钱比较充足。

在寻找零钱的步骤中，首先获取最大面值为5的零钱（贪心，上来就找最大的），接着发现剩余待找零钱6=11-5，于是继续寻找最大的面值为5的零钱（继续贪心），待找零钱1=6-5。

此时只要获取面值为1的零钱就可以完成任务了，再将之前步骤中的结果整合到一起，最终我们得出想要获取total为11的最少张数零钱的大小为3。通过这样的分析，贪心算法是不是也没有那么的复杂。

对应的代码实现如下所示：

/**
* @Author: mufeng
* @Date: 2022/5/15 15:33
* @Version: V 1.0.0
* @Description: 计算最小满足条件的零钱张数
*/
public class MinChangeCountSolution {

   public static void main(String[] args) {
       int values[] = {5,5,3,3,1};
       System.out.println(getMinChangeCount(11, values));

   }

   //假设values数组从大到小排列
   static int getMinChangeCount(int total, int[] values) {
       int rest = total;
       int result = 0;
       int count = values.length;

       // 从大到小遍历所有面值
       for (int i = 0; i < count; ++ i) {
           //计算需要几张这种面值的零钱
           int needCount = rest / values[i];
           //计算使用后的余额
           rest -= needCount * values[i];
           //计数增加
           result += needCount;

           if (rest == 0) {
               return result;
           }
       }
       //没有找到合适的面值
       return -1;
   }

}

以上我们分析了贪心算法的大致实现过程，但是实际上还是有问题的。不知道大家有没有发现，由于贪心算法过于贪心，每一个步骤都想要找到局部最优解。那么假如在上面的例子中，我们没有1块钱的零钱，上述代码的返回结果是-1，即没有符合条件的答案。但是实际并非如此，也就是说5,3,3也是满足条件的，但是上述代码却没有找到。

所以上述代码还是有问题的，关键点就在于，当发现没有1元零钱的时候，需要回头去看能不能把第二步骤中的5元零钱换成3元零钱再进行后续的迭代，如果有这样的步骤，那么就可以找到5,3,3这样的组合。

总结

本文主要通过对于贪心算法的描述，并结合实际的找零钱的例子，带大家一起分析了贪心算法的具体实现过程。同时分析了贪心算法存在的不足，即容易陷入局部最优的陷阱无法自拔，导致最终无法给出满足条件的结果，这也是大家以后在使用贪心算法分析问题时特别需要注意的问题。