# 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 > 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


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.

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)