分割と征服 - 最小コイン - コインを配列として返す

Question

以下は、コインチェンジの問題の最小限の解決策です。それは必要な変更であるインチェンジ、およびコイン貨幣の配列を取ります。その変更を行うために必要な最小コインを返します。

これを変更してコインの配列も返すことができますか？

例えば、[1、2、5]の値を10セント変更するように要求された場合、2コイン分、2つのニッケルの配列[0、0,2]を返します。

if change in coinValueList: 
    return 1 

は、コインのリストにこれを変換するには、単にリターン：あなたが行われているかを示しますテスト - 任意の再帰関数と同様に

def recMC(coinValueList,change): 
    minCoins = change 
    if change in coinValueList: 
     return 1 
    else: 
     for i in [c for c in coinValueList if c <= change]: 
      numCoins = 1 + recMC(coinValueList,change-i) 
     if numCoins < minCoins: 
      minCoins = numCoins 
    return minCoins 

print(recMC([1,5,10,25],63)) 

Answer 1

、あなたのガード条件で始まります1コインからなるリスト：

if change in coinValueList: 
    return [ change ] 

あなたの関数の他の部分では、再帰呼び出しがリストを返すことがわかります。だから、単にリストを取ると、それより大きなリスト行います

 numCoins = 1 + recMC(coinValueList,change-i) 

は次のようになります。

 coins = [ i ] + recMC(coinValueList, change - i) 

あなたは同様にあなたの他のテストを更新する必要があります。