Comment implémenter un algorithme glouton simple (rendu de monnaie, allocation de salles) ?
Construire une solution approchée (ou optimale dans certains cas) à un problème d'optimisation par choix locaux successifs.
Rendre \text{€} avec les pièces disponibles pieces = [50, 20, 10, 5, 2, 1] : écrire une fonction rendu(n, pieces) qui renvoie la liste des pièces utilisées.
Construire une solution approchée (ou optimale dans certains cas) à un problème d'optimisation par choix locaux successifs.
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.
sorted(..., reverse=True/False) ou sorted(..., key=...).Rendre \text{€} avec les pièces disponibles pieces = [50, 20, 10, 5, 2, 1] : écrire une fonction rendu(n, pieces) qui renvoie la liste des pièces utilisées.
Critère : toujours choisir la plus grosse pièce qui ne dépasse pas le montant restant (tri décroissant).
sorted(..., reverse=True/False) ou sorted(..., key=...).pieces est déjà triée par ordre décroissant : .
On parcourt : (on passe) ; , on prend deux fois (reste ) ; (on passe) ; , on prend (reste ) ; , on prend (reste ).
Je renvoie [20, 20, 5, 2].
def rendu(n, pieces):
pieces = sorted(pieces, reverse=True)
R = []
for p in pieces:
while n >= p:
R.append(p)
n -= p
return R
rendu(47, [50,20,10,5,2,1]) renvoie [20, 20, 5, 2].
Allocation de salle : on dispose de cours C = [(9,11),(10,12),(11,13),(13,15),(14,16)] (chaque tuple est (début, fin)). Choisir un ensemble maximal de cours deux à deux compatibles.
Rendre \text{€} avec pieces = [5, 4, 1] par l'algorithme glouton et comparer à l'optimum.
Rendre la monnaie pour centimes avec pieces = [50, 20, 10, 5, 2, 1]. Écrire l'algorithme glouton et donner la liste des pièces utilisées.
Un livreur doit déposer des colis dans créneaux horaires disjoints ; on lui propose C = [(8,10),(9,11),(10,12),(11,13),(12,14),(13,15)]. Sélectionner par algorithme glouton un ensemble maximal de créneaux deux à deux compatibles (un créneau se termine avant le début du suivant).
Crée ton compte pour accéder à la fiche et aux exercices