Programmation dynamique simpleModifier
Une stratégie de programmation dynamique classique travaille à la hausse en trouvant les combinaisons de toutes les valeurs plus petites qui s’additionneraient au seuil actuel. Ainsi, à chaque seuil, tous les seuils précédents sont potentiellement considérés pour travailler vers le haut jusqu’au montant cible W. Pour cette raison, cette approche de programmation dynamique nécessite un nombre d’étapes qui est O(nW), où n est le nombre de types de pièces.
ImplémentationEdit
Ce qui suit est une implémentation de la programmation dynamique (avec Python 3) qui utilise une matrice pour garder la trace des solutions optimales aux sous-problèmes, et renvoie le nombre minimum de pièces, ou « Infini » s’il n’y a aucun moyen de faire de la monnaie avec les pièces données. Une seconde matrice peut être utilisée pour obtenir l’ensemble des pièces de monnaie pour la solution optimale.
def _get_change_making_matrix(set_of_coins, r: int): m = for _ in range(len(set_of_coins) + 1)] for i in range(1, r + 1): m = float('inf') # By default there is no way of making change return mdef change_making(coins, n: int): """This function assumes that all coins are available infinitely. n is the number to obtain with the fewest 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. if coins == r: m = 1 # coins cannot be included. # Use the previous solution for making r, # excluding coins. elif coins > r: m = m # coins can be used. # Decide which one of the following solutions is the best: # 1. Using the previous solution for making r (without using coins). # 2. Using the previous solution for making r - coins (without # using coins) plus this 1 extra coin. else: m = min(m, 1 + m]) return m
Programmation dynamique avec l’arbre de convolution probabilisteEdit
L’arbre de convolution probabiliste peut également être utilisé comme une approche de programmation dynamique plus efficace. L’arbre de convolution probabiliste fusionne des paires de pièces de monnaie pour produire tous les montants qui peuvent être créés par cette paire de pièces de monnaie (avec aucune pièce de monnaie présente, seulement la première pièce de monnaie présente, seulement la deuxième pièce de monnaie présente et les deux pièces de monnaie présentes), puis fusionne ensuite les paires de ces résultats fusionnés de la même manière. Ce processus est répété jusqu’à ce que les deux dernières collections de résultats soient fusionnées en une seule, ce qui conduit à un arbre binaire équilibré avec W log(W) opérations de fusion. De plus, en discrétisant les valeurs des pièces, chacune de ces opérations de fusion peut être effectuée par convolution, ce qui peut souvent être réalisé plus efficacement avec la transformée de Fourier rapide (FFT). De cette manière, l’arbre de convolution probabiliste peut être utilisé pour obtenir une solution en un nombre subquadratique d’étapes : chaque convolution peut être effectuée en n log(n), et les opérations de fusion initiales (plus nombreuses) utilisent un n plus petit, tandis que les opérations ultérieures (moins nombreuses) nécessitent n de l’ordre de W.
La méthode de programmation dynamique basée sur l’arbre de convolution probabiliste résout aussi efficacement la généralisation probabiliste du problème de rendu de monnaie, où l’incertitude ou le flou dans le montant cible W en fait une distribution discrète plutôt qu’une quantité fixe, où la valeur de chaque pièce est de même autorisée à être floue (par exemple, lorsqu’un taux de change est considéré), et où différentes pièces peuvent être utilisées avec des fréquences particulières.
Méthode cupideEdit
Pour les systèmes de pièces dits canoniques, comme ceux utilisés aux États-Unis et dans de nombreux autres pays, un algorithme cupide consistant à choisir la plus grande dénomination de pièce qui n’est pas supérieure à la quantité restante à réaliser produira le résultat optimal. Ce n’est cependant pas le cas pour les systèmes de pièces arbitraires. Par exemple, si les dénominations des pièces sont 1, 3 et 4, alors pour faire 6, l’algorithme gourmand choisira trois pièces (4,1,1) alors que la solution optimale est deux pièces (3,3). Il est possible de tester si un système de pièces est canonique (c’est-à-dire si l’algorithme greedy résout toujours son problème de rendu de monnaie de manière optimale) en temps polynomial.