Université de Sidi Bel Abbès
Département d’Informatique
Master WIC/ ISI/ RSSI 2018/2019
Algorithmique et Complexité
TP5 : Algorithme de programmation dynamique vs algorithme glouton
Problème rendre de la monnaie
Décembre 2018
Considérons n pièces de monnaie {1, 2, 3,…n} de valeurs positives d1, d2,…, dn avec d1=1 ; et
un montant M à rendre.
L’objectif consiste à utiliser le moins de pièces possibles pour rendre le montant M. Chaque
pièce pouvant être utilisée plusieurs fois.
Partie 1 : (à préparer pour la semaine du 09/12/2018)
On veut résoudre ce problème en utilisant une approche de programmation dynamique.
On définit alors une matrice P [0..n 0..M] où: P [i, j] est le nombre minimum de pièces si le
choix est parmi les pièces {1, …, i} sans dépasser le montant j.
Par exemple pour n=3, M=20, d1=1, d2=18, d3=10 la solution optimale est 2 pièces de 10.
On donne les équations de récursives :
P[0 , j ]= ∞ ; P[ i, 0 ]= 0 i=0...n et j=0..M
P[i , j] = min (1+ P[i , j-di] , P[i-1 , j]) Si j>= di
P[i-1 , j] Sinon
Sachant que l’utilisateur doit introduire le montant M, le nombre de pièces n et les valeurs des
différentes pièces d1, d2,…, dn :
1. Ecrire le programme java permettant de calculer le nombre minimal de pièces
requises pour rendre le montant M.
2. Ecrire la fonction permettant d’afficher la matrice P.
3. Ecrire la fonction permettant de retrouver les pièces concernées.
Partie 2 : (à préparer pour la semaine du 16/12/2018)
Ecrire le programme java permettant de résoudre ce problème en utilisant une approche
vorace (gloutonne).
On commence par trier les pièces en ordre décroissant selon leurs valeurs.
Pour calculer, le nombre de pièces à utiliser pour chaque valeur di il suffit de diviser le
montant à rendre par la valeur de la pièce.
Par exemple pour n=3, M=20, d1=1, d2=18, d3=10 la solution vorace donnera 1 pièce de 18
et 2 pièces de 1.
