Fractional Knapsack Algorithm

The fractional knapsack problem is a foundational optimization challenge in computer science where a thief or automated system must select items with given values and weights to maximize total value in a capacity-constrained bag, with the crucial allowance that items can be broken down into fractional parts. Unlike the 0/1 Knapsack problem (where items are all-or-nothing), the fractional variant can be optimally solved using a greedy strategy.

1. Problem Statement & The Core Challenge

You are given $n$ items. Each item is defined as a pair containing a value and a weight. You also possess a knapsack (bag) with a maximum weight capacity $W$ (e.g., $W = 90$).

Your objective is to maximize the total accumulated value inside the knapsack without exceeding its maximum weight capacity. You are allowed to pick items in any order, and crucially, you can take fractions of an item if the remaining bag capacity is smaller than the item's full weight.

Sample Problem Data

Imagine a knapsack capacity $W = 90$ and the following item set (Value, Weight):

• Item 1: (100, 20)
• Item 2: (60, 10)
• Item 3: (100, 50)
• Item 4: (200, 50)

2. Real-Life Analogy: Unit Price Shopping

Real-Life Analogy: Think of buying bulk goods or loose fruits at a market where bins have different total prices and total weights. If your shopping basket can only carry 90 kg total, you naturally want to get the most value (nutrition, quality, or resale price) per single kilogram ($1 \text{ kg}$) of weight you put into your basket. You pick items that offer the highest "bang for your buck" per unit of weight.

3. Why Naive Approaches Fail

When learners first approach optimization problems, two intuitive (but flawed) greedy heuristics come to mind:

1. Pick Maximum Value First: Always grab the item with the highest absolute value first.
2. Pick Minimum Weight First: Always grab the lightest items first to pack as many items as possible.

The Flaw of Maximum Value Heuristic

Imagine your bag capacity is $W = 90$, and you have an item with Value = 200, Weight = 90.

• If you greedily pick this single item because its value ($200$) is the highest, your bag is full. Your total value is $200.
• However, if you picked smaller items with better density, you could achieve $380. Therefore, blindly choosing maximum absolute value fails.

4. The Correct Greedy Strategy: Value-Per-Weight Ratio

To maximize value efficiently, we must calculate the Value-per-Weight ratio ($\text{Value} / \text{Weight}$) for every single item. This tells us exactly how much value we receive for every $1$ unit of weight.

Let's compute the unit value for our sample items:

• Item 1 (100, 20): $\frac{100}{20} = 5.0$ value per weight unit
• Item 2 (60, 10): $\frac{60}{10} = 6.0$ value per weight unit
• Item 3 (100, 50): $\frac{100}{50} = 2.0$ value per weight unit
• Item 4 (200, 50): $\frac{200}{50} = 4.0$ value per weight unit

Sorted Order (Descending by Value-per-Weight)

1. Item 2: (60, 10) -> Ratio: $6.0$
2. Item 1: (100, 20) -> Ratio: $5.0$
3. Item 4: (200, 50) -> Ratio: $4.0$
4. Item 3: (100, 50) -> Ratio: $2.0$

5. Step-by-Step Flow Walkthrough

Let's trace how the algorithm fills a knapsack of capacity $W = 90$ using our sorted items:

6. Algorithmic Pseudocode & Implementation Design

Below is the structured algorithm for implementing the Fractional Knapsack solution.

Data Structure Definition

An item is represented as an object containing value and weight:

struct Item {
    int value;
    int weight;
};

Custom Comparator

To sort items in descending order of their value-per-weight ratio:

bool compareItems(Item a, Item b) {
    double r1 = (double)a.value / (double)a.weight;
    double r2 = (double)b.value / (double)b.weight;
    return r1 >= r2; // Descending order
}

Main Fractional Knapsack Function

double fractionalKnapsack(Item arr[], int n, int W) {
    // Step 1: Sort items by value/weight in descending order
    sort(arr, arr + n, compareItems);
    
    double totalVal = 0.0;
    int currentWeight = W;
    
    for (int i = 0; i < n; i++) {
        // Case A: Item fits completely into the remaining capacity
        if (arr[i].weight <= currentWeight) {
            currentWeight -= arr[i].weight;
            totalVal += arr[i].value;
        } 
        // Case B: Item exceeds remaining capacity; take a fraction
        else {
            double unitValue = (double)arr[i].value / (double)arr[i].weight;
            totalVal += unitValue * currentWeight;
            currentWeight = 0;
            break; // Bag is full, exit loop
        }
    }
    
    return totalVal;
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Problem Nature: Fractional Knapsack allows taking fractions of items, setting it apart from 0/1 Knapsack.
• Optimization Goal: Maximize total value without exceeding the weight limit $W$.
• Greedy Choice Property: Always prioritize items that offer the highest Value-per-Weight ratio ($\text{Value} / \text{Weight}$).
• Custom Comparator: Sorting must be executed in descending order based on the unit ratio (double value / weight).
• Fractional Inclusion: When an item exceeds the remaining bag capacity, compute its unit worth and multiply by the exact remaining weight capacity.
• Early Termination: The moment remaining capacity $W$ reaches zero, break the loop immediately to optimize execution time.
• Data Types: Always use double or float for ratios and accumulated values to prevent integer division truncation and precision loss.