Algorithmes gloutons

Le rendu de monnaie

Imaginez une caissière qui doit rendre 2,37 € avec le moins de pièces et billets possible. Comment fait-elle ?

Elle commence par la plus grosse pièce qu'elle peut rendre, puis recommence avec le reste, et ainsi de suite.

Reste à rendre	Pièce choisie	Reste après
237 centimes	200 (2 €)	37
37 centimes	20	17
17 centimes	10	7
7 centimes	5	2
2 centimes	2	0

Résultat : 5 pièces. C'est optimal.

Cette stratégie s'appelle un algorithme glouton : à chaque étape, on prend la meilleure décision locale sans jamais revenir en arrière.

Exercice 1 - Appliquer le rendu de monnaie

Rendre 1,73 € (173 centimes) avec le système euro [200, 100, 50, 20, 10, 5, 2, 1]. Remplir le tableau étape par étape.

Correction

Reste à rendre	Pièce choisie	Reste après
173	100	73
73	50	23
23	20	3
3	2	1
1	1	0

Résultat : 5 pièces [100, 50, 20, 2, 1].

Définition

Algorithme glouton

Un algorithme glouton résout un problème d'optimisation en faisant, à chaque étape, le meilleur choix possible à cet instant, sans remettre en question les choix précédents.

Avantages : simple, rapide.

Limite : ne garantit pas toujours la solution optimale.

L'algorithme du rendu de monnaie

Entrée : une somme à rendre (en centimes), un système de pièces trié dans l'ordre décroissant
Sortie : la liste des pièces rendues

1. rendu ← liste vide
2. Pour chaque pièce p dans le système (de la plus grande à la plus petite) :
3.     Tant que somme >= p :
4.         Ajouter p à rendu
5.         somme ← somme - p
6. Retourner rendu

EUROS = [500, 200, 100, 50, 20, 10, 5, 2, 1]

def rendre_monnaie(somme: int, systeme: list[int]) -> list[int]:
    rendu = []
    for piece in systeme:
        while somme >= piece:
            rendu.append(piece)
            somme -= piece
    return rendu

Quand l'algorithme glouton échoue

Pour le système euro, la stratégie gloutonne donne toujours la solution optimale. Mais ce n'est pas toujours le cas !

Prenons un système fictif avec les pièces [1, 3, 4] et une somme de 6 :

Glouton : 4 + 1 + 1 = 3 pièces
Optimal : 3 + 3 = 2 pièces

Le glouton s'est trompé ! En choisissant 4 en premier (meilleur choix local), il a raté la meilleure solution globale.

Conclusion

Un algorithme glouton est correct quand la propriété "le meilleur choix local mène au meilleur résultat global" est vérifiée. C'est le cas pour le système euro, mais pas pour tous les systèmes de pièces.

Vérifier formellement qu'un algorithme glouton est correct nécessite une preuve mathématique. Pour l'instant, retenez l'idée : glouton = rapide, mais pas toujours optimal.

Exercice 2 - Rendre 48 centimes

Appliquer l'algorithme glouton pour rendre 48 centimes avec le système euro. Lister les pièces utilisées.

Correction

Reste	Pièce	Reste après
48	20	28
28	20	8
8	5	3
3	2	1
1	1	0

Résultat : 5 pièces [20, 20, 5, 2, 1].

Exercice 3 - Glouton en échec

Avec le système [1, 6, 10], rendre 12 centimes.

Que donne l'algorithme glouton ?
Quelle est la solution optimale ?
Conclure.

Correction

Glouton : 10 + 1 + 1 = 3 pièces.
Optimal : 6 + 6 = 2 pièces.
Le glouton a choisi 10 en premier (meilleur choix local), mais cela l'a empêché d'utiliser deux pièces de 6. Le choix localement optimal n'est pas toujours globalement optimal : le glouton échoue ici.

Exercice 4 - Identifier la stratégie gloutonne

Dans chaque situation, identifier si une stratégie gloutonne est utilisée :

Pour remplir un sac à dos de capacité limitée, on prend toujours l'objet le plus léger disponible.
Pour traverser un labyrinthe, on tourne toujours à droite quand c'est possible.
Pour trier des cartes, on cherche le minimum et on le place en premier.

Correction

Oui : on fait à chaque étape le meilleur choix local (l'objet le plus léger). Attention, ce n'est pas forcément optimal pour maximiser la valeur totale.
Oui : règle locale simple, jamais remise en question. Ne garantit pas de trouver la sortie.
Oui : c'est exactement le tri par sélection, qui est un algorithme glouton (et il est correct pour le tri).