Python Knapsack problem - return the max sum value (with float ) of a tuple (weight,value)

Viewed 17
def fractional_knapsack(items, weight_lim):
    def ratio(items):
        return items[0] / items[1]
    items = sorted(items, key=ratio, reverse=True)
    return helper(items, weight_lim, sum=0)

def helper(items, weight_lim, sum):
    if weight_lim < 0:
        return 0
    if weight_lim == 0:
        return sum
    if len(items) == 0:
        return sum
    if weight_lim - items[0][0] >= 0:
        take = helper(items[1:], weight_lim - items[0][0], sum + items[0][1])
        dont_take = helper(items[1:], weight_lim, sum)
    else:
        ratio = (items[0][0] - weight_lim) / items[0][0]
        return sum + ratio * items[0][1]
    return max(take, dont_take)

First, an example:
[(3,4), (2,1), (4,5), (8,7)], weight_lim = 8
will return me 9.875, why?
it is:
1 * 4 (3,4) + 1 * 5 (4,5) + 1/8 * 8(8,7)
which is: 4 + 5 + (7/8)

Now, the question ( sorry for bad translation of mine ): I need to return the max value optionable from the tuples that it will reach the weight_lim, but it can be float, like I did a the example above.

I tried something, my output is 9. I need to reach 9.875 I need to reach somehow to the else part at the end, there it should end my function, but it is not working... I am getting to the max and there it ends. How to fix it so I can be able to get 9.875?

I dont need an answer, I need a tip ( Please dont say to me, use imports or built in functions or such... This is for me studying for test, I need to do algorithm + do all myself, which is why I am asking for a tip \ clue how to continue this )

EDIT: I tried also reversing the options, so the less than 0 will be first, but its still not working ( so it will reach the sum of 9 + 0.875 )

0 Answers
Related