动态规划问题之贪婪算法实现硬币最优解（贪心算法能保证最优解吗）

动态规划问题之贪婪算法实现硬币最优解（贪心算法能保证最优解吗）

贪婪问题实现最少的硬币找零问题：

start_time = time.time()

end_time = time.time()

print(‘Took %f second’ % (end_time - start_time))

是我们加入用来计算运算时间的

首先定义一个函数：rec(coinValueList,change) 其中coinValueList是我们的硬币的面值，change是我们的需要找零的金额

[c for c in coinValueList if c<=change]：这里创建一个列表用来存储这次找零可以用到的面值金额，然后进行循环调用和递归运算。

import timestart_time = time.time()def rec(coinValueList,change): minCoins=change if change in coinValueList: return 1 else: for i in [c for c in coinValueList if c<=change]: numCoins=1+rec(coinValueList,change-i) if numCoins

我们可以看出这种算法耗时非常多，需要进行优化：

加入一个可查询的列表，就不用重复计算已经算过的此面值最优的找零方法，可以节约非常巨大的一部分时间。

import timestart_time = time.time()def rec(coinValueList,change,list): minCoins=change if change in coinValueList: list[change]=1 return 1 elif list[change]>0: return list[change] else: for i in [c for c in coinValueList if c<=change]: numCoins=1+rec(coinValueList,change-i,list) if numCoins

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。