分而治之 - 最小硬幣 - 返回硬幣作爲陣列

下面是對最小硬幣更換問題的蠻力解決方案。它需要一個整數變化，這是需要做出的變化，以及一系列硬幣面值。它返回進行該更改所需的最小硬幣。分而治之 - 最小硬幣 - 返回硬幣作爲陣列

我該如何修改這個也返回硬幣數組？

例如，如果要求用值[1,2,5]給出10美分的更改，它應該返回2個硬幣分鐘和一個數組[0,0,2]用於兩個鎳幣。

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))

來源

2017-02-04 user3612719

對我來說，它看起來像一個解決問題的網站的任務（[示例]（https://www.codewars.com/kata/knapsack-part-1-the-greedy-solution）），你期望我們爲你寫代碼？你有什麼嘗試？ – MaLiN2223

像任何遞歸函數，你開始你的監護條件 - 告訴你測試時，你就大功告成了：

if change in coinValueList: 
    return 1

將其轉換爲金幣的列表，只是返回由1個硬幣組成的列表：

if change in coinValueList: 
    return [ change ]

在函數的其他部分，您知道遞歸調用將返回一個列表。所以，只取列表，並使它成爲一個更大的列表：

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

變爲：

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

你必須更新您的其他測試也是如此。

來源

2017-02-04 03:28:53

分而治之 - 最小硬幣 - 返回硬幣作爲陣列

回答

相關問題