algorithme de changement de prise dynamique qui retourne la liste réelle des pièces utilisées

Question

Je suis en train de régler le code de l'wikipedia:

https://en.wikipedia.org/wiki/Change-making_problem#Implementation

Pour aussi sortie la liste des pièces utilisées, non seulement le nombre de pièces de monnaie utilisées. C'est-à-dire, par exemple:

change_making([6, 8, 12], 52) produit 5 ce qui est correct (12+12+12+8+8 = 52).

Le problème est que je veux obtenir la sortie dans ce format [12, 12, 12, 8, 8] au lieu de seulement 5 et je n'ai aucune idée de comment faire cela.

Le code en question:

def _get_change_making_matrix(set_of_coins, r): 
    m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)] 

    for i in range(r + 1): 
     m[0][i] = i 

    return m 


def change_making(coins, n): 
    """This function assumes that all coins are available infinitely. 

    n is the number that we need to obtain with the fewest number of coins. 

    coins is a list or tuple with the available denominations.""" 

    m = _get_change_making_matrix(coins, n) 

    for c in range(1, len(coins) + 1): 

     for r in range(1, n + 1): 

      # Just use the coin coins[c - 1]. 
      if coins[c - 1] == r: 
       m[c][r] = 1 

      # coins[c - 1] cannot be included. 
      # We use the previous solution for making r, 
      # excluding coins[c - 1]. 
      elif coins[c - 1] > r: 
       m[c][r] = m[c - 1][r] 

      # We can use coins[c - 1]. 
      # We need to decide which one of the following solutions is the best: 
      # 1. Using the previous solution for making r (without using coins[c - 1]). 
      # 2. Using the previous solution for making r - coins[c - 1] (without using coins[c - 1]) plus this 1 extra coin. 
      else: 
       m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]]) 

    return m[-1][-1] 

Toute aide/suggestion serait grandement appréciée.

------------- ------------- EDIT

La solution (les commentaires supprimés):

def _change_making(coins, n): 
    m = [[0 for _ in range(n + 1)] for _ in range(len(coins) + 1)] 
    for i in range(n + 1): 
     m[0][i] = i 

    for c in range(1, len(coins) + 1): 
     for r in range(1, n + 1): 
      if coins[c - 1] == r: 
       m[c][r] = 1 
      elif coins[c - 1] > r: 
       m[c][r] = m[c - 1][r] 
      else: 
       m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]]) 

    i = len(coins) 
    j = n 
    ret = {k: 0 for k in coins} 
    while j != 0: 
     if m[i][j - coins[i - 1]] == m[i][j] - 1: 
      ret[coins[i - 1]] += 1 
      j = j - coins[i - 1] 
     else: 
      i = i - 1 

    return ret 

Pour trouver le plus proche * solution:

def change_making(coins, n): 
    try: 
     return _generate_packing(coins, n) 
    except: 
     return generate_packing(coins, n + 1) 

Par exemple change_making([2, 5], 8)

{2: 2, 5: 1} 

Parce que 9 est la solution la plus proche possible.

• par le plus proche je veux dire une solution qui est possible de satisfaire mais surtout la demande initiale. Par exemple, si nous devons retourner £ 8 en changement et nous n'avons pas le changement exact, eh bien, nous allons retourner £ 9 parce que nous avons des changements pour cela.

Answer 1

Voici les étapes comment vous pouvez le faire -

1) Commencez par i=len(coins) et j=n-à-dire la fin de votre tableau (ou liste) m

2) Maintenant, nous savons une pièce de monnaie de La valeur coins(i-1) est choisie si m[i][j] utilise exactement une pièce de plus que m[i][j-coins[i-1]].

3) Si cela n'arrive pas, nous vérifions les autres pièces (pièces à l'index inférieur dans la liste) pour la même condition.

Exemple-

Au début, nous avons la valeur 52 et nous avons résolu qu'il a besoin de 5 pièces en utilisant votre votre fonction.

Nous utilisons la première pièce de 12 seulement si pour la valeur 40 (c.-à-d. 52 -12) nous avons besoin de 4 pièces de monnaie et de même pour la 2e et la 3e pièces 12 valorisées.

Mais nous ne pouvons pas utiliser quatrième 12 pièce comme valeur 4 (ie 16-12) ne peut pas être atteint en utilisant 1 pièce.

est ici extrait de code à faire même (vous pouvez le utiliser à la fin de votre fonction au lieu de déclaration de retour) -

i=len(coins) 
j = n 
while(j!=0): 
    if m[i][j-coins[i-1]] == m[i][j]-1: 
     print(coins[i-1]) 
     j=j-coins[i-1] 
    else: 
     i=i-1