Knapsack greedy algorithm in Python 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 &gt; 0 and numItems &gt; 0:
        maxi = 0
        idx = None
        for i in range(numItems):
            if valuePerWeight[i][1] &gt; 0 and maxi &lt; valuePerWeight[i][0]:
                maxi = valuePerWeight[i][0]
                idx = i

        if idx is None:
            return 0.
        if valuePerWeight[idx][1] &lt;= capacity:
            value += valuePerWeight[idx][0]*valuePerWeight[idx][1]
            capacity -= valuePerWeight[idx][1]
        else:
            if valuePerWeight[idx][1] &gt; 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
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] &gt; 0 and maxi &lt; valuePerWeight[i][0]:
        maxi = valuePerWeight[i][0]
        idx = i


could be:

for i,item in enumerate(valuePerWeight):
    if item [1] &gt; 0 and maxi &lt; 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] &gt; 0:
    value += (capacity / valuePerWeight[idx][1]) * valuePerWeight[idx][1] * valuePerWeight[idx][0]
    return value


by (using v and w as instructed above)

if w &gt; 0:
    value += capacity * v
    return value


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

while capacity &gt; 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 &gt; 0 and valuePerWeight:
        maxi = 0
        idx = None
        for i,item in enumerate(valuePerWeight):
            if item [1] &gt; 0 and maxi &lt; item [0]:
                maxi = item [0]
                idx = i

        if idx is None:
            return 0.

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

        if w &lt;= capacity:
            value += v*w
            capacity -= w
        else:
            if w &gt; 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.