如何通过贪婪算法实现动态规划中的硬币最优解问题？

本文共计472个文字，预计阅读时间需要2分钟。

动态规划问题之贪心算法实现最优解+贪心问题实现最少硬币找零问题：start_time=time.time() end_time=time.time() print( Took %f second(s) % (end_time - start_time) + is the time taken for the computation) 是我们加入用来计算运算时间的。

动态规划问题之贪婪算法实现硬币最优解

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

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]：这里创建一个列表用来存储这次找零可以用到的面值金额，然后进行循环调用和递归运算。