De la théorie des graphes à l'optimisation · Chapitre 4

⚡ L'efficacité immédiate

Programmation gloutonne

Choisir le meilleur coup maintenant suffit-il à trouver la meilleure solution ? Explorez le rendu de monnaie, étape par étape, puis confrontez votre résultat à l'optimum.

✦ Tester mes connaissances — QCM

🎛️ Laboratoire de rendu de monnaie

On suppose un nombre illimité de pièces de chaque valeur. Les montants sont des entiers sans unité monétaire imposée.

Tri décroissant automatique ; maximum 30 valeurs.

📊 Résultats de l'expérience

Glouton—Pièces sélectionnées
Optimum dynamique—Minimum de pièces
Écart à l'optimum—Pièces supplémentaires

🪙 Construction gloutonne

Étape 0 / 0

Montant restant : —

✨ Meilleure combinaison

Calculée par programmation dynamique.

🔍 Déroulement des décisions

ÉtapeValeurQuantitéMontant restant
Voir la méthode optimale et sa récurrence

Pour chaque montant m, on calcule dp[m] = 1 + min(dp[m − p]) pour les pièces p ≤ m dont le sous-problème est réalisable, avec dp[0] = 0. Si aucune combinaison n'existe, dp[m] = ∞.

La table mémorise le nombre minimal de pièces. Les prédécesseurs permettent de reconstruire une combinaison optimale.

🎓 À retenir

Glouton : choisit à chaque étape autant que possible la plus grande pièce disponible, sans revenir en arrière. Le choix local n'est pas nécessairement globalement optimal.

Contre-exemple : pour 6 avec {4, 3, 1}, le glouton rend 4 + 1 + 1 (3 pièces), tandis que l'optimum est 3 + 3 (2 pièces).

Complexité : après tri des k valeurs en O(k log k), le calcul glouton des quantités coûte O(k) ; l'affichage individuel de toutes les pièces peut coûter davantage. La programmation dynamique utilisée ici coûte O(kM) en temps et O(M) en mémoire pour un montant M : c'est une complexité pseudo-polynomiale.

L'optimalité du glouton dépend du système de pièces. Un résultat optimal sur un exemple ne prouve pas qu'il l'est pour tous les montants.