Les algorithmes gloutons

Choisir maintenant sans revenir en arrière

Un algorithme glouton construit sa réponse par une succession de choix considérés comme les meilleurs à l’instant présent. Une fois un choix effectué, il n’est pas remis en cause. Pour un rendu de monnaie, on peut prendre la plus grande pièce ne dépassant pas la somme restante, puis recommencer.

La stratégie doit préciser le critère : plus grande valeur, meilleur rapport valeur sur poids, plus petite durée, selon le problème. Le mot glouton ne désigne pas un programme unique. Pour évaluer une stratégie, on doit connaître l’objectif à optimiser et les contraintes qui rendent une solution admissible.

Écrivez d’abord ce que signifie « meilleur ». Dans le rendu de monnaie, l’objectif global est le nombre minimal de pièces, tandis que le critère local choisit la plus grande valeur admissible. Les deux formulations ne sont pas équivalentes. Un choix local peut améliorer immédiatement le reste à payer tout en empêchant une combinaison globale plus économique. C’est précisément ce décalage que les contre-exemples cherchent à mettre en évidence.

Le rendu de monnaie, étape par étape

Avec les pièces 5, 2 et 1, rendre 8 donne successivement 5, puis 2, puis 1 : trois pièces. Le reste décroît après chaque choix. La présence de la pièce 1 garantit que tout montant entier positif peut être atteint, si l’on suppose un stock illimité.

Le programme doit examiner les pièces dans l’ordre décroissant. La liste des pièces est une entrée du problème, pas une simple décoration. Si l’on change le système monétaire ou le stock disponible, les résultats et les garanties peuvent changer. Le cours et le simulateur supposent des pièces entières positives et un stock illimité.

def glouton(montant, pieces):
    resultat = []
    for piece in pieces:  # ordre décroissant
        while montant >= piece:
            resultat.append(piece)
            montant -= piece
    return resultat

Une solution correcte peut utiliser trop de pièces

Avec les pièces 4, 3 et 1, le rendu glouton de 6 prend 4, puis 1, puis 1. Il utilise trois pièces. Pourtant 3 + 3 rend la même somme avec deux pièces. Le choix de 4 semble bon immédiatement, mais laisse un reste peu favorable. Cet exemple suffit à réfuter l’affirmation que la stratégie est toujours optimale.

Le résultat reste valide : la somme des pièces vaut bien 6. Il faut distinguer cette propriété de l’optimalité. L’atelier compare le glouton à une recherche du nombre minimal calculée par programmation dynamique ; cette deuxième méthode est un prolongement de Terminale, pas un prérequis pour comprendre le contre-exemple.

Pour démontrer qu’un rendu de deux pièces est optimal, il suffit parfois de montrer qu’aucune pièce unique ne vaut le montant. Pour 6 avec 4, 3 et 1, une pièce est impossible et deux pièces de 3 existent : le minimum est exactement deux. On n’a pas besoin de maîtriser la programmation dynamique pour justifier ce petit cas.

Un autre terrain : le sac à dos

Supposons un sac de capacité 10 et trois objets indivisibles : A pèse 6 et vaut 12, B pèse 5 et vaut 9, C pèse 5 et vaut 9. Choisir le meilleur rapport valeur/poids conduit à prendre A, de rapport 2. Le reste de capacité 4 empêche de prendre B ou C. La valeur totale est 12.

Prendre B et C donne pourtant une masse totale 10 et une valeur 18. Les objets sont ici indivisibles : autoriser des fractions changerait le problème. Avant toute conclusion, vérifiez les hypothèses, puis comparez une solution gloutonne à une autre solution admissible.

Comparer validité, terminaison et optimalité

Ces trois propriétés répondent à trois questions différentes. La validité demande si la somme des pièces obtenues est égale au montant. La terminaison demande si le programme finit. L’optimalité demande si aucune autre solution admissible n’utilise moins de pièces. Un algorithme peut terminer avec une solution valide tout en étant sous-optimal.

Avec 4, 3 et 1, pour 10, le glouton prend 4, 4, 1, 1. Le reste suit 10, 6, 2, 1, 0 : il diminue et finit à zéro. Pourtant 4, 3, 3 utilise trois pièces. Deux pièces ne peuvent faire 10, puisque chacune vaut au plus 4 ; le minimum vaut donc trois. Cet exemple joint une trace de la stratégie, un contrôle de somme et une petite preuve du meilleur résultat possible.

Que changent les contraintes du problème ?

La présence de la pièce 1 garantit un rendu de tout entier non négatif sous stock illimité. Sans elle, un reste peut subsister. Pour 6 avec 4 et 3, le glouton prend 4 puis reste bloqué à 2, alors que 3+3 aurait réussi. On doit donc vérifier la somme finale et ne pas annoncer automatiquement un rendu complet.

Un stock limité transforme également le raisonnement : une pièce choisie peut ne plus être disponible ensuite. Dans le sac à dos, les objets indivisibles imposent de prendre ou de laisser chaque objet en entier. Un critère par rapport valeur/poids ne possède pas les mêmes garanties que dans un problème permettant des fractions. Dans les exercices, énoncez les contraintes avant de comparer les stratégies ; sinon deux solutions apparemment concurrentes peuvent résoudre deux problèmes différents.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Utiliser « valide » et « optimal » comme synonymes.

Une solution valide respecte les contraintes ; une solution optimale atteint le meilleur objectif parmi les solutions valides.

Déduire une garantie de quelques essais réussis.

Un contre-exemple peut réfuter une garantie ; des essais ne prouvent pas qu’elle vaut pour tous les cas.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2026 · Asie · Jour 1 : Compagnie de danse : relier les spectacles et charger le matériel
• Bac 2025 · Centres étrangers groupe 1 · Jour 1 : Courses d’orientation et choix glouton sur un graphe
• Bac 2025 · Amérique du Nord · Jour 2 bis - Sujet PE2 : Justification de texte et découpage optimal par programmation dynamique

Le prochain pas

• Prouver la correction et la terminaison d’un algorithme
• La programmation dynamique

Retrouver le catalogue de Première

Ce chapitre s’appuie sur le programme officiel de Première (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.