分而治之 - 最小硬币 - 返回硬币作为阵列

下面是对最小硬币更换问题的蛮力解决方案。它需要一个整数变化，这是需要做出的变化，以及一系列硬币面值。它返回进行该更改所需的最小硬币。分而治之 - 最小硬币 - 返回硬币作为阵列

我该如何修改这个也返回硬币数组？

例如，如果要求用值[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

分而治之 - 最小硬币 - 返回硬币作为阵列

回答

相关问题