本文共 641 字，大约阅读时间需要 2 分钟。
贪心算法，又名贪婪法，是寻找最优解问题的常用方法
步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模； 步骤3：将所有解综合起来。假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？
这里需要明确的几个点：
1.货币只有 25 分、10 分、5 分和 1 分四种硬币； 2.找给客户 41 分钱的硬币； 3.硬币最少化思考，能使用我们今天学到的贪婪算法吗？怎么做？
（回顾一下上文贪婪法的基本步骤，1，2，3）
1.找给顾客sum_money=41分钱，可选择的是25 分、10 分、5 分和 1 分四种硬币。能找25分的，不找10分的原则，初次先找给顾客25分；
2.还差顾客sum_money=41-25=16。然后从25 分、10 分、5 分和 1 分四种硬币选取局部最优的给顾客，也就是选10分的，此时sum_money=16-10=6。重复迭代过程，还需要sum_money=6-5=1,sum_money=1-1=0。至此，顾客收到零钱，交易结束； 3.此时41分，分成了1个25，1个10，1个5，1个1，共四枚硬币。转载地址：http://lxxab.baihongyu.com/