Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I implemented the well-known knapsack problem and now I would like to improve it using list comprehension or lambda. I don't want to use NumPy. Could you help me?

def get_optimal_value(capacity, weights, values):
    value = 0.
    numItems = len(values)
    valuePerWeight = sorted([[values[i] / weights[i], weights[i]] for i in range(numItems)], reverse=True)
    while capacity > 0 and numItems > 0:
        maxi = 0
        idx = None
        for i in range(numItems):
            if valuePerWeight[i][1] > 0 and maxi < valuePerWeight[i][0]:
                maxi = valuePerWeight[i][0]
                idx = i

        if idx is None:
            return 0.
        if valuePerWeight[idx][1] <= capacity:
            value += valuePerWeight[idx][0]*valuePerWeight[idx][1]
            capacity -= valuePerWeight[idx][1]
        else:
            if valuePerWeight[idx][1] > 0:
                value += (capacity / valuePerWeight[idx][1]) * valuePerWeight[idx][1] * valuePerWeight[idx][0]
                return value
        valuePerWeight.pop(idx)
        numItems -= 1
    return value

For completeness here is the client code to test the implementation with a simple example:

if __name__ == "__main__":
    n = 3
    capacity = 50
    values = [60, 100, 120]
    weights = [20, 50, 30]
    opt_value = get_optimal_value(capacity, weights, values)
    print("{:.10f}".format(opt_value)) # print 180.0000000000
share|improve this question
up vote 2 down vote accepted

list comprehensions aren't too useful in that code. Well, I think I can help improve your code anyway:

valuePerWeight = sorted([[values[i] / weights[i], weights[i]] for i in range(numItems)], reverse=True)

is overcomplicated instead of the index and range. Use zip instead, which is faster and cleaner:

valuePerWeight = sorted([[v / w, w] for v,w in zip(values,weights)], reverse=True)

Same there: not very pythonic to work with indexes when you can use enumerate:

for i in range(numItems):
    if valuePerWeight[i][1] > 0 and maxi < valuePerWeight[i][0]:
        maxi = valuePerWeight[i][0]
        idx = i

could be:

for i,item in enumerate(valuePerWeight):
    if item [1] > 0 and maxi < item [0]:
        maxi = item [0]
        idx = i

clearer and faster right? and after having found idx you could save a lot of access-by-index time by creating:

v = valuePerWeight[idx][0]
w = valuePerWeight[idx][1]

and refer to v and w in the rest of the code: clearer and faster (double access by index is costly cpu-wise)

Last item: you're dividing and multiplying by the same value. Since they're float operations, you could simplfy:

if valuePerWeight[idx][1] > 0:
    value += (capacity / valuePerWeight[idx][1]) * valuePerWeight[idx][1] * valuePerWeight[idx][0]
    return value

by (using v and w as instructed above)

if w > 0:
    value += capacity * v
    return value

Also, you don't need numItems at all now. Just turn the while loop as:

while capacity > 0 and valuePerWeight:

(when valuePerWeight is empty, the loop ends)

So to sum it all up, here's my proposal for an improved code of yours:

def get_optimal_value(capacity, weights, values):
    value = 0.

    valuePerWeight = valuePerWeight = sorted([[v / w, w] for v,w in zip(values,weights)], reverse=True)
    while capacity > 0 and valuePerWeight:
        maxi = 0
        idx = None
        for i,item in enumerate(valuePerWeight):
            if item [1] > 0 and maxi < item [0]:
                maxi = item [0]
                idx = i

        if idx is None:
            return 0.

        v = valuePerWeight[idx][0]
        w = valuePerWeight[idx][1]

        if w <= capacity:
            value += v*w
            capacity -= w
        else:
            if w > 0:
                value += capacity * v
                return value
        valuePerWeight.pop(idx)

    return value

if __name__ == "__main__":
    n = 3
    capacity = 50
    values = [60, 100, 120]
    weights = [20, 50, 30]
    opt_value = get_optimal_value(capacity, weights, values)
    print("{:.10f}".format(opt_value)) # print 180.0000000000

tested and stil returns 180.0, fortunately.

share|improve this answer
    
Thanks! Exactly the a answer I was hoping for! – Michael Dec 27 '16 at 4:58
    
cool. please accept the answer if it works for you – Jean-François Fabre Dec 27 '16 at 9:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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