0

コインチェンジ問題をやっています。最小限の変更を可能にするために必要なコインの数を出力するという問題は終了しましたが、それらのコインも出力するようにプログラムを変更するにはどうすればよいですか??

サンプル I/O は次のとおりです。

input: coin_change(48, [1, 5, 10, 25, 50])

output: [6, [25, 10, 10, 1, 1, 1]]

input: coin_change(48, [1, 7, 24, 42])

output: [2, [24, 24]]

現在、私のコードは 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)

以下のコードは私が試したものですが、2番目の入力では機能しません

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

2 に答える 2

1

maxx=max(V) を使用しない場合があります

最適なソリューションは、48=25+10+10+1+1+1 未満の 2 つのコインを持つ、たとえば 48=24+24 などの小さなコインで構成される場合があります。その場合、25>24 ですが、48 を作成するには、より多くの小さなコインを使用する必要があります。

したがって、入力が (48, [1, 7, 24, 42]) の場合、2 番目の状況に陥り、48 = 42+1+1+1+1+1+1 になります。2 番目に投稿されたコードを最初のコードと組み合わせ、変更を保存するためのパラメータとしてリストを追加し、同じ再帰設計を使用できます。

于 2012-09-22T04:43:16.640 に答える
0

最初のコードは、いくつかの変更で機能します。カウントだけを返す代わりに、関数はリストまたは (count, [coins]) タプルを返すことができます。V をソートすることもできます。

于 2012-09-22T05:13:28.350 に答える