1

コイン交換の問題をやっています。最小限の変更で必要なコインの数が印刷されるという問題は解決しましたが、それらのコインも印刷されるようにプログラムを変更するにはどうすればよいですか？

ここにサンプルがありますI/O：

入力：coin_change(48, [1, 5, 10, 25, 50])

出力：[6, [25, 10, 10, 1, 1, 1]]

現在、私のコードは。のみを返します6。

ちなみに、これは再帰のみで実行する必要があります。ループは許可されていません

コード：

def change(C, V):
    def min_coins(i, aC):
        if aC == 0:
            return 0
        elif i == -1 or aC < 0:
            return float('inf')
        else:
            return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
    return min_coins(len(V)-1, C)
4

1 に答える 1

2

プログラムの別のバージョン：

def change(C, V, res=None):
    res = [] if res is None else res
    if len(V) == 0:
        return len(res), res
    maxx = max(V)
    V.remove(maxx)
    ans = C//maxx
    if ans == 0 and maxx < C :
        res += [maxx] * ans
        return len(res), res
    else:
        res += [maxx] * ans
        return  change(C % maxx, V, res)

print change(48,[1, 5, 10, 25, 50])
print change(30,[25, 10, 2, 3, 1])

出力：

(6, [25, 10, 10, 1, 1, 1])
(3, [25, 3, 2])

PS：必要に応じて説明を追加します。

于 2012-09-21T18:33:40.890 に答える