Le problème de changement aborde la question de trouver le nombre minimum de pièces (de certaines coupures) qui s’additionnent à une somme d’argent donnée. C’est un cas particulier du problème du sac à dos entier, et a des applications plus larges que la simple monnaie.
C’est également la variante la plus courante du problème du changement de pièce, un cas général de partition dans lequel, compte tenu des coupures disponibles d’un ensemble infini de pièces, l’objectif est de découvrir le nombre de façons possibles de faire un changement pour une quantité d’argent spécifique, sans tenir compte de l’ordre des pièces.
faire du changement est un problème de minimisation, nous choisissons la solution où nous devons donner un minimum de pièces pour un montant donné.
- Méthode gourmande
2. Méthode dynamique
programmation dynamique
Une stratégie de programmation dynamique classique fonctionne à 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 comme allant vers le haut jusqu’au montant objectif W. Pour cette raison, cette approche de programmation dynamique peut nécessiter un certain nombre d’étapes au moins quadratiques dans le montant objectif W.
changement optimal des pièces Nous l’avons vu, vous souhaitez effectuer un changement en utilisant un système de coupures, en utilisant le plus petit nombre de pièces possible. Parfois, l’algorithme gourmand donne la solution optimale. Mais parfois, ce n’est pas le cas — un exemple était le système (12, 5, 1), où l’algorithme dynamique donne 15 = 12 + 1 + 1 + 1 mais une meilleure réponse est 15 = 5 + 5 + 5 . mais la dynamique donne toujours une solution optimale ou des pièces minimales possibles dans ces dénominateurs.
Étapes: –
Nous trouverons le nombre minimum. des pièces requises pour le montant.
Le montant est le montant pour lequel nous effectuons le changement.
nous allons d’abord définir min. aucun. des pièces requises, c’est-à-dire, min = INFINITY
Cela signifie que nous ne savons pas au départ combien de pièces seront nécessaires.
Ensuite, nous vérifions chaque pièce de monnaie et voyons si elle peut être utilisée pour obtenir la solution.
Si c’est possible, nous mettons à jour les variables min et coin.
où, min = minimum non. des pièces nécessaires pour effectuer une modification de la quantité
coin= premier index de la pièce dans la solution
Exemple:
Montant = 5
pièces ={1,2,3}
Façons de faire des modifications = 5
