Solution: Fractional Knapsack Problem

Solution#1: Brute force (naive)

The brute force solution says to try all the possible subsets with all the different fractions. However, that takes too much time. The brute force approach is very naive, and it is in no way suitable for an interview. We need a more optimized solution.

Time complexity

A brute force approach would try picking items in all possible proportions. Since the items can be picked in fractions, there is an infinite number of possible fractions of each time. This clearly is not tractable.

Note: The naive solution is not provided here because it is not appreciated for an interview, but you might work on it on your own just for an activity.