3
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ Is it an algorithmical review you wish for or is it rather about the coding style? \$\endgroup\$
    – Kim
    Apr 25, 2017 at 20:17
  • \$\begingroup\$ I would like to get an review on both: coding style as well as on alogrithm \$\endgroup\$
    – Harsha
    Apr 27, 2017 at 17:03
  • \$\begingroup\$ 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. \$\endgroup\$
    – holroy
    Apr 28, 2017 at 9:03

1 Answer 1

1
\$\begingroup\$
  • 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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.