GreedyProblem 5 of 35

Fractional Knapsack Problem

Brute Force
Time: O(2^n)
Space: O(n)
Optimal
Time: O(n log n)
Space: O(1)

Problem Statement

Given weights and values of n items, and a knapsack with capacity W, find the maximum value that can be put in the knapsack. Unlike 0/1 Knapsack, you can break items (take fractions of items).

Constraints:

  • 1 ≤ n ≤ 10^5
  • 1 ≤ W ≤ 10^9
  • 1 ≤ weight[i], value[i] ≤ 10^6

Example:

  • Input: weights = [10, 20, 30], values = [60, 100, 120], W = 50
  • Output: 240
  • Explanation: Take full items of weight 10, 20 (value = 60 + 100 = 160), then 2/3 of item with weight 30 (value = 80). Total = 240.

Example 2:

  • Input: weights = [10, 40, 20, 30], values = [60, 40, 100, 120], W = 50
  • Output: 240
  • Explanation: Take items with best value/weight ratio first.

Approach 1: Brute Force (Try All Fractions)

Intuition

Try all possible combinations of items and fractions. This is impractical but shows the exponential nature of the problem without the greedy insight.

Algorithm

  1. Generate all possible selections
  2. For each item, try taking various fractions (0, 0.1, 0.2, ..., 1)
  3. Track maximum value while staying within capacity
java
import java.util.*;

public class Solution {
    private double maxValue = 0;
    
    private void solve(int[][] items, int idx, double capacity, double value) {
        maxValue = Math.max(maxValue, value);
        
        if (idx == items.length || capacity <= 0) return;
        
        double maxFraction = Math.min(1.0, capacity / items[idx][0]);
        
        for (double frac = maxFraction; frac >= 0; frac -= 0.1) {
            double weight = frac * items[idx][0];
            double val = frac * items[idx][1];
            solve(items, idx + 1, capacity - weight, value + val);
        }
    }
    
    public double fractionalKnapsack(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[][] items = new int[n][2];
        for (int i = 0; i < n; i++) {
            items[i][0] = weights[i];
            items[i][1] = values[i];
        }
        
        maxValue = 0;
        solve(items, 0, W, 0);
        return maxValue;
    }
}

Complexity Analysis

  • Time Complexity: O(2^n) - Exponential due to trying all combinations
  • Space Complexity: O(n) - Recursion stack

Approach 2: Greedy (Sort by Value/Weight Ratio) - Optimal

Intuition

The greedy approach is to always pick the item with the highest value per unit weight. Since we can take fractions, we should maximize value density.

Key Insight: Items with higher value/weight ratio give more value per unit capacity used.

Algorithm

  1. Calculate value/weight ratio for each item
  2. Sort items by ratio in descending order
  3. Take items greedily starting from highest ratio
  4. If item fits completely, take it entirely
  5. Otherwise, take the fraction that fits
java
import java.util.*;

class Item implements Comparable<Item> {
    int weight;
    int value;
    double ratio;
    int index;
    
    Item(int weight, int value, int index) {
        this.weight = weight;
        this.value = value;
        this.ratio = (double) value / weight;
        this.index = index;
    }
    
    @Override
    public int compareTo(Item other) {
        return Double.compare(other.ratio, this.ratio);  // Descending
    }
}

public class FractionalKnapsack {
    public double solve(int[] weights, int[] values, int W) {
        int n = weights.length;
        
        // Create items with ratio
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(weights[i], values[i], i);
        }
        
        // Sort by value/weight ratio in descending order
        Arrays.sort(items);
        
        double totalValue = 0;
        double remainingCapacity = W;
        
        for (Item item : items) {
            if (remainingCapacity <= 0) break;
            
            if (item.weight <= remainingCapacity) {
                // Take entire item
                totalValue += item.value;
                remainingCapacity -= item.weight;
            } else {
                // Take fraction
                double fraction = remainingCapacity / item.weight;
                totalValue += fraction * item.value;
                remainingCapacity = 0;
            }
        }
        
        return totalValue;
    }
    
    public double[] getDetailedSolution(int[] weights, int[] values, int W) {
        int n = weights.length;
        
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(weights[i], values[i], i);
        }
        
        Arrays.sort(items);
        
        double[] fractions = new double[n];
        double remainingCapacity = W;
        
        for (Item item : items) {
            if (remainingCapacity <= 0) break;
            
            if (item.weight <= remainingCapacity) {
                fractions[item.index] = 1.0;
                remainingCapacity -= item.weight;
            } else {
                fractions[item.index] = remainingCapacity / item.weight;
                remainingCapacity = 0;
            }
        }
        
        return fractions;
    }
    
    public static void main(String[] args) {
        FractionalKnapsack fk = new FractionalKnapsack();
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int W = 50;
        
        System.out.println("Maximum value: " + fk.solve(weights, values, W));  // 240
    }
}

Dry Run Example

weights = [10, 20, 30] values = [60, 100, 120] W = 50 Calculate ratios: Item 0: value/weight = 60/10 = 6.0 Item 1: value/weight = 100/20 = 5.0 Item 2: value/weight = 120/30 = 4.0 After sorting by ratio (descending): Item 0 (ratio=6.0), Item 1 (ratio=5.0), Item 2 (ratio=4.0) Greedy selection: remaining_capacity = 50, total_value = 0 Step 1: Item 0 (weight=10, value=60, ratio=6.0) - 10 <= 50, take entire item - remaining_capacity = 50 - 10 = 40 - total_value = 0 + 60 = 60 Step 2: Item 1 (weight=20, value=100, ratio=5.0) - 20 <= 40, take entire item - remaining_capacity = 40 - 20 = 20 - total_value = 60 + 100 = 160 Step 3: Item 2 (weight=30, value=120, ratio=4.0) - 30 > 20, take fraction - fraction = 20/30 = 2/3 - value_taken = (2/3) × 120 = 80 - remaining_capacity = 0 - total_value = 160 + 80 = 240 Result: Maximum value = 240 Items taken: Item 0 (100%), Item 1 (100%), Item 2 (66.67%)

Complexity Analysis

  • Time Complexity: O(n log n)
    • O(n) for calculating ratios
    • O(n log n) for sorting
    • O(n) for greedy selection
  • Space Complexity: O(n) for storing items (can be O(1) with in-place modifications)

Comparison: Fractional vs 0/1 Knapsack

| Aspect | Fractional Knapsack | 0/1 Knapsack | |--------|---------------------|--------------| | Items | Can take fractions | Must take whole or nothing | | Approach | Greedy | Dynamic Programming | | Complexity | O(n log n) | O(nW) | | Optimality | Greedy is optimal | Greedy is NOT optimal |

Key Takeaways

  1. Greedy by Ratio: Sort by value/weight ratio in descending order
  2. Fractions Allowed: The key that makes greedy work
  3. Take Greedily: Always take item with highest ratio first
  4. Partial Taking: If item doesn't fit, take the fraction that fits
  5. Optimal Proof: Exchange argument shows greedy is optimal
  6. vs 0/1 Knapsack: 0/1 requires DP, fractional uses greedy
  7. Real Applications: Resource allocation, cargo loading
  8. Edge Cases: Single item, all items fit, no item fits
Previous
Water Connection Problem
Next
Greedy Algorithm to find Minimum number of Coins