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