I solved the knapsack problem where duplicates elements are allowed:Given weights and values related to n items and the maximum capacity allowed for these items. What is the maximum value we can achieve if we can pick any weights any number of times for a total allowed weight of W?input:W = 10weight = [2,3,6,4]cost = [3,4,6,10]output:23I have written this code. Is there any way to improve it?def knapsack(W, weight, cost):    #import pdb; pdb.set_trace()    table = [0] * (W+1)    for w in xrange(W+1):        max_so_far = 0        for i, wt in enumerate(weight):            if wt <= w:                cur = cost[i] + table[w-weight[i]]                if cur > max_so_far:                    max_so_far = cur        table[w] = max_so_far    print table        return table[W]weight = [2,3,6,4]cost = [3,4,6,10]print knapsack(10,weight,cost)
Knapsack problem with duplicate elements
python;knapsack problem