Разделите и покорите - Минимальные монеты - Монеты возврата в качестве массива

Question

Ниже приведена грубая сила решения проблемы с минимальной заменой монет. Требуется изменение int, которое требуется для изменения, и массив монетных деноминаций. Он возвращает минимальные монеты, необходимые для внесения этих изменений.

Как я могу изменить это, чтобы вернуть массив монет?

Например, если требуется внести изменение на 10 центов со значениями [1, 2, 5], он должен вернуть 2 монеты min и массив [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)) 

Answer 1

Как и любой рекурсивной функции, вы начинаете с защитного состояния - тест, который говорит вам, когда вы сделали:

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) 

Вы должны обновить другие тесты, а также.