贪心算法1 #

1. 贪心算法的基本概念
2. 贪心算法的算法思路

贪心算法的基本概念 #

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最优的选择，并以此希望得到最优的结果。

贪心算法不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

例如钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户硬币，你该如何安排才能找给客人的钱既正确且硬币的个数又最少呢？根据贪心算法的思路，我们每次取硬币的币值都尽可能的取大币额的硬币来保证硬币个数最少，可按照以下四步即可完成:

1.所给硬币总值不低于25时，一直给客户25分硬币，直到所给硬币总值小于25分

2.所给硬币总值不低于10时，一直给客户10分硬币，直到所给硬币总值小于10分

3.所给硬币总值不低于5时，一直给客户5分硬币，直到所给硬币总值小于5分

4.所给硬币总值不低于1时，一直给客户1分硬币，直到所给硬币总值小于1分

贪心算法的算法思路 #

从上面找硬币的例中：首先将找硬币的问题分为若干步骤，每步仅找一个硬币，其次该硬币的金额应该尽可能的取大币额的硬币，直到找给客户所有硬币为止。该例其实已经包含了贪心算法的基本步骤总结如下:

把求解的问题分成若干个子问题

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

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

n=int(input()) #输入所需找给客户硬币数
proc=[]#记录下每次给的硬币
count=0#最少所需硬币个数
while n>=25:#货币总额不低于25时
    n-=25  #给出一枚25分硬币
    count+=1#硬币数加1
    proc.append(25)
while n>=10:#参考上一循环
    n-=10
    count+=1
    proc.append(10)
while n>=5:#参考上一循环
    n-=5
    count+=1
    proc.append(5)
while n>=1:#参考上一循环
    n-=1
    count+=1
    proc.append(1)
print(count,proc)

小结 #

理解贪心算法的概念

掌握贪心算法的基本思路

习题 #

1. 贪心算法选取当前状态下最优的选择，并以此希望得到整体最优的结果。那么最终的结果一定是最优的吗？如果不是请举出实例
2. 能根据实际问题，做出贪心策略的算法步骤，并使用python代码实现