Un algorithme glouton (ou “greedy”) construit une solution étape par étape, en choisissant à chaque étape le meilleur choix possible sur le moment, sans revenir en arrière. Il ne garantit pas toujours la meilleure solution globale, mais il est souvent simple et rapide à mettre en œuvre.
À chaque appel récursif, on sélectionne le plus grand élément possible qui respecte encore la contrainte du problème, puis on réappelle la fonction sur ce qu'il reste à résoudre.
pieces_disponibles = [50, 20, 10, 5, 2, 1] #pièces disponibles, triées du plus grand au plus petit def rendu_monnaie(montant, pieces_disponibles): """ Objectif : Calcule, de façon récursive, la liste des pièces à rendre pour un montant donné, en choisissant à chaque étape la plus grande pièce possible. Entrée : montant : int : le montant restant à rendre pieces_disponibles : list : la liste des pièces disponibles, triées du plus grand au plus petit Sortie : rendu : list : la liste des pièces utilisées pour rendre le montant """ if montant == 0: #condition d'arrêt : il ne reste plus rien à rendre return [] for piece in pieces_disponibles: #on cherche la plus grande pièce satisfaisant la contrainte if piece <= montant: rendu = [piece] + rendu_monnaie(montant - piece, pieces_disponibles) return rendu print(rendu_monnaie(78, pieces_disponibles)) #affiche [50, 20, 5, 2, 1]
À chaque étape de la boucle, on parcourt les emplacements disponibles (par exemple des boîtes) et on place l'élément dans le premier emplacement qui peut encore le contenir.
objets = [4, 8, 1, 4, 2] #taille de chaque objet à ranger capacite_boite = 10 #capacité maximale de chaque boîte def rangement_boites(objets, capacite_boite): """ Objectif : Range une liste d'objets dans des boîtes, en plaçant chaque objet dans le premier emplacement disponible (première boîte ayant encore assez de place). Entrée : objets : list : la liste des tailles des objets à ranger capacite_boite : int : la capacité maximale de chaque boîte Sortie : boites : list : la liste des boîtes, chaque boîte étant elle-même une liste d'objets """ boites = [] for objet in objets: #on place chaque objet un par un place = False #indique si l'objet a été placé dans une boîte for boite in boites: #on cherche la première boîte ayant assez de place if sum(boite) + objet <= capacite_boite: boite.append(objet) place = True break if not place: #aucune boîte existante ne peut accueillir l'objet boites.append([objet]) return boites print(rangement_boites(objets, capacite_boite)) #affiche [[4, 4, 2], [8, 1]]