objets0 = [(1,5),(1,2),(4,6),(2,3)]


objets1 = [(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3),(1,5),(1,2),(4,6),(2,3)]








def maxi(objets) :
    rep = objets[0]
    for j in range (len(objets)) :
        if rep[1] < objets[j][1] :
            rep  = objets[j]
    return rep

def indice(objets,o) :
    for j in range (len(objets)) :
        if objets[j] == o :
            return j

def poids_eg(objets,M) :
    objetscop = objets.copy() # objets[:]
    rep = []
    for nombre_obj in range(M) :
        ochoisi = maxi(objetscop)
        if ochoisi[1] == -1 :
            # Tous les objets sont dans le sac
            return rep
        rep.append(indice(objetscop,ochoisi))
        objetscop[indice(objetscop,ochoisi)] = (-1,-1)
        # objetscop[indice(objetscop,ochoisi)][1] = -1
        # Pas possible
    return rep






"""
def poids_eg(objets,M) :
    dispo = [i for i in range (len(objets))]
    rep =[]
    for j in range (M) :
        # Le sac contient tous les objets
        if len(dispo) == 0 :
            return rep

        # Il faut chercher un objet de plus
        maxi = objets[dispo[0]][1]
        ind_maxi = 0
        for j in range (len(dispo)) :
            if maxi < objets[dispo[j]][1] :
                maxi = objets[dispo[j]][1]
                ind_maxi = j
        # On ajoute l'objet trouvé et on le supprime
        # des objets dispo
        rep.append(dispo[ind_maxi])
        dispo.pop(ind_maxi)
    return rep
"""

def D(n,p,objets) :
    if n == -1 :
        if p == 0 :
            return 0
        else :
            return -1
    else :
        poids,valeur = objets[n]
        if p - poids >= 0 :
            if D(n-1,p-poids,objets) != -1 :
                return max(D(n-1,p-poids,objets)+valeur,D(n-1,p,objets))
    return D(n-1,p,objets)

def sac_a_dos(M,objets) :
    maxi = 0
    for i in range (M+1) :
        calcul = D(len(objets)-1,i,objets)
        if calcul > maxi :
            maxi = calcul
    return maxi







dic = {}
def D_mem(n,p,objets) :
    t_objets = tuple(objets)

    if (n,p,t_objets) in dic :
        return dic[(n,p,t_objets)]

    if n == -1 :
        if p == 0 :
            dic[(n,p,t_objets)] = 0
            return 0
        else :
            dic[(n,p,t_objets)] = -1
            return -1
    else :
        poids,valeur = objets[n]
        if p - poids >= 0 :
            if D_mem(n-1,p-poids,objets) != -1 :
                dic[(n,p,t_objets)] = max(D_mem(n-1,p-poids,objets)+valeur,D_mem(n-1,p,objets))
                return dic[(n,p,t_objets)]

        dic[(n,p,t_objets)] = D_mem(n-1,p,objets)
        return dic[(n,p,t_objets)]




def sac_a_dos_mem(M,objets) :
    maxi = 0
    for i in range (M+1) :
        calcul = D_mem(len(objets)-1,i,objets)
        if calcul > maxi :
            maxi = calcul
    return maxi




def valeur_max_sac_a_dos(poids_sac, li_objets) :
    M = poids_sac
    n = len(li_objets)
    D = [[-1 for j in range(n + 1)] for i in range(M + 1)]
    D[0][0] = 0
    for n_objet in range(1,n + 1) :
        for poids in range(0,M + 1) :

            poids_obj, valeur_obj = li_objets[n_objet - 1]

            # Si D[poids][n_objet - 1] n'est pas défini, v1 vaut -1
            v1 = D[poids][n_objet - 1]
            v2 = -1
            # Si poids de l'objet est plus grand que poids, v2 reste à -1
            if li_objets[n_objet - 1][0] <= poids :
                # Si D[poids - poidsObjet]][objet - 1] n'est pas défini,
                # v2 reste à - 1
                if D[poids - poids_obj][n_objet - 1] >= 0 :
                    v2 = D[poids - poids_obj][n_objet - 1] + valeur_obj

            D[poids][n_objet] = max(v1,v2)

    maxi = 0
    for poids in range(poids_sac + 1) :
        if D[poids][n] >= maxi :
            maxi = D[poids][n]

    return maxi



