Mochila

# Nao pode repetir os itens...

# item = {Item:[peso,valor]....}
item = {1:[4,500],2:[2,400],3:[1,300],4:[3,450]}

#quantidade de Itens
I = len(item)

#Capacidade
w = 5

#Criar matriz------------------
def criamatriz(n,m):
    mat =[0]*n
    for i in range(n):
        mat[i] = [0]*m
    return mat
resultado = criamatriz(I+1,w+1)
#-------------------------------
#Variar coluna primeiro e mais simples.
for j in range(0,w+1):#Coluna
    resultado[0][j] = 0 # Toda primeira coluna sera 0
    for i in range(1,I+1):#Linha

        a= resultado[i-1][j]#Linha anterior
        if item[i][0] > j:#Se peso > w
            b = 0
        else:#Se peso for menor que w

            b = resultado[i-1][j-item[i][0]]+item[i][1]


        if (a>b):
            resultado[i][j] = a
        else:
            resultado[i][j] = b

for k in range(0,len(resultado)):

    print(resultado[k])