6

目標額とコインの種類のリストが与えられた場合、私のコードは、目標額に到達するために必要な最小のコインを見つけることになっています。

例:

  • C(78, [1, 5, 10, 25, 50]) = 6

    • 253x + 3xから 78 を作ることができる1ので、6 コインが必要です。

  • C(48, [1, 7, 24, 42]) = 2

    • 48 = 2x24なので、2 コインで十分です。

  • C(35, [1, 3, 16, 30, 50]) = 3

    • 162x + 1xから 35 を作ることができる3ので、コイン 3 枚で十分です。

for ループでコードを作成しましたが、再帰的にするにはどうすればよいですか?

def C(i, coins, cdict = None):
    if cdict == None:
        cdict = {}
    if i <= 0:
        cdict[i] = 0
        return cdict[i]
    elif i in cdict:
        return cdict[i]
    elif i in coins:
        cdict[i] = 1
        return cdict[i]
    else:
        min = 0
        for cj in coins:
            result = C(i - cj, coins)
            if result != 0:
                if min == 0 or (result + 1) < min:
                    min = 1 + result
        cdict[i] = min
        return cdict[i]
4

3 に答える 3

19

それは変化をもたらす問題です。これが標準の再帰的解決策でVあり、コインのリストとC目標金額です。

def min_change(V, C):
    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)

そして、これは動的計画法を使用した最適化されたバージョンです：

def min_change(V, C):
    m, n = len(V)+1, C+1
    table = [[0] * n for x in xrange(m)]
    for j in xrange(1, n):
        table[0][j] = float('inf')
    for i in xrange(1, m):
        for j in xrange(1, n):
            aC = table[i][j - V[i-1]] if j - V[i-1] >= 0 else float('inf')
            table[i][j] = min(table[i-1][j], 1 + aC)
    return table[m-1][n-1]

どちらの実装も常に最適なソリューションを返しますが、2番目の実装は大規模な入力の場合ははるかに高速になります。他の回答で提案されている欲張りアルゴリズムは、特定の通貨の組み合わせに対してのみ最適なソリューションを提供することに注意してください。たとえば、アメリカのコインで機能します。

于 2012-09-20T20:29:56.733 に答える
2

欲張りアルゴリズムを使用してみてください（最初に最大のコイン）。合計に適用した後、リストからコインを削除し、内部から関数を再度呼び出します。

于 2012-09-20T20:23:41.243 に答える