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.

Real life example

Before moving on to the solution, we want you to understand the concept using an example.

Consider the following example, where the knapsack has a maximum capacity of 10. You have to smartly pick the items that can maximize the value (in dollars) in the knapsack.

Sample input

Here a double 2D Array is given, having {weight, value} of each given item:

double [][]input = {{2, 50},