【原创首发】跟着小灰学Python-贪心算法

声明：版权归本人所有，违者必究。 
转载请注明来源 https://juejin.cn/post/7111942157082034212

1.1. 贪心算法

1.1.1. 算法定义

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，贪心算法并不是从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解，接近整体最优解。

1.1.2. 基本思想

贪心算法的基本思想是，将一个大的问题拆解成多个子问题，对每个子问题做出最优选择，最终将所有子问题的输出合并获取大问题的最优解。设计步骤为： 

（1）建立数学模型来描述问题。

（2）把求解的问题分成若干个子问题。

（3）对每个子问题求解，得到子问题的局部最优解。

（4）把子问题的解局部最优解合成原来解问题的一个解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

以理财为例，理财有风险和收益两种属性，我们希望找到一种最好的理财方式，如果我们贪心于低风险，那么在找理财产品时，我们可以按风险高低排序，挑选出最低风险的产品；如果我们贪心于高收益，可以按收益率排序，挑选出最高收益率的产品；如果我们既要低风险又要高收益，可将各理财产品的风险与收益率进行量化，将风险和收益率的比值进行排序，挑选出性价比最高的理财产品。以上可以看做是三种不同的贪心策略。**

1.1.3. 代码实现--钱币找零

问题描述：

有面额为1元、5元、10元、20元、50元、100元的纸币，现希望支付N元，最少需要多少张纸币？

算法分析：

问题的目的是找出最少需要的纸币张数。可以将问题分解为多个子问题，将纸币按面额大小排序，分别是找出最少需要多少张100的纸币、多少张50的纸币、多少张20的纸币等；用总金额除以100，获得的整数即为最少需要的100的纸币张数，余数作为后续计算的输入，依次迭代计算每种面额纸币所需的最小张数；每种面额的纸币数量加起来，组成最终的最优解，即最少需要的纸币张数。

代码实现：

【例1-1】 钱币找零：

papers = [100, 50, 20, 10, 5, 1]              # 按大小排序后的纸币金额
total_money = 248                       # 要支付的金额时
temp = total_money                      # 剩余的零钱
total_count = 0                          # 总纸币张数
for paper in papers:
    if temp >= paper:
        least_count = temp // paper        # 局部最优解，每种纸币最少需要的张数
        total_count += least_count
        print("局部计算：最少需要{}张{}元".format(least_count, paper))
        temp = temp % paper
    if temp == 0:
        break
print("最终计算：最少需要{}张纸币".format(total_count))

执行结果:

局部计算：最少需要2张100元
局部计算：最少需要2张20元
局部计算：最少需要1张5元
局部计算：最少需要3张1元
最终计算：最少需要8张纸币