Fractional Knapsack

Problem

Given item weights, values and a capacity, return the maximum total value when fractions of items may be taken.

Sort items by value over weight and take as much as possible from the best ratio first, splitting the last item when the capacity runs out. Return 0.0 when there are no items or no capacity.

Hint

The greedy choice by value density is optimal when items can be split.

Test cases

case 1

in: [[10,20,30],[60,100,120],50]

expected: 240

case 2

in: [[5,10],[10,20],5]

expected: 10

case 3

in: [[],[],0]

expected: 0

case 4

in: [[1,2,3],[3,4,5],3]

expected: 7

case 5

in: [[10],[100],5]

expected: 50

Starter codePython

def fractional_knapsack(weights, values, capacity):
    # Your code here
    pass

5 test cases · run your code against them in the editor