Divide and Conquer - Pièces minimum - Pièces de retour sous forme de tableau

Question

Voici une solution force brute au problème minimum de changement de pièce. Il faut un changement int, qui est le changement qui doit être fait, et un tableau de dénominations de pièces de monnaie. Il retourne les pièces minimales nécessaires pour effectuer ce changement.

Comment puis-je modifier cela pour revenir aussi un tableau des pièces de monnaie? Par exemple, si l'on vous demande de changer pour 10 cents avec les valeurs [1, 2, 5], il faut retourner 2 pièces min et un tableau [0, 0, 2] pour deux nickels.

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

Comme toute fonction récursive, vous commencez avec votre condition de garde - le test qui vous indique quand vous avez terminé:

if change in coinValueList: 
    return 1 

Pour convertir en une liste des pièces, juste retour une liste composée de 1 pièce:

if change in coinValueList: 
    return [ change ] 

Dans l'autre partie de votre fonction, vous savez que vos appels récursifs renvoie une liste. Donc, il suffit de prendre la liste et en faire une plus grande liste:

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

devient:

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

Vous devez mettre à jour vos autres tests aussi bien.