Mochila | Python Fiddle

import math

class Mochila():
    
    def __init__(self,lista,capacidade):
        self.lista=lista
        self.capacidade=capacidade
        self.ops=0
        self.itens=[ False ]*len(lista)
        
    
    def solve(self):
        n=len(self.lista)
        W=self.capacidade
        V=[[0]*(W+1) for i in range(n+1)] #Inicia Matrix n x W com 0
        tabela_troca=[[False]*(W+1) for i in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,W+1):
                pesoI=self.lista[i-1]['peso']
                if pesoI>j: #Enquanto item i pesar mais que a coluna de capacidade mantem valor da ate item anterior
                    V[i][j]=V[i-1][j]
                    self.ops+=1
                else: #caso contrario pega o maior valor entre o valor removendo item com peso e adicionando item i e seu valor ou valor anterior 
                    V[i][j]=max(V[i-1][j-pesoI]+self.lista[i-1]['valor'],V[i-1][j])
                    if V[i-1][j-pesoI]+self.lista[i-1]['valor'] > V[i-1][j]:
                        tabela_troca[i][j]=True
                    self.ops+=1
        w=W
        for i in range(n,0,-1):
            if tabela_troca[i][w]:
                self.itens[i-1]=True
                w-=self.lista[i-1]['peso']
            else:
                self.itens[i-1]=False
        return V

if __name__ == "__main__":
    """
    |item | peso| valor ($)
    ------|------|-----------
    1 |2| 12
    2 |1| 10
    3 |3 |20
    4 |2 |15
    """
    itens = [{'item':1,'peso':2,'valor':12},
             {'item':2,'peso':1,'valor':10},
             {'item':3,'peso':3,'valor':20},
             {'item':4,'peso':2,'valor':15}
             ]
    itens2 = [{'item':1,'peso':4,'valor':500},
             {'item':2,'peso':2,'valor':400},
             {'item':3,'peso':1,'valor':300},
             {'item':4,'peso':3,'valor':450}
            ]
    mochila=Mochila(itens2,5)
    for linha in mochila.solve():
        print linha
    print mochila.ops
    n=len(mochila.lista)
    W=mochila.capacidade
    print "n(%d) * W(%d) = %d" % (n,W,n*W)
    print "Itens que coloquei na mochila"
    for i in range(len(mochila.itens)):
        if mochila.itens[i]:
            print "Item: %s Peso: %s Valor %s" % (mochila.lista[i]['item'],mochila.lista[i]['peso'],mochila.lista[i]['valor'])

Python Fiddle

Python Cloud IDE