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)

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]