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?
W = 10
weight = [2,3,6,4]
cost = [3,4,6,10]
I have written this code. Is there any way to improve it?
def knapsack(W, weight, cost): #import pdb; pdb.set_trace() table =  * (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)