"""
Programme qui trouve le contenu glouton
pour le sac à dos de l'ex. 2
de la série Algorithmes gloutons
selon deux critères gloutons:
1. utilité max
2. masse min
"""

# glouton utilité max
print("############################")
print("Critère glouton: utilité max")
print("############################")

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]

sac = []
masse_tot = 0
utilite_tot = 0
while masse_tot <= 17 and len(utilites)>0:
    glouton = utilites.index(max(utilites))
    masse_tot += masses[glouton]
    utilite_tot += utilites[glouton]
    sac.append([noms.pop(glouton), masses.pop(glouton), utilites.pop(glouton)])
    # print(utilite_tot, masse_tot, sac)
utilite_tot -= sac[-1][2]
masse_tot -= sac[-1][1]
sac.pop(-1)
print("Utilité totale:", utilite_tot)
print("Masse totale:", masse_tot)
print("Contenu du sac:", sac)

# glouton masse min
print("############################")
print("Critère glouton: masse min")
print("############################")

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]

sac = []
masse_tot = 0
utilite_tot = 0
while masse_tot <= 17 and len(masses)>0:
    glouton = masses.index(min(masses))
    masse_tot += masses[glouton]
    utilite_tot += utilites[glouton]
    sac.append([noms.pop(glouton), masses.pop(glouton), utilites.pop(glouton)])
    # print(utilite_tot, masse_tot, sac)
utilite_tot -= sac[-1][2]
masse_tot -= sac[-1][1]
sac.pop(-1)
print("Utilité totale:", utilite_tot)
print("Masse totale:", masse_tot)
print("Contenu du sac:", sac)

# glouton (utilité/masse) max
print("############################")
print("Critère glouton: (utilité/masse) max")
print("############################")

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]
utilites_masses = [utilites[i]/masses[i] for i in range(15)]

sac = []
masse_tot = 0
utilite_tot = 0
while masse_tot <= 17 and len(utilites_masses)>0:
    glouton = utilites_masses.index(max(utilites_masses))
    masse_tot += masses[glouton]
    utilite_tot += utilites[glouton]
    sac.append([noms.pop(glouton), masses.pop(glouton), utilites.pop(glouton), utilites_masses.pop(glouton)])
utilite_tot -= sac[-1][2]
masse_tot -= sac[-1][1]
sac.pop(-1)
print("Utilité totale:", utilite_tot)
print("Masse totale:", masse_tot)
print("Contenu du sac:", sac)