Problem Statement

Given items with value and weight, maximize total value inside a knapsack of capacity W.

Unlike 0/1 Knapsack, fractions of items are allowed.

Brute Force Intuition

Try every possible combination of items and fractions.

Although it guarantees correctness, the search space becomes huge.

Complexity

• Exponential

Moving Towards the Optimal Approach

Since fractions are allowed, we should always pick the item that gives maximum value per unit weight.

That means:

value / weight

should be highest first.

Greedy Pattern Recognition

Whenever you see:

• Fraction allowed
• Profit per unit
• Maximize value

Think:

Sort by Value/Weight Ratio

Optimal Java Solution

import java.util.*;

class Solution {

    double fractionalKnapsack(int W, Item arr[], int n) {

        Arrays.sort(arr, (a, b) ->
            Double.compare(
                (double)b.value / b.weight,
                (double)a.value / a.weight
            )
        );

        double profit = 0.0;

        for (Item item : arr) {

            if (W >= item.weight) {
                profit += item.value;
                W -= item.weight;
            } else {

                profit += ((double)item.value / item.weight) * W;
                break;
            }
        }

        return profit;
    }
}

Dry Run

Capacity = 50

Value Weight

60      10
100     20
120     30

Ratios:

6
5
4

Selection:

Take 10 weight -> +60

Take 20 weight -> +100

Remaining = 20

Take 20/30 of last item

120 × (20/30) = 80

Result

Maximum Profit = 240

Why Greedy Works?

Since fractions are allowed, taking the highest value-per-weight item first can never hurt the answer.

The locally optimal choice always contributes maximum profit per unit capacity.

Complexity Analysis

Interview One-Liner

Sort items by value-to-weight ratio and always pick the highest ratio item first, taking fractions when necessary.