时间戳

首页 > 解决方案 > 用有限的硬币找零

python-3.x - 用有限的硬币找零

问题描述

import sys

def minCoins(coins, m, how, V):
    # table[i] will be storing the minimum  
    # number of coins required for i value.  
    # So table[V] will have result 
    table = [0 for i in range(V + 1)] 
    index = []
    # Base case (If given value V is 0) 
    table[0] = 0

    # Initialize all table values as Infinite 
    for i in range(1, V + 1): 
        table[i] = sys.maxsize 

    # Compute minimum coins required  
    # for all values from 1 to V 
    for i in range(1, V + 1):
        # Go through all coins smaller than i 
        for j in range(m): 
            if (coins[j] <= i): 
                sub_res = table[i - coins[j]]
                if (sub_res != sys.maxsize and 
                    sub_res + 1 < table[i]):
                    if sub_res +1 <= how[j] :
                        table[i] = sub_res + 1

    return table[V]

coins = [200, 100, 50, 20, 10, 5, 2, 1]
howmanycoins = [0, 2, 2, 3, 0, 0, 7, 8]
m = len(coins)
V = 16
print("Minimum coins required is ", minCoins(coins, m, howmanycoins, V))

我对这段代码有疑问。当 tablehowmanycoins有这个值时，[0, 2, 2, 3, 0, 0, 7, 9]程序给出很好的答案 7x "2" + 2x "1" = 9 个硬币，但是当 8 在最后一个位置时，输出如下所示：

所需的最低硬币为 9223372036854775807。

标签： python-3.x

解决方案

看这行代码：

if sub_res +1 <= how[j] :

在这里你检查你没有使用更多的硬币how[j]，但实际上这些sub_res + 1硬币可以有不同的价值，而不仅仅是coins[j]价值。最小的例子：

coins = [1, 2]
howmanycoins = [1, 1]
m = len(coins)
V = 3

行不通，因为您显然需要 2 个硬币，但是2 > how[0]and 2 > how[1], 但在这种情况下，您使用每个值的 1 个硬币。

为了解决您的问题，您应该为每个值保存所有使用过的硬币，并将您的算法更改为蛮力。

推荐阅读