def valeur_max_sac_a_dos_tableau(poids_sac, li_objets) :
    M = poids_sac
    n = len(li_objets)
    D = [[-1 for j in range(n + 1)] for i in range(M + 1)]
    D[0][0] = 0
    for n_objet in range(1,n + 1) :
        for poids in range(0,M + 1) :

            poids_obj, valeur_obj = li_objets[n_objet - 1]

            # Si D[poids][n_objet - 1] n'est pas défini, v1 vaut -1
            v1 = D[poids][n_objet - 1]
            v2 = -1
            # Si poids de l'objet est plus grand que le poids considéré, v2 reste à -1
            if li_objets[n_objet - 1][0] <= poids :
                # Si D[poids - poidsObjet]][objet - 1] n'est pas défini, v2 reste à - 1
                if D[poids - poids_obj][n_objet - 1] >= 0 :
                    v2 = D[poids - poids_obj][n_objet - 1] + valeur_obj

            D[poids][n_objet] = max(v1,v2)

    return D

def objet_sac_a_dos(poids_sac, li_objets):
    D = valeur_max_sac_a_dos_tableau(poids_sac,li_objets)
    n = len(li_objets)

    # On recherche le poids pour lequel on a la valeur maximale
    maxi = 0
    poids_maxi = -1
    for poids in range(poids_sac + 1) :
        if D[poids][n] >= maxi :
            maxi = D[poids][n]
            poids_maxi = poids

    # On a trouvé le poids, on procède à la reconstruction
    liste_maxi = []
    dernier_objet = n

    while poids_maxi != 0 :
        if D[poids_maxi][dernier_objet - 1] == D[poids_maxi][dernier_objet] :
            # Pas besoin de rendre le dernier objet pour avoir la valeur maximale
            dernier_objet = dernier_objet - 1
        else :
            # Besoin de rendre le dernier objet pour avoir la valeur maximale
            liste_maxi.append(li_objets[dernier_objet - 1])
            poids_maxi = poids_maxi - li_objets[dernier_objet-1][0]
            dernier_objet = dernier_objet - 1
    return liste_maxi









## Multi sac



def valeur_max_multi_sac_a_dos_tableau(L_sac, li_objets) :


    M0 = L_sac[0]
    M1 = L_sac[1]
    n = len(li_objets)
    D = [[[-1 for j in range(n + 1)] for i in range(M1 + 1)] for k in range (M0+1)]
    D[0][0][0] = 0
    for n_objet in range(1,n + 1) :
        for poids0 in range(0,M0 + 1) :
            for poids1 in range(0,M1 + 1) :

                poids_obj, valeur_obj = li_objets[n_objet - 1]

                v1 = D[poids0][poids1][n_objet - 1]
                v2 = -1
                v3 = -1

                if li_objets[n_objet - 1][0] <= poids0 :
                    if D[poids0 - poids_obj][poids1][n_objet - 1] >= 0 :
                        v2 = D[poids0 - poids_obj][poids1][n_objet - 1] + valeur_obj

                if li_objets[n_objet - 1][0] <= poids1 :
                    if D[poids0][poids1 - poids_obj][n_objet - 1] >= 0 :
                        v3 = D[poids0][poids1 - poids_obj][n_objet - 1] + valeur_obj

                D[poids0][poids1][n_objet] = max(v1,v2,v3)

    return D




def objet_mult_sac_a_dos(L_sac, li_objets):
    D = valeur_max_multi_sac_a_dos_tableau(L_sac,li_objets)
    n = len(li_objets)

    # On recherche le poids pour lequel on a la valeur maximale
    maxi = 0
    poids_maxi = -1
    for poids0 in range(L_sac[0] + 1) :
        for poids1 in range(L_sac[1] + 1) :
            if D[poids0][poids1][n] >= maxi :
                maxi = D[poids0][poids1][n]
                poids_maxi = (poids0,poids1)

    # On a trouvé le poids, on procède à la reconstruction
    liste_maxi = []
    dernier_objet = n

    while poids_maxi != (0,0) :
        p0,p1 = poids_maxi
        p_obj,val = li_objets[dernier_objet - 1]
        if D[p0][p1][dernier_objet - 1] == D[p0][p1][dernier_objet] :
            # Pas besoin de rendre le dernier objet pour avoir la valeur maximale
            dernier_objet = dernier_objet - 1
        elif p1 - p_obj >= 0 and D[p0][p1-p_obj][dernier_objet - 1] + val == D[p0][p1][dernier_objet] :
            # Besoin de rendre le dernier objet pour avoir la valeur maximale
            liste_maxi.append((li_objets[dernier_objet - 1],1))
            p1 = p1 - p_obj
            dernier_objet = dernier_objet - 1
        else :
            liste_maxi.append((li_objets[dernier_objet - 1],0))
            p0 = p0 - p_obj
            dernier_objet = dernier_objet - 1
        poids_maxi = (p0,p1)
    return liste_maxi