Rendu de monnaie
Définition : Problème : RenduMonnaie
Entrée :
\(S=(c_1,c_2,\ldots,c_n)\) : système de monnaie ou \(c_i\) représente la valeur de la pièce (ou du billet) \(i\) avec \(c_1=1\) et tous les \(c_i\) sont croissants et positifs
\(v\) : entier
Sortie :
\(T=(x_1,x_2,\ldots,x_n)\) : n-uplet (même \(n\) que \(S\) où chaque \(x_i\) indique le nombre de pièces \(c_i\) à utiliser dans le but d'atteindre précisément la valeur \(v\).
Autrement dit, on cherche à minimiser \(\sum_{i=1}^n x_i\) avec pour contrainte \(\sum_{i=1}^n x_i c_i = v\)
Exemple : Système euro
On se place dans le système d'euro, plus précisément des centimes (pour simplifier), c'est-à-dire que \(S=(1,2,5,10,20,50)\).
On souhaite rendre 42 centimes de monnaie et on cherche à minimiser le nombre de pièces à rendre.
L'algorithme glouton (vu en classe de première) cherche toujours à rendre la pièce la plus élevée :
20 cts est la plus grosse pièce possible qui ne dépasse pas 42. On choisit la pièce 20 cts, il reste 22 cts.
On choisit ensuite 20 cts, il reste 2 cts.
On choisit ensuite 2 cts, il reste 0 cts.
Ainsi, on a \(T=(0,1,0,0,2,0)\) ce qui fait \(\sum_{i=1}^n x_i = 3\) et la contrainte est bien respectée.
Il n'est pas possible de rendre 42 centimes avec seulement deux pièces, et on ne prouvera pas pourquoi (désolé, vous verrez ça en études supérieures).
Définition : Système canonique
Un système de monnaie est dit canonique s'il est possible de résoudre le problème RenduMonnaie avec un algorithme glouton.
Il existe des systèmes non canoniques (par exemple \(S=(1,3,4)\) car le rendu de 6 va donner :
Algo glouton : 4 + 1 + 1 = 6 (3 pièces)
Optimal : 3 + 3 = 6 (2 pièces)
Première idée
Une première solution consiste à réaliser une fonction rendu_monnaie(S, v) qui s'appelle récursivement sous la forme rendu_monnaie(S, v-c) pour tout c dans S et qui conserve le rendu_monnaie(S, v-c) ayant la valeur de retour la plus faible. La fonction rendu_monnaie() renvoit donc le nombre de pièces optimales pour la résolution du problème.
Attention : Une solution non exploitable
Cette première solution est lourde à mettre en place car elle va recalculer plusieurs fois les mêmes valeurs. On peut calculer le nombre d'appels nécessaires en prenant \(S=(1,2)\).
rendu_monnaie(1)devra appelerrendu_monnaie(0)rendu_monnaie(2)devra appelerrendu_monnaie(1)etrendu_monnaie(0)sauf querendu_monnaie(1)appelle aussirendu_monnaie(0)ainsi de suite...
Donc pour les valeurs \(v = \{0,1,2,3,4,5\}\) on obtient ce nombre d'appels : \(\{1, 2, 4, 7, 12, 20\}\) qui correspond à ... la suite de Fibonnacci \(F_n\) décallée de 3 à laquelle on a retiré 1 à chaque valeur : \(\{0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots\}\).
Donc le nombre d'appels pour une valeur \(v\) quelconque est de \(F_{v+3}-1\)
Or, pour \(v=42\) on a \(F_{v+3} = F_{45} = 1134903170\) soit beaucoup trop d'appels récursif pour une si petite valeur.
Fondamental : Deuxième idée
Cette fois-ci, on va utiliser le principe de progammation dynamique pour notre algorithme. On va initialiser une variable qui permettra de stocker les résultats déjà calculés de rendu_monnaie(k). On pourra utiliser par exemple une liste.
En pratique, on impélmente cette mémoire en faisaint :
soit une fonction itérative avec une variable locale ;
soit une fonction récursive avec un paramètre qui contient la mémoire ;
soit une classe qui contient la mémoire en attribut ;
soit une variable globale en Python.