Solution: Fractional Knapsack Problem

This review provides a detailed analysis of the solution to the 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.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.