# Liste des objets codés comme des dictionnaires
objets = [{'couleur':"Vert",'valeur':4,'masse':12}, {'couleur':"Bleu",'valeur':2,'masse':2},
          {'couleur':"Gris",'valeur':2,'masse':1}, {'couleur':"Orange",'valeur':1,'masse':1},
          {'couleur':"Jaune",'valeur':10,'masse':4}]
CAPACITE_SAC = 15

def sac_a_dos(capacite:int, objets:list[dict]) -> list:
    """
    Renvoi la liste des objets contenus dans un sac à dos dont la capacité
    (en masse) est donnée en argument en essayant de maximiser la valeur par une
    méthode gloutonne. La liste d'objets est constituée de dictionnaires
    représentant chaque objets :
       {'couleur': str représentant la couleur,
        'valeur': nombre représentant la valeur de l'objet
        'masse' : nombre représentant la masse de l'objet}
    La liste renvoyée est de même constituée des objets tirés de la liste
    'objets' et peut contenir plusieurs fois le même objet.
    """
    # Initialisation des variables
    contenu = []    # Liste contenant les objets qui sont mis dans le sac au fur et à mesure
    plein = False   # Variable logique signalant quand le sac ne peut plus accueillir d'objets
    restant = CAPACITE_SAC  # Variable entière représentant la capacité encore disponible dans le sac

    # Boucle de remplissage du sac par une méthode gloutonne
    while .............:   # Tant que le sac n'est pas plein on cherche à le remplir
        # Recherche de l'objet le plus précieux qui rentre dans le sac
        meilleur_objet = None  # Variable contenant le meilleur objet initialisée à " None "
        for ...................:   # On parcourt la liste des objets disponibles
            if ....................:    # Si l'objet peut encore rentrer dans le sac
                if .................:   # et s'il n'y a pas encore de meilleur objet
                    .................   # alors il devient meilleur objet quelque soit sa valeur
                elif ...........................................: # Si le nouvel objet est plus précieux
                    .....................   # alors il devient le meilleur choix
                elif ...........................................: # Si les objets ont la même valeur
                    if ........................................:  # et que le nouveau est plus léger
                        ......................                    # alors il devient le meilleur choix
        # Maintenant on met à jour le sac
        if ......................: # Si on a trouvé aucun objet qui rentre dans le sac (" None ")
            ............           # alors il est plein et on le signale pour sortir de la boucle
        else:
            ..............................                # Si on a trouvé un objet, on l'ajoute au sac
            ...........................................   # Et on soustrait à la capacité restante
    return contenu


# Affichage du contenu du sac (supposé être une liste d'objets appelée " contenu ")
contenu = sac_a_dos(CAPACITE_SAC, OBJETS)
print("Masse\t| Contenu du sac :")
masse = 0
valeur = 0
for objet in contenu:
    masse += objet['masse']
    valeur += objet['valeur']
    print(str(masse) + "\t| " + objet['couleur'])
print("Valeur totale dans le sac à dos :", valeur)