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 = 10
weight = [2,3,6,4]
cost = [3,4,6,10]
output:
23
I 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)