Vue d'ensemble
Imagine que tu doives rendre la monnaie à un client, ou choisir le plus d'activités possible dans une journée. À chaque étape, une stratégie tentante consiste à prendre ce qui paraît le meilleur ici et maintenant, sans se soucier de la suite, et sans jamais revenir sur une décision. C'est exactement l'idée d'un algorithme glouton (en anglais greedy, « gourmand »). Cette fiche te montre pourquoi cette idée est à la fois puissante, rapide… et parfois trompeuse.
Prérequis
- Boucles
foretwhile, testsif. - Manipulation de listes Python (parcours,
append, tri). - Notion de tri d'une liste (souvent on trie avant de dérouler le glouton).
- Complexité temporelle : savoir dire qu'un algorithme est en , , etc.
Le glouton, un piège d'oral. « Votre algorithme donne-t-il toujours l'optimum ? » est LA question qui déstabilise en colle. Nos mentors alumni X · Centrale · Mines t'entraînent à démasquer un glouton non optimal en trente secondes, contre-exemple à l'appui.
Trouver un mentor →1. Le principe glouton
Un algorithme glouton construit une solution par étapes. À chaque étape, il fait le choix qui semble le meilleur localement (le plus « gourmand ») selon un critère fixé, puis il passe à l'étape suivante sans jamais remettre en cause les choix déjà faits.
Trois mots résument tout : étapes (on avance morceau par morceau), local (on regarde seulement ce qui est le mieux à cet instant, jamais l'avenir), irrévocable (aucun retour en arrière). Ce dernier point est ce qui rend un glouton rapide… et ce qui l'empêche parfois d'atteindre l'optimum.
- Identifier les « objets » parmi lesquels choisir (des pièces, des activités…).
- Choisir un critère de gourmandise : quel objet paraît le meilleur à chaque étape ? (souvent après un tri).
- Parcourir les objets dans cet ordre, ajouter un objet à la solution s'il est « compatible » avec ce qui a déjà été choisi.
- Ne jamais revenir en arrière.
- Se méfier : vérifier sur des exemples, et surtout chercher un contre-exemple avant d'affirmer que le glouton est optimal.
2. Exemple central — le rendu de monnaie
Le problème : rendre une somme donnée avec le moins de pièces possible, à partir d'un système de pièces disponibles en quantité illimitée. Avec le système euro , le glouton naturel est : à chaque étape, prendre la plus grande pièce inférieure ou égale à ce qui reste à rendre.
def rendu_glouton(systeme, somme):
systeme = sorted(systeme, reverse=True) # pieces de la plus grande a la plus petite
pieces = []
for piece in systeme:
while somme >= piece:
somme -= piece
pieces.append(piece)
return pieces
euro = [1, 2, 5, 10, 20, 50, 100, 200]
print(rendu_glouton(euro, 68)) # [50, 10, 5, 2, 1]def rendu_glouton(systeme, somme):On définit la fonction : systeme est la liste des valeurs de pièces disponibles, somme est le montant (en unités, ici en euros entiers) qu'il faut rendre.systeme = sorted(systeme, reverse=True)On trie les pièces de la plus grande à la plus petite. C'est le cœur du critère glouton : on veut essayer d'abord les grosses pièces. reverse=True inverse l'ordre croissant habituel.pieces = []Liste (vide au départ) qui va accumuler les pièces effectivement rendues.for piece in systeme:On parcourt les valeurs de pièces, de la plus grande à la plus petite.while somme >= piece:Tant que la pièce courante « tient » dans ce qui reste à rendre, on la reprend encore une fois. Le while permet d'utiliser plusieurs fois la même valeur (par exemple deux pièces de 1).somme -= pieceOn retire la valeur de la pièce du montant restant : on vient de « rendre » cette pièce.pieces.append(piece)On enregistre la pièce rendue dans la solution.return piecesUne fois toutes les pièces passées, le montant restant vaut 0 (car la pièce 1 finit toujours le travail) et on renvoie la liste des pièces choisies.Déroulons sur un exemple concret : rendre 68. La plus grande pièce est 50 → reste 18. La plus grande pièce est 10 → reste 8. Puis 5 → reste 3, puis 2 → reste 1, puis 1 → reste 0. Total : 5 pièces.
| Étape | Reste à rendre | Plus grande pièce reste | Pièces rendues |
|---|---|---|---|
| départ | 68 | 50 | [50] |
| 2 | 18 | 10 | [50, 10] |
| 3 | 8 | 5 | [50, 10, 5] |
| 4 | 3 | 2 | [50, 10, 5, 2] |
| 5 | 1 | 1 | [50, 10, 5, 2, 1] |
| fin | 0 ✓ | — | 5 pièces ✓ |
while retire une pièce à la fois : si tu ne disposes que de la pièce 1 pour rendre , tu fais tours. Le nombre de tours dépend donc du montant, pas seulement du nombre de types de pièces. Le tri initial, lui, coûte où est le nombre de types de pièces.3. Le piège capital — le glouton n'est pas toujours optimal
Voici le point le plus important de toute la fiche. Prends un système de pièces différent : . On veut rendre 6. Que fait le glouton ?
systeme = [1, 3, 4]
print(rendu_glouton(systeme, 6)) # [4, 1, 1] -> 3 piecessysteme = [1, 3, 4]Un système de pièces inventé : on ne dispose que des valeurs 1, 3 et 4.print(rendu_glouton(systeme, 6))On applique EXACTEMENT le même glouton que pour l'euro. Il trie en [4, 3, 1], prend d'abord 4 (reste 2) ; 4 et 3 ne tiennent plus dans 2, donc il prend 1 puis 1 (reste 0). Résultat : [4, 1, 1], soit 3 pièces.| Étape | Reste | Plus grande pièce reste | Pièces rendues |
|---|---|---|---|
| départ | 6 | 4 | [4] |
| 2 | 2 | 1 (4 et 3 trop grands) | [4, 1] |
| 3 | 1 | 1 | [4, 1, 1] |
| fin | 0 ✓ | — | 3 pièces |
Mais existe-t-il mieux ? Oui ! : deux pièces de 3 suffisent. L'optimum est donc 2 pièces, alors que le glouton en a rendu 3. Le glouton s'est trompé en prenant la pièce 4 tout de suite.
# Verification de l'optimum par programmation dynamique
def rendu_optimal(systeme, somme):
INF = float('inf')
dp = [0] + [INF] * somme
for s in range(1, somme + 1):
for p in systeme:
if p <= s and dp[s - p] + 1 < dp[s]:
dp[s] = dp[s - p] + 1
return dp[somme]
print(rendu_optimal([1, 3, 4], 6)) # 2dp = [0] + [INF] * sommeTableau : dp[s] = nombre minimal de pièces pour rendre exactement s. On sait rendre 0 avec 0 pièce ; toutes les autres cases valent « l'infini » tant qu'on ne les a pas améliorées.for s in range(1, somme + 1):On calcule l'optimum pour chaque montant de 1 jusqu'à la somme visée.for p in systeme:Pour rendre s, on essaie toutes les pièces possibles comme « dernière pièce rendue » — c'est justement ce que le glouton ne fait pas.if p <= s and dp[s - p] + 1 < dp[s]:Si la pièce p tient dans s, alors rendre s coûte au mieux « rendre s-p » plus cette pièce. On garde le minimum.return dp[somme]La case finale contient le vrai minimum : 2 pour et 6. Le glouton, lui, en donnait 3.Pour le système euro, le rendu glouton donne toujours le nombre minimal de pièces (système dit canonique). Mais il existe des systèmes, comme , pour lesquels le glouton est strictement pire que l'optimum : rendre 6 coûte 3 pièces au glouton contre 2 à l'optimum. La garantie d'optimalité dépend donc du système de pièces.
Trouver le contre-exemple, ça se travaille. Sur , le déclic vient de . Nos mentors alumni X · Centrale · Mines te donnent la méthode pour construire un contre-exemple à la demande, sur n'importe quel énoncé de glouton.
Trouver un mentor →4. Deuxième exemple — la sélection d'activités (glouton optimal)
Un problème où, cette fois, le glouton est optimal. On dispose d'activités, chacune avec une heure de début et une heure de fin. On ne peut faire qu'une activité à la fois. Objectif : en réaliser le plus grand nombre possible sans chevauchement. Le bon critère glouton (souvent contre-intuitif) : choisir à chaque étape l'activité compatible qui finit le plus tôt, car elle libère le temps au plus vite.
def selection_activites(activites):
activites = sorted(activites, key=lambda x: x[1]) # tri par heure de fin
choisies = []
fin = 0
for debut, f in activites:
if debut >= fin: # compatible avec la derniere choisie
choisies.append((debut, f))
fin = f
return choisies
acts = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 11), (12, 16)]
print(selection_activites(acts)) # [(1, 4), (5, 7), (8, 11), (12, 16)]activites = sorted(activites, key=lambda x: x[1])On trie les activités par heure de fin croissante. x[1] est le deuxième élément du couple (début, fin), donc la fin. C'est LE critère glouton de ce problème.choisies = []Liste des activités retenues.fin = 0Heure de fin de la dernière activité choisie. Au départ, aucune activité choisie, on met 0 (avant tout).for debut, f in activites:On parcourt les activités dans l'ordre de fin croissante. debut et f sont le début et la fin de l'activité courante.if debut >= fin:On garde l'activité seulement si elle commence après (ou pile à) la fin de la dernière retenue : pas de chevauchement.choisies.append((debut, f))On l'ajoute à la sélection.fin = fOn met à jour l'heure de fin de référence : les prochaines activités devront commencer après f.| Activité (début, fin) | fin avant | debut >= fin ? | Décision |
|---|---|---|---|
| (1, 4) | 0 | 1 ≥ 0 : oui | on garde → fin = 4 |
| (3, 5) | 4 | 3 ≥ 4 : non | on jette |
| (0, 6) | 4 | 0 ≥ 4 : non | on jette |
| (5, 7) | 4 | 5 ≥ 4 : oui | on garde → fin = 7 |
| (8, 11) | 7 | 8 ≥ 7 : oui | on garde → fin = 11 |
| (12, 16) | 11 | 12 ≥ 11 : oui | on garde → 4 activités ✓ |
5. Reconnaître un problème glouton — et rester méfiant
- Peut-on décider par étapes ? La solution se construit-elle en ajoutant un objet à la fois ?
- Y a-t-il un critère local naturel ? « le plus grand », « celui qui finit le plus tôt », « le moins cher »…
- Le critère se justifie-t-il intuitivement ? (« finir tôt libère du temps ».)
- Test décisif : puis-je trouver un contre-exemple ? Fabrique de petits cas à la main. Si le glouton échoue une seule fois, il n'est pas optimal.
- Si tu ne trouves pas de contre-exemple et que le critère se justifie, le glouton est un bon candidat — mais en Sup, on ne te demande pas de prouver l'optimalité, seulement de la discuter.
[4,1,1] rend bien 6 : elle est valide. Elle n'est simplement pas minimale. L'erreur d'un glouton non optimal n'est jamais de se tromper de total, c'est de ne pas faire au mieux.6. Exercices corrigés
Avec le système euro , donne, à la main, la liste des pièces rendues par rendu_glouton pour la somme 87, et le nombre de pièces.
Voir la correction détaillée
[50, 20, 10, 5, 2], soit 5 pièces. (Le système euro étant canonique, c'est bien l'optimum.)On considère le système de pièces . Montre que le glouton n'est pas optimal pour rendre la somme 10 : donne le rendu glouton et une meilleure solution.
Voir la correction détaillée
[8, 1, 1] = 3 pièces.[5, 5] = 2 pièces.On dispose des activités données en . Applique le glouton « finir le plus tôt » : donne les activités retenues et leur nombre.
Voir la correction détaillée
fin = 0. (1,3) : 1 ≥ 0 → on garde, fin = 3.Récap final — Ce qu'il faut absolument retenir
Un glouton avance par étapes, choisit le meilleur localement, ne revient jamais en arrière : rapide, mais pas toujours optimal. Le réflexe d'oral, c'est le contre-exemple.
- Sais-tu énoncer les trois mots-clés du glouton : par étapes, choix local, irrévocable ?
- Sais-tu écrire et décrypter le rendu de monnaie glouton (tri décroissant +
while somme >= piece) ? - Sais-tu dérouler le glouton euro sur une somme donnée, par exemple 68 →
[50,10,5,2,1]? - Sais-tu produire le contre-exemple pour 6 : glouton 3 pièces contre optimum 2 () ?
- Sais-tu qu'un système où le glouton est toujours optimal s'appelle canonique, et que c'est une propriété du système, pas du glouton ?
- Sais-tu que le glouton donne toujours une solution valide, la question étant seulement de savoir si elle est optimale ?
- Sais-tu appliquer le glouton « finir le plus tôt » pour la sélection d'activités, et pourquoi ce critère (et pas « commencer tôt ») ?
- Sais-tu, face à « ce glouton est-il optimal ? », chercher d'abord un contre-exemple avant de répondre ?