## 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.

#### Suggested Problems to Solve

- Sequencing the Jobs Problem
- 0–1 Knapsack Problem
- 0–1 Knapsack problem using Branch and Bound
- Unbounded Fractional Knapsack
- Activity Selection Problem
- Gas station Problem
- Distribute Candy Problem

**Happy Coding! Enjoy Algorithms!!**