首页 > 代码库 > 利用动态方法修正贪婪算法中找硬币的问题

利用动态方法修正贪婪算法中找硬币的问题

在博文: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]

注意:上述返回的是找回的最小硬币数量。