====== Algorithme Glouton ======

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.

===Algorithme glouton récursif : à chaque étape, on choisit le plus grand élément satisfaisant la contrainte===
À 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.

<code python>
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]
</code>

===Algorithme glouton itératif : à chaque étape, on place l'élément dans le premier emplacement disponible===
À 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.

<code python>
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]]
</code>