首页 > 代码库 > 利用动态方法修正贪婪算法中找硬币的问题
利用动态方法修正贪婪算法中找硬币的问题
在博文:http://blog.csdn.net/qiwsir/article/details/31375449 中,讲述了如何用贪婪算法解决找硬币的问题,同时也指出了该方法存在的问题。
如何解决?
下面就是一个解决方案,在这里采用的是动态算法。
def coinChange(centsNeeded, coinValues): minCoins = [[0 for j in range(centsNeeded + 1)] for i in range(len(coinValues))] minCoins[0] = range(centsNeeded + 1) for i in range(1,len(coinValues)): for j in range(0, centsNeeded + 1): if j < coinValues[i]: minCoins[i][j] = minCoins[i-1][j] else: minCoins[i][j] = min(minCoins[i-1][j], 1 + minCoins[i][j-coinValues[i]]) return minCoins[-1][-1]
注意:上述返回的是找回的最小硬币数量。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。