Programmation dynamique de pièce de monnaie de Python

Question

J'essaye actuellement d'implémenter la programmation dynamique en Python, mais je ne sais pas comment installer la partie de backtracking de sorte qu'elle ne répète pas les permutations. Par exemple, une entrée serait (6, [1,5]) et la sortie attendue devrait être 2 car il y a 2 façons possibles d'agencer 1 et 5 pour que leur somme soit équivalente à 6. Ces combinaisons sont {1, 1,1,1,1,1} et {1,5} mais comme mon programme fonctionne actuellement, il tient compte des combinaisons affichées ci-dessus et de la combinaison {5,1}. Cela provoque la sortie à 3 ce qui n'est pas ce que je voulais. Donc ma question est "Comment puis-je empêcher de répéter des permutations?". Mon code actuel est indiqué ci-dessous.

import collections as c 

    class DynamicProgram(object): 
     def __init__(self): 
      self.fib_memo = {} 
      # nested dictionary, collections.defaultdict works better than a regular nested dictionary 
      self.coin_change_memo = c.defaultdict(dict) 
      self.__dict__.update({x:k for x, k in locals().items() if x != 'self'}) 
     def coin_change(self, n, coin_array): 
      # check cache 
      if n in self.coin_change_memo: 
       if len(coin_array) in self.coin_change_memo[n]: 
      return [n][len(coin_array)] 

      # base cases 
      if n < 0: return 0 
      elif n == 1 or n == 0: return 1 

      result = 0 
      i = 0 

      # backtracking (the backbone of how this function works) 
      while i <= n and i < len(coin_array): 
       result += self.coin_change(n-coin_array[i], coin_array) 
       i += 1 

      # append to cache 
      self.coin_change_memo[n][len(coin_array)] = result 

      # return result 
      return result 

Answer 1

Quick fix serait:

result += self.coin_change(n-coin_array[i], coin_array[i:]) # notice coin_array[i:] instead of coin_array 

Mais vous voulez éviter ce que chaque fois que vous allez créer une nouvelle liste.

Mieux fix serait:

ajouter simplement un paramètre lastUsedCoinIndex dans la fonction. Ensuite, utilisez toujours des pièces avec index> = lastUsedCoinIndex à partir de la matrice de pièces. Cela garantira que les solutions sont distinctes.

Vous devrez également modifier l'état de votre note. Vous stockez actuellement la somme n et size of array (la taille du tableau ne change pas dans votre implémentation fournie contrairement à la correction rapide que j'ai fournie, donc il n'y a pas d'utilisation là-dedans !!) ensemble comme état pour le mémo. Maintenant, vous aurez n et lastUsedCoinIndex, ensemble déterminer un état mémo.

EDIT:

Votre fonction ressemblerait à ceci:

def coin_change(self,coin_array,n,lastUsedCoinIndex): 

Ici, les seules variables changeantes seront n et lastUsedCoinIndex. Vous pouvez donc également modifier votre constructeur de sorte qu'il prenne coin_array en entrée et que vous accédiez à la pièce coin_array initialisée par le constructeur via self.coin_array. Ensuite, la fonction deviendrait simplement:

def coin_change(self,n,lastUsedCoinIndex): 

Answer 2

L'un des moyens d'éviter la permutation est d'utiliser les numéros pour « non décroissante ». En faisant cela, vous n'ajouterez jamais de réponse pour [5 1] parce que ce n'est pas dans l'ordre "non décroissant". Et [1 5] sera ajouté car il est dans l'ordre "non décroissant". Donc, le changement de votre code sera si vous corrigez pour utiliser le nombre ith dans l'ordre trié que vous n'utiliserez jamais le nombre qui est strictement inférieur à cela.

Le changement de code sera comme décrit dans Suparshva's réponse avec la liste initiale des numéros triés.