找零问题之递归算法求解
其实贪心算法得出的结果并不一定是最优解。拿上篇文章中的找零问题来说，如果是找零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())
转播
