#Corrigé provisoire (avec sans doute une erreur en question 10...)

##
#Question 1
#L'utilité maximale que l'on peut transporter pour un poids maximal de 24 kg vaut 51.
#Il faut pour l'obtenir transporter les objets 0,2,5 et 6

##
#Question 2
#Il s'agit d'une stratégie gloutonne.
#Dans ce qui suit, on représente la liste d'objets sous forme d'une liste de listes, chaque objet étant représenté par une liste [poids, utilité]
Objets=[[3,7],[4,8],[5,12],[5,10],[7,13],[8,15],[8,17]]
#En question 3, on trie les objets par ordre d'utilité décroissante (tri 1). En question 4, on utilisera le tri 2
def Tri1(S):
    T=S+[]
    for i in range(len(T)):
        for j in range(len(T)-1):
            if T[j][1]<T[j+1][1]:
                T[j],T[j+1]=T[j+1],T[j]
    return T

def Tri2(S):
    T=S+[]
    for i in range(len(T)):
        for j in range(len(T)-1):
            if T[j][1]/T[j][0]<T[j+1][1]/T[j+1][0]:
                T[j],T[j+1]=T[j+1],T[j]
    return T

#Questions 3 et 4 :
def glouton(S,L,Tri):
    T=Tri(S)
    c=L
    i=0
    D=[]
    for i in range(len(T)):
        if T[i][0]<c:
            D.append(T[i])
            c-=T[i][0]
    return D
#Pour Q3 : glouton(Objets,24,Tri1) renvoie la liste [[8, 17], [8, 15], [7, 13]] (utilité totale de 47).
#Pour Q4 : glouton(Objets,24,Tri2) renvoie la liste [[5, 12], [3, 7], [8, 17], [4, 8]] (utilité totale de 44).
#Dans les deux cas, on voit que la stratégie n'est pas optimale.

##
#Question 5
#Il y a 2**n combinaisons possibles. Il faut calculer le poids de chacune d'entre elles, ainsi que leur utilité (complexité libnéaire), puis trier celles dont le poids est inférieur à L par utilité décroissante (complexité en O(N.ln(N), où N est le nombre de listes à trier). On obtient une complexité totale en O(n.2**n*ln(n))

##
#Question 6
#M(L,n) est la réponse recherchée.

##
#Question 7
#On note :
#catégorie 1 : les combinaisons qui ne contiennent pas l'objet i
#catégorie 2 : les combinaisons qui contiennent l'objet i
#L'utilité maximale que l'on peut obtenir sans prendre l'objet i est M(t,i-1)
#L'utilité maximale que l'on peut obtenir en prenant l'objet i est : M(t-p(i),i-1)+u(i)
#En tenant compte du fait que l'on ne peut envisager de prendre l'objet i que si son poids est inéfrieur ou égal à t, on a :
#M(t,i)= M(t,i-1) si p(i)>t
#M(t,i)=max{M(t,i-1),M(t-p(i),i-1)+u(i)} si p(i)<=t

##
#Question 8
#M(t,0) est évidemment égal à 0 (si pas d'objet, pas d'utilité...)

##
#Question  9
def tableau(u,p,L):
    n=len(p)
    M= [[0 for i in range(0,n+1)] for j in range(0,L+1) ]
    for c in range(1,L+1): # la ligne pour c==0 contient déjà des 0, inutile de la remplir.
        for i in range(0,n):
            if p[i] <= c:
                M[c][i+1]=max(M[c][i],M[c-p[i]][i]+u[i])
            else:
                M[c][i+1]=M[c][i]
    return M

L=1000
p=[30, 45, 49, 33, 21, 20, 30, 33, 13, 27, 22, 47, 10, 47, 20, 23, 12, 30, 11, 49, 13, 24, 26, 16, 44, 21, 29, 39, 12, 41, 15, 37, 40, 11, 15, 17, 50, 34, 28, 13, 21, 30, 42, 20, 46, 32, 18, 20, 22, 35]
u=[44, 35, 25, 55, 39, 10, 53, 30, 24, 40, 23, 83, 15, 34, 26, 34, 21, 56, 13, 72, 17, 45, 21, 23, 53, 36, 41, 67, 11, 67, 27, 60, 80, 10, 26, 28, 56, 22, 24, 8, 25, 46, 22, 36, 74, 44, 27, 14, 34, 47]

