Fractional Knapsack Problem

In this article, we will solve the Fractional Knapsack Problem using the Greedy approach.

Problem Statement: The weights and values of N items are given. We have to put these items in a knapsack of weight W such that the total value obtained is maximized.

Example:

Input: weights[] = {10, 20, 30}, values[] = {60, 100, 120}, W = 50

Output: 240.0

Input: weights[] = {5, 10, 15}, values[] = {10, 40, 30}, W = 20

Output: 66.67

Solution:

To solve this problem, we will follow these steps:

Steps to Solve:

1.    Calculate Value per Weight:

o   For each item, calculate the value per unit weight.

2.    Sort Items:

o   Sort the items based on the value per unit weight in descending order.

3.    Select Items:

o   Initialize the total value to zero.

o   Traverse the sorted items and add as much of each item as possible to the knapsack.

o   If adding the entire item exceeds the weight limit, add a fraction of it.

Time Complexity: O(N log N)

Space Complexity: O(1)