Fractional Knapsack Problem

Difficulty: Medium

Asked in: Amazon

Understanding the Problem: →

We are given N items with their corresponding weights and values, we have a knapsack weighing W. We have to choose among these N items to put into the knapsack such that the value of the knapsack is maximum. For example:

Input: items[] = [ [60, 10], [100, 20], [120, 30] ]
Knapsack Capacity(capacity) = 50
Output: Maximum possible value = 240
Explanation: By taking full items of 10 kg, 20 kg and 2/3rd of last item of 30 kg. Total value = 60 + 100 + 120*2/3 = 240

Possible follow-up questions to ask the interviewer: →

Do we have to take items as whole or we can take them as fraction?( Ans: You can take fractions of the items too.)

Solution

Solution idea

Here the problem is to find the maximum profit possible from the items[] and we are also allowed to take fractions of the items. This is an optimization problem which can be solved by applying greedy algorithm startegy. In this algorithm, we go on choosing the locally optimal choice (or the greedy choice) with a consideration that it will lead to globally optimal solution.

Lets think about the solution insights. Which item will you pick first (Greedy choice) ? One startegy is to maximize the profit with every choice and pick the item with the largest ratio of value/weight. This will assure us that we will reach to the globally optimal profit. (Think!)

Solution steps

Find the value/weight ratio for each given item.
Sort the items based on the ratio of value/weight.
Then start picking up the item with the highest ratio until that item is completely taken up. After that we will move to the next highest.

Pseudo-code

double fractionalKnapsack(int K, item A[], int N)
{
   //Sort the items on the basis of increasing ratio of V/W 
    sort(A, A+N)
    double totalValue = 0.0
    int currUsedWeight = 0
    for(int i = 0 to N-1)
    {
       if(A[i].weight < K)
       {
           totalValue = totalValue + A[i].value
           currUsedWeight = currUsedWeight + A[i].weight
       }
       else
       {
           int availableSpace = K - currUsedSpace
           //Taking the Fraction
           totalValue = totalValue + A[i].value*(availableSpace/A[i].weight)
           break
       }
    }
}

Complexity Analysis

Time Complexity: Time complexity of the sorting + Time complexity of the loop to maximize profit = O(NlogN) + O(N) = O(NlogN)

Space Complexity: O(1)

Critical ideas to think!

Do you think locally optimal solution is always the globally optimal? In many problems, a greedy strategy does not produce an optimal solution.
Proving that a greedy algorithm is correct is more of an art than a science. Usually, coming up with an algorithm might seem to be trivial, but proving that it is actually correct, is a whole different problem.
Can we solve this problem using Dynamic Programming? Compare greedy algorithms and Dynamic Programming approach.