Comment implémenter un algorithme glouton simple (rendu de monnaie, allocation de salles) ?
En triant les candidats selon un critère local (ordre décroissant des pièces, ordre croissant des fins) puis en les sélectionnant un à un tant que la contrainte est satisfaite
L'objectif
Construire une solution approchée (ou optimale dans certains cas) à un problème d'optimisation par choix locaux successifs.
Le principe
Un algorithme glouton trie les candidats selon un critère (décroissant pour les pièces de monnaie : on épuise la plus grosse d'abord ; croissant des dates de fin pour l'allocation : on libère la salle au plus tôt) puis sélectionne séquentiellement ceux qui respectent la contrainte.
La méthode
- 1Je définis le critère de tri adapté au problème (décroissant sur les pièces, croissant sur les fins d'activités).
- 2Je trie les candidats selon ce critère à l'aide de
sorted(..., reverse=True/False)ousorted(..., key=...). - 3Je parcours les candidats triés et j'en sélectionne chacun s'il respecte la contrainte (montant restant positif, horaire compatible).
- 4Je renvoie la solution construite (liste de pièces, liste d'activités).
Exemple corrigé
Difficulté croissante de 1 à 3
Exercices aujourd'hui0 / 3
Prêt à t'entraîner ?
Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.