贪心算法1 #

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

贪心算法的基本概念 #

例如钱柜里的货币只有 25 分、10 分、5 分和 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代码实现