Fractional Knapsack

Problem Link

Problem: Fractional Knapsack

Problem Statement

Given weights and values of N items, and a knapsack capacity W, determine the maximum total value that can be accommodated in the knapsack. You are allowed to take fractions of items.

Examples

Example 1
Input:

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

Output: 240.00
Explanation:

Take the whole item of weight 10 (value 60).
Take the whole item of weight 20 (value 100).
Remaining capacity = 20, take 20/30 fraction of the third item for value = (20/30)*120 = 80.
Total = 60 + 100 + 80 = 240.

Example 2
Input:

N = 2  
W = 10  
values[] = {100, 50}  
weights[] = {30, 10}

Output: 50.00
Explanation:

Only the second item can fit entirely for value 50. The first item cannot fit and taking a fraction yields (10/30)*100 = 33.33, which is less than taking the second item entirely. Optimal is 50.

Constraints

1 ≤ N ≤ 10^5
1 ≤ W, weights[i], values[i] ≤ 10^9

Intuition

To maximize total value when fractions are allowed, we should prioritize items with the highest value-to-weight ratio (value per unit weight). This is a classic greedy approach: always take as much as possible of the item with the highest ratio remaining.

Approach

Create a list of items where each item has (value, weight, ratio = value/weight).
Sort the list in descending order of ratio.
Initialize remainingCapacity = W and totalValue = 0.0.
Iterate over the sorted list:
- If the current item’s weight ≤ remainingCapacity, take it whole:
  - totalValue += value
  - remainingCapacity -= weight
- Else, take a fraction f = remainingCapacity / weight:
  - totalValue += value * f
  - remainingCapacity = 0
  - Break out of the loop.
Return totalValue formatted to two decimal places.

Code (Java)

import java.util.*;

class Item {
    int value;
    int weight;
    double ratio;

    Item(int value, int weight) {
        this.value = value;
        this.weight = weight;
        this.ratio = (double) value / weight;
    }
}

class Solution {
    public static double fractionalKnapsack(int W, Item[] items) {
        // Sort by value-to-weight ratio in descending order
        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));

        double totalValue = 0.0;
        int remainingCapacity = W;

        for (Item item : items) {
            if (remainingCapacity == 0) {
                break;
            }
            if (item.weight <= remainingCapacity) {
                totalValue += item.value;
                remainingCapacity -= item.weight;
            } else {
                double fraction = (double) remainingCapacity / item.weight;
                totalValue += item.value * fraction;
                remainingCapacity = 0;
            }
        }

        return totalValue;
    }

    // Example driver
    public static void main(String[] args) {
        Item[] items = {
            new Item(60, 10),
            new Item(100, 20),
            new Item(120, 30)
        };
        int W = 50;
        System.out.printf("%.2f", fractionalKnapsack(W, items));
    }
}

Time and Space Complexity

Time Complexity:
- Sorting takes O(N log N).
- A single pass over items takes O(N).
- Overall: O(N log N).
Space Complexity:
- O(N) for the array of Item objects.

Dry Run

Input:

W = 50  
items = [{value=60, weight=10}, {value=100, weight=20}, {value=120, weight=30}]

Compute ratios:
- Item1: 60/10 = 6.0
- Item2: 100/20 = 5.0
- Item3: 120/30 = 4.0
Sort by ratio: [Item1, Item2, Item3]
remainingCapacity = 50, totalValue = 0
Take Item1 (weight 10): totalValue = 60, remaining = 40
Take Item2 (weight 20): totalValue = 160, remaining = 20
Item3 weight (30) > remaining (20): take fraction = 20/30
- totalValue += 120 * (20/30) = 80
- totalValue = 240, remaining = 0
Return 240.00

Conclusion

The Fractional Knapsack problem demonstrates the greedy strategy of selecting items by highest value-to-weight ratio first. This approach yields the optimal solution when fractional quantities are allowed, and runs efficiently in O(N log N) time.