Skip to main content
 首页 » 编程设计

python之返回实际使用的硬币列表的动态找零算法

2025年02月15日8soundcode

我正在尝试调整来自维基百科的代码:

https://en.wikipedia.org/wiki/Change-making_problem#Implementation

同时输出使用的硬币列表,而不仅仅是使用的硬币数量。也就是说,例如:

change_making([6, 8, 12], 52) 输出 5 是正确的 (12+12+12+8+8 = 52)。

问题是我想得到这种格式的输出 [12, 12, 12, 8, 8] 而不是 5 我不知道怎么做这样做。

有问题的代码:

def _get_change_making_matrix(set_of_coins, r): 
    m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)] 
 
    for i in range(r + 1): 
        m[0][i] = i 
 
    return m 
 
 
def change_making(coins, n): 
    """This function assumes that all coins are available infinitely. 
 
    n is the number that we need to obtain with the fewest number of coins. 
 
    coins is a list or tuple with the available denominations.""" 
 
    m = _get_change_making_matrix(coins, n) 
 
    for c in range(1, len(coins) + 1): 
 
        for r in range(1, n + 1): 
 
            # Just use the coin coins[c - 1]. 
            if coins[c - 1] == r: 
                m[c][r] = 1 
 
            # coins[c - 1] cannot be included. 
            # We use the previous solution for making r, 
            # excluding coins[c - 1]. 
            elif coins[c - 1] > r: 
                m[c][r] = m[c - 1][r] 
 
            # We can use coins[c - 1]. 
            # We need to decide which one of the following solutions is the best: 
            # 1. Using the previous solution for making r (without using coins[c - 1]). 
            # 2. Using the previous solution for making r - coins[c - 1] (without using coins[c - 1]) plus this 1 extra coin. 
            else: 
                m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]]) 
 
    return m[-1][-1] 

如有任何帮助/建议,我们将不胜感激。

------------ 编辑------------

解决方案(删除注释):

def _change_making(coins, n): 
    m = [[0 for _ in range(n + 1)] for _ in range(len(coins) + 1)] 
    for i in range(n + 1): 
        m[0][i] = i 
 
    for c in range(1, len(coins) + 1): 
        for r in range(1, n + 1): 
            if coins[c - 1] == r: 
                m[c][r] = 1 
            elif coins[c - 1] > r: 
                m[c][r] = m[c - 1][r] 
            else: 
                m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]]) 
 
    i = len(coins) 
    j = n 
    ret = {k: 0 for k in coins} 
    while j != 0: 
        if m[i][j - coins[i - 1]] == m[i][j] - 1: 
            ret[coins[i - 1]] += 1 
            j = j - coins[i - 1] 
        else: 
            i = i - 1 
 
    return ret 

找到最接近 * 的解决方案:

def change_making(coins, n): 
    try: 
        return _generate_packing(coins, n) 
    except: 
        return generate_packing(coins, n + 1) 

例如 change_making([2, 5], 8)

{2: 2, 5: 1} 

因为 9 是最接近的解。

  • 最接近 是指可以满足但高于原始要求的解决方案。例如,如果我们需要退还 8 英镑的零钱,但我们没有确切的零钱,那么我们将退还 9 英镑,因为我们确实有零钱。

请您参考如下方法:

以下是您可以执行此操作的步骤 -

1) 从 i=len(coins) 和 j=n 开始,即数组(或列表)的末尾 m

2) 现在我们知道如果 m[i][j] 使用的硬币正好比 m[i][j-coins[i-1]].

3) 如果没有发生这种情况,我们会检查其他硬币(列表中较低索引的硬币)的相同情况。

示例-

一开始我们的值是 52,我们已经使用您的函数解决了它需要 5 个硬币的问题。

只有当值(value) 40(即 52 -12)我们需要 4 个硬币时,我们才使用 12 的第一个硬币,对于第二个和第三个 12 值(value)的硬币也类似。

但是我们不能用第四个12个硬币作为值4(即16-12)不能用1个硬币来实现。

这是执行相同操作的代码片段(您可以在函数末尾使用它而不是 return 语句)-

i=len(coins) 
j = n 
while(j!=0): 
    if m[i][j-coins[i-1]] == m[i][j]-1: 
        print(coins[i-1]) 
        j=j-coins[i-1] 
    else: 
        i=i-1