Problème du rendu de monnaie (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen dont est tiré l'exemple du rendu de monnaie.
- le livre part 3 : greedy algorithms and dynamic programming de Tim Roughgarden dont est tirée la comparaison entre les méthodes de conception d'algorithme programmation dynamique et Diviser Pour Régner.
- le cours de mon collègue Pierre Duclosson pour l'exemple du triangle de nombres
🔖 Synthèse de ce qu'il faut retenir pour le bac
Un problème d'optimisation⚓︎
Point de cours 1 : problème du rendu de monnaie
On se place dans la position du caissier qui doit rendre en monnaie un certain montant avec un nombre minimal de pièces. On suppose que le caissier dispose en nombre illimité de toutes les valeurs de pièces disponibles. L'ensemble des valeurs de pièces disponibles constitue le système monétaire.
Il s'agit d'un problème d'optimisation dont la spécification est la suivante :
- Entrée du problème : un montant à rendre et une liste de valeurs de pièces d'un système monétaire ; on suppose qu'on dispose d'un nombre illimité de pièces de chaque valeur et qu'on dispose de pièces de 1 ainsi on peut toujours rendre la monnaie
- Sortie du problème : une liste de pièces dont la somme est égale au montant à rendre et dont le nombre de pièces est minimal
En programmation dynamique on utilise une sous-structure optimale⚓︎
Exercice 1
On a déjà rencontré le problème du rendu de monnaire dans le chapitre sur les algorithmes gloutons. L'heuristique gloutonne (une heuristique ne donne pas forcément une solution exacte mais a pour but de l'approcher convenablement) est simple :
- tant qu'il reste un montant à rendre on choisit la plus grande valeur de pièce disponible inférieure ou égale à la somme et on la retranche du montant à rendre
Attention
La solution construite n'est minimale en nombre de pièces que si le système monétaire vérifie une propriété de système canonique, qui n'est d'ailleurs pas simple à vérifier.
Question 1
Dans le système monétaire constitué des pièces [1, 4, 6], quel est le nombre de pièces rendues en monnaie par l'algorithme glouton pour un montant de 8 ?
Donner un contre-exemple prouvant que le nombre de pièces rendu par l'algorithme glouton n'est pas minimal.
| Montant restant | Pièce choisie par l'algorithme glouton |
|---|---|
| 8 | 6 |
| 2 | 1 |
| 1 | 1 |
L'algorithme rend la monnaie sur 8 avec 3 pièces. Cette solution n'est pas optimale : on peut rendre la monnaie sur 8 avec deux pièces de 4 car \(8 = 4 + 4\).
Question 2
Soit un montant M à rendre. Pour déterminer une solution optimale, on peut imaginer qu'on dispose d'une telle solution S c'est-à-dire d'une liste de pièces de somme égale à M, dont le nombre de pièces est minimal.
Si on enlève une pièce P de cette solution optimale, on obtient une liste S' de somme égale à M \(-\) P . Cette liste peut-elle ne pas être optimale (en nombre de pièces) pour le rendu de monnaie sur M \(-\) P ?
Supposons que la liste de pièces S' obtenue en enlevant une pièce P de la solution S ne soit pas optimale pour le rendu de monnaie sur M \(-\) P. Cela signifie qu'il existe une liste de pièces S'' de somme égale à M \(-\) P avec moins de pièces que S'. Mais alors en ajoutant la pièce P à S'' on construit une liste de pièces S''' de somme égale à M et qui compte moins de pièces que S. C'est contradictoire avec le fait que S est optimale pour le rendu de monnaie sur M. Par conséquent l'hypothèse que S' ne soit pas optimale pour le rendu de monnaie sur M \(-\) P, est fausse.
Ceci est un raisonnement par l'absurde.
Question 3
Soit un montant M à rendre. On a démontré que si on dispose d'une liste de pièces solution S optimale pour M alors la liste obtenue en retranchant une pièce P de S est est optimale pour le montant M \(-\) P.
Imaginons qu'on ait calculé des solutions optimales pour tous les montants M \(-\) P avec P pièce du système monétaire, comment peut-on construire une solution optimale pour le montant M ?
Si on connaît une solution pour tous les M \(-\) P avec P pièce du système monétaire, alors il suffit de sélectionner parmi les solutions de tous ces sous-problèmes, celle qui a le nombre de pièces minimal et de lui ajouter la pièce P (ce qui fera une pièce de plus) pour obtenir une solution optimale pour M.
Question 4
Recopier et compléter le tableau suivant en calculant du bas vers le haut afin de déterminer une solution optimale pour le rendu de monnaie sur le montant 8 dans le système monétaire [1, 4, 6].
| Montant | Si on rend 1 | Si on rend 4 | Si on rend 6 | Pièces donnant un rendu minimal | Rendu minimal Rmin |
|---|---|---|---|---|---|
| 8 | ... | ... | ... | ... | ... |
| 7 | ... | ... | ... | ... | ... |
| 6 | ... | ... | ... | ... | ... |
| 5 | Reste 4 de Rmin 1 | Reste 1 de Rmin 1 | \(\emptyset\) | 1 ou 4 | 1+1=2 |
| 4 | Reste 3 de Rmin 3 | Reste 0 de Rmin 0 | \(\emptyset\) | 4 | 1+0=1 |
| 3 | Reste 2 de Rmin 1 | \(\emptyset\) | \(\emptyset\) | 1 | 1+2=3 |
| 2 | Reste 1 de Rmin 1 | \(\emptyset\) | \(\emptyset\) | 1 | 1+1=2 |
| 1 | Reste 0 de Rmin 0 | \(\emptyset\) | \(\emptyset\) | 1 | 1+0=1 |
| 0 | \(\emptyset\) | \(\emptyset\) | \(\emptyset\) | \(\emptyset\) | 0 |
| Montant | Si on rend 1 | Si on rend 4 | Si on rend 6 | Pièces donnant un rendu minimal | Rendu minimal Rmin |
|---|---|---|---|---|---|
| 8 | Reste 7 de Rmin 2 | Reste 4 de Rmin 1 | Reste 2 de Rmin 2 | 4 | 1+1=2 |
| 7 | Reste 6 de Rmin 1 | Reste 3 de Rmin 3 | Reste 1 de Rmin 1 | 1 ou 6 | 1+1=2 |
| 6 | Reste 5 de Rmin 2 | Reste 2 de Rmin 2 | Reste 0 de Rmin 0 | 6 | 1+0=1 |
| 5 | Reste 4 de Rmin 1 | Reste 1 de Rmin 1 | \(\emptyset\) | 1 ou 4 | 1+1=2 |
| 4 | Reste 3 de Rmin 3 | Reste 0 de Rmin 0 | \(\emptyset\) | 4 | 1+0=1 |
| 3 | Reste 2 de Rmin 1 | \(\emptyset\) | \(\emptyset\) | 1 | 1+2=3 |
| 2 | Reste 1 de Rmin 1 | \(\emptyset\) | \(\emptyset\) | 1 | 1+1=2 |
| 1 | Reste 0 de Rmin 0 | \(\emptyset\) | \(\emptyset\) | 1 | 1+0=1 |
| 0 | \(\emptyset\) | \(\emptyset\) | \(\emptyset\) | \(\emptyset\) | 0 |
Question 5
Quand le tableau précédent est complété, comment peut-on construire une liste de pièces optimale pour un certain montant (par exemple pour 7) ?
On part de la ligne correspondant au montant et on regarde la colonne où on a noté la ou les pièces à enlever dans la solution optimale pour se ramener à une solution optimale d'un problème plus petit. On réitère jusqu'à ce qu'on atteigne le montant de base 0.
Par exemple, pour 7 on lit qu'il faut retrancher 1 ou 6 à une solution optimale ce qui nous ramène au montant \(7 - 1=6\) ou \(7-6=1\). Pour \(6\) on lit qu'il faut retrancher 6 et on atteint alors le cas de base 0 et pour \(1\) de même en retranchant 1.
Ainsi on retrouve les solutions optimales pour 7 : \(7 = 6 + 1 \) ou \(7= 1 + 6\).
Point de cours 2 : programmation dynamique et décomposition en sous-problèmes
La programmation dynamique est une méthode de conception d'algorithmes qui s'applique à des problèmes d'optimisation où la solution finale doit rendre maximale ou minimale une certaine fonction objectif. Un algorithme de programmation dynamique n'est pas une heuristique comme c'est souvent le cas avec les algorithmes gloutons, il est en général moins performant qu'un algorithme glouton, mais il détermine une solution exacte, pas une solution approchée.
Exemples où s'applique la programmation dynamique
| Problème | Entrées | Nature de la solution | Fonction objectif à optimiser |
|---|---|---|---|
| Rendu de monnaie | Un montant à rendre | Une liste de pièces de somme égale au montant | Le nombre de pièces doit être minimal |
| Sac à dos | Listes de poids et de valeurs d'objets et une capacité de sac à dos | Une sélection d'objets compatible avec la capacité du sac | La somme des valeurs des objets doit être maximale |
| Alignement de séquences | Deux séquences de gènes | Un alignement des deux séquences avec éventuellements des trous | La somme des pénalités doit être minimale, sachant que chaque trou ou différence dans l'alignement est pénalisé |
| Chemin minimal dans un triangle de nombres | Triangle de nombres | Un chemin du sommet vers la base du triangle | La somme des nombres sur le chemin doit être minimale |
Voici les trois étapes de la programmation dynamique :
- Étape 1 Décomposition en sous-problèmes : On exprime la solution optimale du problème en fonction de solutions optimales de sous-problèmes similaires : on fait apparaître une sous-structure optimale à travers une relation de récurrence.
- Étape 2 Calcul et mémorisation des solutions des sous-problèmes : On résout les sous-problèmes en partant du bas : les cas de base et en remontant vers le haut : le problème initial, et on mémorise les résultats intermédiaires dans une structure de données (par exemple un tableau).
- Étape 3 Construction de la solution finale : À l'issue de l'étape 2, on a l'optimum de la fonction objectif mais il reste à construire la solution finale. On peut le faire en parcourant dans l'autre sens, du haut vers le bas, la structure de données où on a mémorisé les résultats de tous les sous-problèmes.
En programmation dynamique on évite les redondances de calcul⚓︎
Exercice 2
💻 Saisir ses réponses sur Capytale
Question 1
Dans l'exercice 1 question 3 on a déterminé une relation de récurrence, qui dans un système monétaire fixé par une liste pieces de valeurs de pièces, permet d'exprimer une solution optimale pour un certain montant M en fonction des solutions optimales pour les montants M \(-\) P où P décrit l'ensemble des valeurs du système monétaire.
On met ainsi en oeuvre l'étape 1 caractéristique de la programmation dynamique : la décomposition en sous-problèmes.
Compléter ci-dessous le code de la fonction récursive rendu_monnaie1 à l'aide de la relation de récurrence déterminée dans l'exercice 1 question 3.
def rendu_monnaie1(montant, pieces):
"""Renvoie le nombre minimal de pièces pour rendre la monnaie
sur montant avec le système monétaire pieces qui contient une pièce de 1"""
if montant == 0:
return 0
rmin = montant # montant pièces de 1, pire des cas
for p in pieces:
if p <= montant:
rmin = min(rmin, 1 + rendu_monnaie1(montant - p, pieces))
return rmin
def test_rendu_monnaie1():
assert rendu_monnaie1(10, [1, 2]) == 5
assert rendu_monnaie1(8, [1, 4, 6]) == 2
print("tests réussis")
test_rendu_monnaie1()
Question 2
L'exécution du jeu de tests unitaires pour rendu_monnaie1 ne laissait guère de doutes sur la mauvaise complexité de l'algorithme implémenté. Dans cette question on considère le système monétaire simplifié constitué de deux pièces 1 et 2.
-
Tester
rendu_monnaie1(15, [1, 2])et comparer avec le temps mis pour déterminer la solution à la main. -
Pour simplifier, on note
r(m)l'évaluation derendu_monnaie1(m, [1, 2]).- Dessiner l'arbre d'appels récursifs de
r(5). - On note \(a(m)\) le nombre d'appels de fonctions pour calculer
r(m). Exprimer \(a(m)\) en fonction de \(a(m-1)\) et \(a(m-2)\) pour \(m \geqslant 2\) (on comptera l'appel initial der(m)et les appels récursifs). Sachant que \(a(1)=2\) et \(a(0)=1\), calculer les premiers termes. En ajoutant \(1\) à chaque terme, quelle suite reconnaît-on ? - En déduire une estimation de la complexité de
rendu_monnaie1par rapport au montant d'entrée avec le système monétaire[1, 2]. Ce résultat peut se généraliser à tous les systèmes monétaires de plus d'une pièce.
- Dessiner l'arbre d'appels récursifs de
Le rendu de monnaie optimal pour 15 est \(15=7 \times 2 + 1\) et peut s'obtenir avec l'algorithme glouton car on peut vérifier que le système [1, 2] est canonique : l'algorithme glouton est optimal pour tous les montants inférieurs à \(1+2=3\).
En revanche, rendu_monnaie1(15, [1, 2]) ne se termine pas dans un temps raisonnable et bloque la page web ce qui dénote une complexité très mauvaise.
En dessinant l'arbre d'appels de r(5) on peut observer une forte redondance de calculs dans les appels récursifs imbriqués :
- le calcul de
r(5)nécessite ceux der(4)etr(3) - le calcul de
r(4)nécessite ceux der(3)etr(2) - le calcul de
r(3)nécessite ceux der(2)etr(1) - le calcul de
r(2)nécessite ceux der(1)etr(0) - le calcul de
r(1)nécessite le calcul der(0)
Comme le système monétaire contient deux pièces 1 et 2, pour \(m \geqslant 2\) on a l'appel initial et deux appels récursifs donc \(a(m)=1 + a(m-1)+a(m-2)\). Comme \(a(1)=2\) et \(a(0)=1\) on a la suite :
\(1, 2, 4, 7, 12, 20, 33 \ldots\)
En ajoutant \(1\) à chaque terme, on reconnaît la suite de Fibonacci :
\(2,3,5,8,13,21,34 \ldots\)
Or on sait que le terme de rang \(m\) de la suite de Fibonacci est égale à \(c \times ((1+\sqrt{5})/2)^{m}\).
On en déduit que par rapport à la taille \(m\) du montant à rendre, le nombre d'appels récursifs et donc la complexité de l'algorithme (car le travail à faire par appel récursif est constant) est exponentielle, en \(O(((1+\sqrt{5})/2)^{m})\).
Question 3
Dans le code ci-dessous, la fonction récursive rendu_monnaie est identique à rendu_monnaie1 sauf qu'elle enregistre dans un dictionnaire memo toute solution de sous-problème calculée et que si le sous-problème a déjà sa solution stockée dans memo alors elle la renvoie directement. Cette technique où le dictionnaire memo agit comme un cache mémoire s'appelle la mémoïsation.
- Compléter le code de la fonction auxiliaire
rendu_monnaiedansrendu_monnaie_memoci-dessous. - Chaque solution de sous-problème n'est calculée qu'une fois. Quel est le nombre maximal de sous-problèmes pour un montant d'entrée ? Quelle complexité peut-on attendre pour cet algorithme avec mémoïsation par rapport au montant d'entrée ?
On a \(M\) sous-problèmes pour un montant \(M\) : les montants inférieurs de \(0\) à \(M-1\). En comptant le problème initial cela donne \(M+1\) solutions à calculer et donc une complexité linéaire en \(O(M)\) par rapport au montant \(M\).
def rendu_monnaie_memo(montant, pieces):
"""Renvoie le nombre minimal de pièces pour rendre la monnaie
sur montant avec le système monétaire pieces qui contient une pièce de 1"""
def rendu_monnaie(montant, pieces):
if montant not in memo:
rmin = montant # montant pièces de 1, pire des cas
for p in pieces:
if p <= montant:
rmin = min(rmin, 1 + rendu_monnaie(montant - p, pieces))
memo[montant] = rmin
return memo[montant]
memo = {0: 0}
return rendu_monnaie(montant, pieces)
def test_rendu_monnaie_memo():
assert rendu_monnaie_memo(10, [1, 2]) == 5
assert rendu_monnaie_memo(8, [1, 4, 6]) == 2
systeme_euro = [1, 2, 5, 10, 20, 50, 100, 200, 500]
assert rendu_monnaie_memo(49, systeme_euro) == 5
assert rendu_monnaie_memo(76, systeme_euro) == 4
print("tests réussis")
test_rendu_monnaie_memo()
Exercice 3
💻 Saisir ses réponses sur Capytale
Question 1
Dans l'exercice 2, on a exploité la formule de récurrence mise en évidence par la décomposition en sous-problèmes pour construire une solution avec un algorithme récursif, ce qui correspond à une descente du haut (le problème initial) jusqu'au bas (les cas de base). Les calculs (sélection de la meilleure solution parmi toutes celles des sous-problèmes) sont cependants effectués dans la phase de remontée du bas vers le haut.
L'algorithme récursif est élégant mais cache la complexité des calculs puisque les sous-problèmes se chevauchent (contrairement aux algorithmes de type Diviser Pour Régner) et on a dû mettre en oeuvre une technique de mémoïsation pour éviter les redondances de calcul et enregistrer les solutions des sous-problèmes dans une structure de données.
On souhaite dans cette question traduire dans un algorithme itératif la progression des calculs du bas vers le haut effectués dans le tableau de la question 4 de l'exercice 1. Pour construire la solution optimale d'un montant M, on parcourt tous les sous-problèmes d'un montant m allant de 0 à M et pour chaque m on calcule la solution optimale (nombre minimal de pièces) comme pour l'algorithme récursif en tirant partie du fait que les solutions des sous-problèmes plus petits ont déjà été calculées dans le tableau memo.
Compléter la fonction rendu_monnaie_dyna.
def rendu_monnaie_dyna(montant, pieces):
"""Renvoie le nombre minimal de pièces pour rendre la monnaie
sur montant avec le système monétaire pieces qui contient une pièce de 1
"""
memo = [0 for _ in range(montant + 1)]
for m in range(1, montant + 1):
memo[m] = m # m pièces de 1
for p in pieces:
if p <= m:
memo[m] = min(memo[m], 1 + memo[m - p])
return memo[montant]
def test_rendu_monnaie_dyna():
assert rendu_monnaie_dyna(10, [1, 2]) == 5
assert rendu_monnaie_dyna(8, [1, 4, 6]) == 2
systeme_euro = [1, 2, 5, 10, 20, 50, 100, 200, 500]
assert rendu_monnaie_dyna(49, systeme_euro) == 5
assert rendu_monnaie_dyna(76, systeme_euro) == 4
print("tests réussis")
test_rendu_monnaie_dyna()
Question 2
On dispose désormais d'au moins deux algorithmes (un récursif et un itératif) permettant de déterminer l'optimum de la fonction objectif c'est-à-dire le nombre minimal de pièces. Dans cette question, on met en oeuvre l'étape 3 caractéristique de la programmation dynamique : la construction d'une solution finale.
Il suffit d'enregister pour chaque montant m de la boucle représentant un sous-problème, la valeur p de la pièce qui ramène au sous-problème m - p donnant la solution optimale pour m. On peut ainsi remplir un tableau choix et quand on est arrivé en haut (le montant du problème initial), on parcourt ce tableau choix à rebours pour reconstruire une liste de pièces optimale.
Compléter la fonction rendu_monnaie_dyna_solution. On prendra toujours la dernière pièce examinée qui permet de se ramener à un sous-problème optimal.
def rendu_monnaie_dyna_solution(montant, pieces):
"""Renvoie un couple avec :
- le nombre minimal de pièces pour rendre la monnaie
sur montant avec le système monétaire pieces qui contient une pièce de 1
- une liste de pièces réalisant cet optimum
"""
memo = [0 for _ in range(montant + 1)]
choix = [0 for _ in range(montant + 1)]
for m in range(1, montant + 1):
memo[m] = montant # m pièces de 1
for p in pieces:
if p <= m:
if memo[m - p] + 1 <= memo[m]:
memo[m] = 1 + memo[m - p]
choix[m] = p
solution = [choix[montant]]
m = montant - choix[montant]
while m != 0:
solution.append(choix[m])
m = m - choix[m]
return (memo[montant], solution)
def test_rendu_monnaie_dyna_solution():
assert rendu_monnaie_dyna_solution(8, [1, 4, 6]) == (2, [4, 4])
systeme_euro = [1, 2, 5, 10, 20, 50, 100, 200, 500]
assert rendu_monnaie_dyna_solution(49, systeme_euro) == (5, [20, 20, 5, 2, 2])
assert rendu_monnaie_dyna_solution(76, systeme_euro) == (4, [50, 20, 5, 1])
Point de cours 3 : programmation dynamique et redondance des calculs
La programmation dynamique détermine une solution optimale d'un problème à partir des solutions optimales de sous-problèmes similaires (sous-struture optimale). Cela nous conduit naturellement à l'écriture d'un algorithme récursif de résolution.
Cependant, contrairement aux algorithmes Diviser Pour Régner, où les sous-problèmes sont indépendants, dans les problèmes de programmation dynamique les sous-problèmes peuvent se chevaucher.
Un algorithme récursif naïf va donc calculer plusieurs fois les solutions des mêmes sous-problèmes. La mémoïsation permet d'éviter ces redondances de calcul : on améliore notablement la complexité temporelle (d'exponentielle à linéaire pour le rendu de monnaie) au prix d'une plus grande complexité spatiale :
- on enregistre chaque solution de sous-problème dans une structure de données
memo(dictionnaire ou tableau qui permettent l'accès en temps constant) - l'algorithme récursif vérifie d'abord si le sous-problème traité n'est pas déjà stocké dans
memoavant de calculer sa solution et enregistre toute nouvelle solution dansmemo
En programmation dynamique, un algorithme récursif procède de haut en bas en décomposant d'abord le problème et il doit être mémoisé pour être efficace. Mais, avec un algorithme itératif, on peut aussi effectuer les calculs de bas en haut en progressant des plus petits sous-problèmes jusqu'aux plus grands et en enregistrant toutes les solutions calculées dans un tableau.
Dans tous les cas, l'objectif de la programmation dynamique est d'éviter la redondance des calculs : on calcule toutes les solutions de sous-problèmes nécessaires mais une seule fois !
Différences entre Diviser Pour Régner et Programmation dynamique
Les méthodes de programmation dynamique et Diviser Pour Régner permettent de résoudre un problème en le décomposant en sous-problèmes mais se distinguent en de nombreux points :
- Dans la méthode Diviser Pour Régner les sous-problèmes sont indépendants et ne se chevauchent pas, alors qu'en programmation dynamique cette contrainte n'existe pas et les sous-problèmes peuvent se chevaucher.
- La méthode Diviser Pour Régner est choisie principalement avec l'objectif de réduire la complexité temporelle, alors qu'en programmation dynamique l'objectif principal est de construire une solution correcte.
- En général, avec Diviser Pour Régner la taille des sous-problèmes est une fraction de celle du problème initial, alors qu'en programmation dynamique elle peut être simplement décrémentée de quelques unités.
En résumé, la programmation dynamique s'applique à une plus grande variété de problèmes. Diviser Pour Régner peut être vue comme un cas particulier de la programmation dynamique où la décomposition en sous-problèmes est toujours la même et où les sous-problèmes sont indépendants.