M=tableau(u,p,L)
n=len(p)
print(M[L][n])

##
#Question  10
def reconstruction(M,i,L,p):
    if i==0:
        return []
    elif M[L][i]==M[L][i-1]:
        return reconstruction(M,i-1,L,p)
    else:
        return reconstruction(M,i-1,L-p[i-1],p)+[i-1]

def listes_optimales(M,p):
    L=len(M)-1
    n=len(M[0])-1
    V=M[L][n]
    print(V)
    res=[]
    for j in range(L+1):
        for i in range(n+1):
            if M[j][i]==V and M[j][i]!=M[j][i-1]:
                if reconstruction(M,i,j,p) not in res:
                   res.append(reconstruction(M,i,j,p))
    return res
A=listes_optimales(M,p)
for a in A:
    print(a)
#j'obtiens une solution de moins que M. Pichetti, il y a donc sans doute une erreur quelque part...
##
#Question  11
u=[7,8,12,10,13,15,17]
p=[3,4,5,5,7,8,8]
M=tableau(u,p,26)
print(listes_optimales(M,p))

#Test
u=[7.05,7.05,7.1]
p=[8,8,8]
M=tableau(u,p,17)
print(listes_optimales(M,p))

def tableau2(u,p,L):
    n=len(p)
    M= [[0 for i in range(0,n+1)] for j in range(0,L+1) ]
    R= [[0 for i in range(0,n+1)] for j in range(0,L+1) ]
    for c in range(1,L+1): # la ligne pour c==0 contient déjà des 0, inutile de la remplir.
        for i in range(0,n):
            if p[i] <= c:
                M[c][i+1]=max(M[c][i],M[c-p[i]][i]+u[i])
                if M[c][i]==M[c-p[i]][i]+u[i]:
                    R[c][i+1]=1
            else:
                M[c][i+1]=M[c][i]
    return M,R

def reconstruction2(M,R,i,L,p):
    if i==0:
        return []
    elif M[L][i]==M[L][i-1] and R[L][i]!=1:
        return reconstruction2(M,R,i-1,L,p)
    else:
        return reconstruction2(M,R,i-1,L-p[i-1],p)+[i-1]

def listes_optimales2(M,R,p):
    L=len(M)-1
    n=len(M[0])-1
    V=M[L][n]
    print(V)
    res=[]
    for j in range(L+1):
        for i in range(n+1):
            if M[j][i]==V:
                print(j,i,reconstruction2(M,R,i,j,p))
                if reconstruction2(M,R,i,j,p) not in res:
                   res.append(reconstruction2(M,R,i,j,p))
    return res

L=1000
p=[30, 45, 49, 33, 21, 20, 30, 33, 13, 27, 22, 47, 10, 47, 20, 23, 12, 30, 11, 49, 13, 24, 26, 16, 44, 21, 29, 39, 12, 41, 15, 37, 40, 11, 15, 17, 50, 34, 28, 13, 21, 30, 42, 20, 46, 32, 18, 20, 22, 35]
u=[44, 35, 25, 55, 39, 10, 53, 30, 24, 40, 23, 83, 15, 34, 26, 34, 21, 56, 13, 72, 17, 45, 21, 23, 53, 36, 41, 67, 11, 67, 27, 60, 80, 10, 26, 28, 56, 22, 24, 8, 25, 46, 22, 36, 74, 44, 27, 14, 34, 47]

M,R=tableau2(u,p,L)
n=len(p)
print(M[L][n])

A=listes_optimales2(M,R,p)
for a in A:
    print(a)

#Test
u=[1,1,1]
p=[1,1,1]
M,R=tableau2(u,p,2)
print(listes_optimales2(M,R,p))