今天介绍应用很广的贪心算法

01 算法介绍

贪心算法：选择每一阶段的局部最优，从而达到全局最优。选择贪心算法的关键在于可以从局部最优推出整体最优。

基本思路，可以分为5步：

建立数学模型来描述问题

把问题分成若干个子问题

找出合适的贪心策略

对每一子问题求局部最优解

将局部最优解堆叠成全局最优解

需要注意的是：贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题能产生整体最优解或者是整体最优解的近似解。

02 场景模拟

场景：在超市结账时，假设只有1分、5分、1角、3角、5角、1元的硬币，如果需要找零钱，收银员希望将最少的硬币数找给顾客。那么，给定需要找的零钱数目，如何求得最少的硬币数呢？

1.首先我们要为收银员建立起一个零钱库。这个零钱库决定了收银员拥有的总零钱金额，及零钱的各个面值。代码如下：

2.随后们就可以用贪心算法去计算找零所需各面值数量。这里贪心算法获得局部最优解的原则为总是从最大面值开始找零，依次向下。代码为：

3.最后，主代码段为：

03 运行尝试

运行程序：根据提示输入你想要为收银员创建的各面值零钱的数量。比如0.01面值有20个、0.05面值有4个、0.1面值有20个、0.5面值有8个、1.0面值有4个，则可以得到收银员总零钱金额为：10.4。程序的运行结果如下：

然后可以输入找零金额，比如6.6，则贪心算法可以计算出总硬币数最少对应的各面值数量组合为：

这就是贪心算法在收银员找零问题上的应用。贪心算法还有许多应用案例，比如：

如何分发胡萝卜能达到“喂饱尽可能多兔子”效果

如何玩跳跃游戏能达到“最小步数走到终点”效果

……