python找零方案_找零问题之递归算法求解Python

论坛 期权论坛 脚本     
已经匿名di用户   2022-5-29 19:26   2104   0

找零问题之递归算法求解

其实贪心算法得出的结果并不一定是最优解。拿上篇文章中的找零问题来说,如果是找零6元,并且面值为[1,3,4],那么依据算法结果应该是一张4元,两张1元,一共三张。但是实际上两张3元即可。所以贪心算法的到的结果不一定是最优解,取决于实际数据。(实际是“每次选取面值大的纸币不一定使得最终的纸币数量少”)。

所以用贪心算法来做是不完美的。简单粗暴的方法就是枚举出所有的方案,对比得出最优的方案。

直接枚举而不用递归,暂时想不出来┭┮﹏┭┮。还是用递归吧。

思路2:也可以用递归的思想来枚举所有的找零方案。比如,当前面值有1,2,5,10元四种面值的纸币,如果需要找零15元,那么可以这样想,15元由1元和14元组成(2元和13元组成,5元和10元组成,10元和5元组成),这样,找零15元就可以是1张一元的纸币和找零14元的最优方案相加起来(1张2元纸币和找零13元的最优方案加起来,同理,1张5元和找零10元,一张10元和找零五元,四种方案取最优),而找零14元的最优方案也是可以分成1张一元的纸币和找零13元的最优方案相加(1张2元和找零11元的最优方案相加,1张5元和找零8元等等一次类推,四种方案取最优),以此类推。即递归求解。

# 递归算法解决找零问题

def recMC(coinList, change):

dic = {}

dics = {}

minCoins = change

# coinList.sort(reverse=True)

# 递归终止条件

if change in coinList:

if dic.get(str(change)):

dic[str(change)] += 1

else:

dic[str(change)] = 1

return 1, dic

# 向递归终止演进

else:

for c in [i for i in coinList if i <= change]:

num, dic = recMC(coinList, change - c)

numCoins = 1 + num

# 获取到上一个子问题的字典,并依据当前步骤进行更新字典

if dic.get(str(c)):

dic[str(c)] += 1

else:

dic[str(c)] = 1

# 当前值小于最小值,对最小值重新赋值,并抓住当前值的字典,用于后续返回真正的最小值的字典。

if numCoins < minCoins:

minCoins = numCoins

dics = dic

# print(type(dic))

return minCoins, dics

num, dic = recMC([1,2,5,10], 17)

print(num)

print(dic)

代码有点小问题,更新一下。

def recMC(coinList, change):

dic = {}

dics = {}

minCoins = change

# coinList.sort(reverse=True)

# 递归终止条件

# 因为是终止,所以肯定空字典,也就不用判断是否含有当前键值了

if change in coinList:

# if dic.get(str(change)):

# dic[str(change)] += 1

# else:

dic[str(change)] = 1

return 1, dic

# 向递归终止演进

else:

for c in [i for i in coinList if i <= change]:

num, dic = recMC(coinList, change - c)

numCoins = 1 + num

# 这里因为有返回值,所以字典里可能已经有了键了,需要判断一下。

if dic.get(str(c)):

dic[str(c)] += 1

else:

dic[str(c)] = 1

# 更新完当前操作后,比较得出最小值

# 因为开头默认的最小值就是找零金额,所以最小值是没有问题的

# 但是最小字典方案没有初始化,所以这里用小于等于比较合适。

if numCoins <= minCoins:

minCoins = numCoins

dics = dic

# print(type(dic))

return minCoins, dics

import time

print(time.clock())

num, dic = recMC([1,5,10,25], 63)

# num, dic = recMC([1], 63)

print(num)

print(dic)

print(time.clock())

分享到 :
0 人收藏
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:81
帖子:4969
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP