Fractional Knapsack Problem (Greedy Approach)

Posted by on Mar 31, 2024

Given the weights and values of n items, the task is to put these items in a knapsack of capacity w to get the maximum total value in the knapsack.

Note: Unlike the 0/1 knapsack, you are allowed to break the item.

Input: items[] = {{value: 60, weight: 10}, {value:100, weight: 20}, {value:120, weight: 30}}, w = 50
Output: 240.0

Input: items[] = {{value: 500, weight: 30}}, w = 10
Output: 66.667


Solutions

Method 1: Greedy

In the greedy approach, we calculate the ratio of value to weight and sort the items in descending order of this ratio.

Next, start adding the items to the knapsack.

Add the whole item if the current weight is less than the capacity; else, add a portion of the item to the knapsack.

Stop when all the items have been considered or the capacity of the knapsack is exhausted.

Complexity

The time complexity of this solution is O(nlogn) and space complexity is O(n).

Related


Activity Selection Problem (Greedy algorithm)

Job Sequencing Problem (Greedy algorithm)