"""
Programme qui trouve le contenu optimal
pour le sac à dos de l'ex. 2
de la série Algorithmes gloutons
"""
# Création de listes avec les données de l'exercice
noms = ["eau", "nourriture", "nécessaire", "couverture",
        "matelas", "tente", "gaz", "lampe", "console",
        "change", "jumelles", "cartes", "pull", "machette",
        "livre"]
masses = [3, 4.3, 2.2, 1, 1.5, 3.4, 0.8, 0.5, 2.1, 2.8, 1.3,
          0.5, 0.8, 2.4, 0.3]
utilites = [20, 15, 12, 6, 4, 18, 13, 10, 7, 11, 9, 8, 8, 5, 2]

# Création de la liste sacs qui contient
# toutes les possibilités de contenus du
# sac avec la masse et l'utilité totales
# exemples:
# el5 = 1 signifie que le 6ème élément est
# présent dans le sac
# el0 = 0 signifie que le premier élément
# n'est pas pris dans le sac
sacs = []
for el0 in [0, 1]:
 for el1 in [0, 1]:
  for el2 in [0, 1]:
   for el3 in [0, 1]:
    for el4 in [0, 1]:
     for el5 in [0, 1]:
      for el6 in [0, 1]:
       for el7 in [0, 1]:
        for el8 in [0, 1]:
         for el9 in [0, 1]:
          for el10 in [0, 1]:
           for el11 in [0, 1]:
            for el12 in [0, 1]:
             for el13 in [0, 1]:
              for el14 in [0, 1]:
                  contenu = ""
                  masse = 0
                  utilite = 0
                  for i in range(15):
                      contenu += str(globals()["el"+str(i)])
                      masse += masses[i] * globals()["el"+str(i)]
                      utilite += utilites[i] * globals()["el"+str(i)]
                  sacs.append([contenu, masse, utilite])
# Recherche du sac avec utilité maximale et masse<17
max = 0
for sac in sacs:
    if sac[1] <= 17 and sac[2] > max:
        max = sac[2]
        contenu = sac[0]
        masse = sac[1]
print("L'utilité max est ", max)
print("Voici les éléments pris pour obtenir ce maximum:")
print(contenu)
for i in range(len(contenu)):
    if contenu[i] == "1":
        print(noms[i])
print("Masse totale: ", masse)