⚡ 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
🪙 Construction gloutonne
Montant restant : —
✨ Meilleure combinaison
Calculée par programmation dynamique.
🔍 Déroulement des décisions
| Étape | Valeur | Quantité | 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.