def knapsack(v,w,n,W):
    V = [[None for x in range(W+1)] for x in range(len(v)+1)]
 
    for wy in range(W+1):
        V[0][wy] = 0
 
    for i in range(1,n+1):
        for wx in range(W+1):
            # print i,wx
            if w[i-1] <= wx:
 
                V[i][wx] = max(V[i-1][wx], v[i-1]+V[i-1][wx-w[i-1]])
            else:
                V[i][wx] = V[i-1][wx]
    return V[n][W]
 
print knapsack(v = [10,40,30,50],w=[5,4,6,3],n=4,W=10)

ZGVmIGtuYXBzYWNrKHYsdyxuLFcpOgogICAgViA9IFtbTm9uZSBmb3IgeCBpbiByYW5nZShXKzEpXSBmb3IgeCBpbiByYW5nZShsZW4odikrMSldCgogICAgZm9yIHd5IGluIHJhbmdlKFcrMSk6CiAgICAgICAgVlswXVt3eV0gPSAwCgogICAgZm9yIGkgaW4gcmFuZ2UoMSxuKzEpOgogICAgICAgIGZvciB3eCBpbiByYW5nZShXKzEpOgogICAgICAgICAgICAjIHByaW50IGksd3gKICAgICAgICAgICAgaWYgd1tpLTFdIDw9IHd4OgoKICAgICAgICAgICAgICAgIFZbaV1bd3hdID0gbWF4KFZbaS0xXVt3eF0sIHZbaS0xXStWW2ktMV1bd3gtd1tpLTFdXSkKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIFZbaV1bd3hdID0gVltpLTFdW3d4XQogICAgcmV0dXJuIFZbbl1bV10KCnByaW50IGtuYXBzYWNrKHYgPSBbMTAsNDAsMzAsNTBdLHc9WzUsNCw2LDNdLG49NCxXPTEwKQ==