Dérouler la monnaie

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 18 — La programmation dynamique

Énoncé

Pour le système ${10, 7, 1}$ et la somme $s = 14$ , dresser à la main la table des valeurs $N [0..14]$ et des choix effectués. Reconstruire pas à pas la solution optimale et comparer le résultat avec le choix glouton. Quelle est la solution pour $s = 20$ ?

Corrigé

Table des valeurs calculées :

$v$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$N [v]$	0	1	2	3	4	5	6	1	2	3	1	2	3	4	2
choix	—	1	1	1	1	1	1	7	7	7	10	10	10	10	7

Reconstruction pour $s = 14$ :
$N [14]$ est minimal en choisissant la pièce $7$ (menant à la somme résiduelle $14 - 7 = 7$ ).
$N [7]$ est minimal en choisissant la pièce $7$ (menant à la somme résiduelle $7 - 7 = 0$ ). Le rendu optimal est donc [7, 7], soit 2 pièces. L'algorithme glouton aurait choisi la pièce de 10, laissant un reste de 4 à rendre avec des pièces de 1, totalisant 5 pièces ( $10 + 1 + 1 + 1 + 1$ ).
Pour $s = 20$ : $N [20] = 2$ par le choix de deux pièces de $10$ . Dans ce cas, le glouton trouve la même solution optimale.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.