from random import randint
from itertools import combinations

def valeur(L):
    return L[1]

def poids(L):
    return L[2]

def algoAleatoire(L,n):
    vSacMax = 0
    for i in range(n):
        randL = [x for x in L if randint(0,1)==1]
        vSac = sum([valeur(x) for x in randL])
        pSac = sum([poids(x) for x in randL])
        if (pSac <= pMax and vSac > vSacMax):
            vSacMax = vSac
            optL = randL
    return optL

def algoForceBrute(L):
    n = len(L)
    vSacMax = 0
    for i in range(n):
        for c in combinations(L,i):
            combL = list(c)
            vSac = sum([valeur(x) for x in combL])
            pSac = sum([poids(x) for x in combL])
            if (pSac <= pMax and vSac > vSacMax):
                vSacMax = vSac
                optL = combL
    return optL

def algoGlouton(L):
    sortL = sorted(L, key=valeur, reverse=True)
    pSac = 0
    optL = []
    for x in sortL:
        if pSac + poids(x) <= pMax:
            optL.append(x)
            pSac = pSac + poids(x)
    return optL

pMax = 30
Objets = [("A",20,29),("B",12,10),("C",12,10),("D",12,10),("E",4,1)]

print(algoAleatoire(Objets,100))
print(algoForceBrute(Objets))
print(algoGlouton(Objets))