Problem statement

https://binarysearch.com/problems/Fractional-Knapsack/

Solution

The idea is to sort by value/weight and start with the biggest ones.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, weights, values, capacity):
        items = list(zip(weights, values))
        items.sort(key = lambda x: -x[1] / x[0])

        ans = 0
        for w, v in items:
            taken = min(capacity, w)
            capacity -= taken
            ans += taken * v / w
        return int(ans)