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 )