Knapsack greedy algorithm in Python

Question

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

Answer 1

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.

Answer 2

I believe Jean-Francois edited the code perfectly well and I learned to use zip from his example (didn't change it in my code though). But the whole structure of the code to solve this problem seems overly complicated. I don't understand why you need a while loop when the for loop is naturally going to terminate. There is also no need to check a lot of things such as "if w <= capacity". I'm not going to address everything but I have included my working code and am available to further clarify.

PS: Since this is for the coursera class, I'll add that my code passed the grader.

import sys
def get_optimal_value(capacity, weights, values):
    finalValue = 0
    a=0
    A=[0]*len(weights)
    # write your code here
    densities = sorted([[values[i] /float( weights[i]), weights[i]] for i in range(len(weights))], reverse=True)

    #while (capacity >0 and densities):
    for i, v in enumerate(densities):
        a= min(capacity, densities[i][1])
        #print(a)
        finalValue += a*densities[i][0]
        capacity -= a

    return finalValue