【数据结构与算法python】贪心策略

1、引入（找零兑换问题 ）

假设你为一家自动售货机厂家编程序，自动售货机要每次找给顾客最少数量硬币； 假设某次顾客投进$1纸币，买了ȼ37的东西，要找ȼ63，那么最少数量就是： 2个quarter（ȼ25）、 1个dime（ȼ10）和3个penny（ȼ1），一共6个

2、思想

从最大面值的硬币开始，用尽量多的数量有余额的，再到下一最大面值的硬币，还用尽量多的数量，一直到penny（ȼ1）为止 。 因为我们每次都试图解决问题的尽量大的一部分对应到兑换硬币问题，就是每次以最多数量的最大面值硬币来迅速减少找零面值。

3、代码实现

change = 63 coinList = [1,5,10,21,25] coinNumSum = 0 coinValue = [] while change>0: for i in range(len(coinList)-1,-1,-1): if change//coinList[i]>=1: coinNum = change//coinList[i] coinNumSum = coinNumSum+coinNum for j in range(coinNum): coinValue.append(coinList[i]) change = change-coinNum*coinList[i] break print(coinNumSum) print(coinValue)

4、算法分析

“贪心策略”解决找零兑换问题， 在美元或其他货币的硬币体系下表现尚好，但如果货币体系比较特殊，若某一国家的货币体系中含有ȼ21的硬币，则贪心算法即会失效，分析流程如下 按照“贪心策略”， 在Elbonia， ȼ63还是原来的6个硬币 ȼ63 = ȼ252 + ȼ101 + ȼ13 但实际上最优解是3个面值ȼ21的硬币！ ȼ63 = ȼ213