DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Fractional Knapsack

#algorithms #computerscience #java #tutorial

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
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run 

Capacity = 50

Value Weight

60      10
100     20
120     30
Enter fullscreen mode Exit fullscreen mode

Ratios:

6
5
4
Enter fullscreen mode Exit fullscreen mode

Selection:

Take 10 weight -> +60

Take 20 weight -> +100

Remaining = 20

Take 20/30 of last item

120 × (20/30) = 80
Enter fullscreen mode Exit fullscreen mode

Result 

Maximum Profit = 240
Enter fullscreen mode Exit fullscreen mode

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

Metric Complexity
Time O(N log N)
Space O(1)

Interview One-Liner

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

Top comments (0)