returns 实际使用的硬币列表的动态找零算法

Question

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

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]

任何 help/suggestion 将不胜感激。

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

解决方案（删除注释）：

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 是最接近的解。

最接近 我的意思是可以满足但高于原始要求的解决方案。例如，如果我们需要 return 8 英镑的零钱，但我们没有确切的零钱，那么，我们会 return 9 英镑，因为我们确实有零钱。

Answer 1

这里是你如何做的步骤-

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

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

正好多一枚硬币，则选择价值 coins(i-1) 的硬币

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

示例-

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

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

但是我们不能用第四个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

returns 实际使用的硬币列表的动态找零算法

Dynamic change-making algorithm that returns actual list of coins used

python

dynamic-programming

coin-change