6
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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