Coin change
💡
Le problème du « coin change » est l’un des exemples les plus connus dans le domaine de la programmation dynamique. Il met en évidence la différence marquée entre l’approche gloutonne (Greedy) et l’approche par programmation dynamique, et montre comment on peut être tenté de croire que la solution gloutonne est suffisante, alors qu’en réalité, cette approche n’aboutit qu’à une solution partielle et non à la solution globale optimale.
Étant donné un système monétaire composé de
n pièces, chacune ayant une valeur positive , votre objectif est de trouver un moyen de former la somme x en utilisant le moins de pièces possible.Par exemple, si les valeurs de pièces sont et que nous devons former
11, le choix optimal est d’utiliser 1 + 5 + 5 ⇒ 3 pièces.Entrée
La première ligne de l’entrée contient deux entiers
n (1 ≤ n ≤ 100) et x (1 ≤ x ≤ ).La ligne suivante contient
n entiers séparés par des espaces (1 ≤ ≤ ).Sortie
Le programme doit afficher le nombre minimal de pièces nécessaire pour obtenir la somme
x. S’il est impossible de former x, le programme doit afficher -1.Exemples
Input | Output |
3 11
1 5 7 | 3 |
3 12
1 5 7 | 2 |
Explication
- 11 → 1 + 5 + 5
- 12 → 5 + 7
Tutoriel
Remarquez que l’approche gloutonne, qui consiste à prendre toujours la pièce la plus grande possible, ne fonctionne pas. Le premier exemple l’illustre parfaitement. Si nous voulons obtenir 11 et que nous prenons d’abord la pièce de valeur 7 ⇒ il nous reste 4 à obtenir. Nous devons alors prendre 4 fois la pièce de 1, ce qui donne 5 pièces au total. Or, la réponse optimale n’est que de 3 pièces (5 + 5 + 1).
Définissons une variable d'état
d[i] qui représentera le nombre minimal de pièces nécessaires pour former la somme i. Si nous arrivons à initialiser correctement d et à mettre à jour toutes les valeurs jusqu’à la somme désirée x, la réponse finale sera simplement d[x] (le nombre minimal de pièces pour former x).Au départ, on peut initialiser toutes les valeurs de
d à l’infini (somme impossible), sauf la valeur 0, qui peut être formée avec 0 pièce :c = [...]
x = ...
d = [0] + [float('inf')] * x # d[0] vaut 0 et d[1...x] (inclus) vaut l’infiniEnsuite, pour chaque nombre
1...x, nous cherchons à trouver le nombre minimal de pièces permettant d’atteindre ce nombre. Lorsque nous considérons un nombre num, nous testons toutes les pièces possibles pour vérifier si on peut former num en ajoutant la valeur d’une des pièces à l’une des sommes déjà obtenues (num - ). Si cela permet d’améliorer le résultat, nous mettons d[num] à jour. Ainsi, pour chaque num de 1...x, nous examinons tous les états précédents susceptibles de mener à num et nous tentons d’améliorer la valeur de d[num] :for num in range(1, x + 1): # Itérer sur tous les nombres 1...x (inclus)
for ci in c: # Tenter d'améliorer d[num] avec chaque pièce
if num - ci >= 0: # Si c'est possible de former num avec la pièce ci
d[num] = min(d[num], d[num - ci] + 1)
print(d[x])d[num] = min(d[num], d[num - ci] + 1) est l’étape clé de la solution. À chaque itération, on essaye d’améliorer l’état de d[num] si on peut le faire à partir de num - . On prend alors le nombre minimal de pièces pour former num - et on ajoute 1 pour utiliser la pièce .Une fois que nous avons traité tous les nombres avec toutes les pièces, la réponse finale est simplement la valeur de
d[x].Illustrons l’algorithme avec l’exemple donné :
c = [1, 5, 7] et x = 11
d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
num = 1(on tente d’améliorer le nombre de pièces pour former 1)
num = 2(on tente d’améliorer le nombre de pièces pour former 2)
num = 3(on tente d’améliorer le nombre de pièces pour former 3)
num = 4(on tente d’améliorer le nombre de pièces pour former 4)
num = 5(on tente d’améliorer le nombre de pièces pour former 5)
num = 6(on tente d’améliorer le nombre de pièces pour former 6)
num = 7(on tente d’améliorer le nombre de pièces pour former 7)
num = 8(on tente d’améliorer le nombre de pièces pour former 8)
num = 9(on tente d’améliorer le nombre de pièces pour former 9)
num = 10(on tente d’améliorer le nombre de pièces pour former 10)
num = 11(on tente d’améliorer le nombre de pièces pour former 11)
print(d[11])⇒ affiche 3
Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB