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].
Les applications suivantes et la correction guidée sont réservées aux membres Premium
La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.