Knapsack problem with duplicate elements

Question

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)

• Kim: Is it an algorithmical review you wish for or is it rather about the coding style?
• Harsha: I would like to get an review on both: coding style as well as on alogrithm
• holroy: This seems like it is a programming-challenge, could you please verify that (and tag the question), and if so also link to the description of the programming challenge? This can help us clarify some details related to your question.

Answer 1

• table is a meaningless name for an important data structure. It should be explained by a comment at least.
• W and w look similar enough to cause confusion.
• Instead of using enumerate, you could iterate over zip(weight, cost) and avoid indexing.
• The max builtin function is convenient for computing a maximum. The inner for loop can be converted to a generator expression for max to process. However, max raises an error if there are no items to process. In recent versions of Python a default value can be given to max to avoid that.

My rewrite for Python 3.4 or later (I see you are using Python 2.x):

def knapsack(W, weights, costs):
 '''Given weights and costs of items, compute maximum cost for total
 allowed weight W when any item can be picked any number of times.
 '''
 best = [0] # best[x] is the max cost for allowed weight x
 for capacity in range(1, W + 1):
 best.append(max((cost + best[capacity - weight]
 for weight, cost in zip(weights, costs)
 if weight <= capacity),
 default=0))
 return best[W]