##exo3
w={1:5,2:4,3:3}
v={1:10,2:7,3:5}

def solsad(v,w,n,weight):
    V=[x[:] for x in [[0]*(weight+1)]*(n+1)]
    for i in range(1,n+1):
        for j in range(weight+1):
            if w[i]<=j: #on ajoute l'élement i
                V[i][j]=max(V[i-1][j],v[i]+V[i-1][j-w[i]])
            else : #l'élément n'est pas ajouté
                V[i][j]=V[i-1][j]
    return V[n][weight]
    
print(solsad(v,w,3,7))    

##
from sympy import *
init_printing() #pour faire un affichage joli des matrices (Matrix)

def sad(v,w,n,weight):
    V=[x[:] for x in [[0]*(weight+1)]*(n+1)]
    memo=[x[:] for x in [[0]*(weight+1)]*(n+1)]
    elements=[]
    for i in range(1,n+1):
        for j in range(weight+1):
            if w[i]<=j and v[i]+V[i-1][j-w[i]]>V[i-1][j]:
                V[i][j]=v[i]+V[i-1][j-w[i]]
                memo[i][j]=1
            else :
                V[i][j]=V[i-1][j]
                memo[i][j]=0 #un peu inutile ...
    k=weight
    for i in range(n,0,-1):
        if memo[i][k]==1:
            elements.append(i)
            k=k-w[i]
    return (V[n][weight],elements,Matrix(memo),Matrix(V))
    
print(sad(v,w,3,7))