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

Thanks

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