Greedy: Fractional Knapsack Problem

Imagine you're a logistics manager filling a cargo plane with valuable shipments, but you can't fit everything. Some shipments can be split open to take just a portion of their contents. Your goal is to maximize profit, and you need a fast, reliable strategy. This is the essence of the Fractional Knapsack Problem, a classic optimization challenge where a greedy algorithm provides a perfect, efficient solution. Understanding this problem teaches you a powerful problem-solving paradigm and clarifies a fundamental distinction in computational complexity: when an item's divisibility makes a problem drastically easier to solve.

Problem Definition and Core Idea

The Fractional Knapsack Problem is formally defined as follows: you have a knapsack (or container) with a maximum weight capacity $W$. You are given a set of $n$ items, each with a positive value $v_i$ and a positive weight $w_i$. The key difference from other knapsack problems is that you can take a fractional part of any item. If you take a fraction $f$ (where $0\le f\le 1$) of item $i$, you gain a value of $f\ast v_i$ and use $f\ast w_i$ of the knapsack's capacity. Your objective is to maximize the total value of items in the knapsack without exceeding its weight capacity.

The core insight for solving it optimally is to prioritize items not by their total value or lowest weight, but by their value density or value-to-weight ratio, $r_i=v_i/w_i$. An item with a high ratio gives you more value per unit of weight consumed. A greedy algorithm makes a series of locally optimal choices—at each step, taking as much as possible of the available item with the highest ratio—with the hope that this leads to a globally optimal solution. For this specific problem, that hope is fulfilled.

The Greedy Algorithm: Step-by-Step

The algorithm is straightforward and efficient, running in $O(n\log n)$ time due to the required sorting step.

1. Calculate Ratios: For each item $i$, compute its value-to-weight ratio, $r_i=v_i/w_i$.
2. Sort: Sort all items in decreasing order of their ratio $r_i$.
3. Iterate and Fill: Initialize the knapsack as empty (remaining capacity = $W$) and total value = $0$.

• Go through the sorted list of items.
• For each item, if you can take the whole item ($w_i\le$ remaining capacity), take all of it. Add $v_i$ to the total value and subtract $w_i$ from the remaining capacity.
• If you cannot take the whole item (remaining capacity $<w_i$), take a fraction of it. The fraction is remaining capacity / w_i. Add (remaining capacity / w_i) * v_i to the total value. The knapsack is now full (remaining capacity becomes $0$).

1. Terminate: The algorithm stops when the knapsack is full or all items have been considered.

Worked Example: Let capacity $W=50$. Items: (Value, Weight) = A(60, 10), B(100, 20), C(120, 30).

1. Calculate ratios: $r_A=60/10=6.0$, $r_B=100/20=5.0$, $r_C=120/30=4.0$.
2. Sort: A (ratio 6), B (ratio 5), C (ratio 4).
3. Fill:

• Take all of A. Value += 60, Capacity left = $50-10=40$.
• Take all of B. Value += 100, Capacity left = $40-20=20$.
• Cannot take all of C (weight 30 > 20). Take a fraction: $20/30$ of C. Value += $(20/30)\ast 120=80$.

1. Total Optimal Value = $60+100+80=240$.

Proof of Optimality

Why does this greedy approach guarantee the best possible solution? The proof hinges on the ability to take fractions and the concept of opportunity cost. If the knapsack contains any amount of an item with a lower ratio $r_l$ while some amount of a higher-ratio item $r_h$ (not necessarily from the same input set) is left out, you can always swap some weight from the lower-ratio item for an equal weight of the higher-ratio item. This swap would increase the total value without changing the total weight, proving the original solution wasn't optimal. Therefore, an optimal solution must fill the knapsack by taking as much as possible of the highest-ratio items first, exactly what our algorithm does. This is often formalized using an exchange argument.

Contrast with the 0/1 Knapsack Problem

This contrast is crucial for understanding problem complexity. The 0/1 Knapsack Problem has identical inputs except for one constraint: you must take an item entirely or leave it behind—no fractions allowed. This indivisibility changes everything.

A greedy strategy based on value-to-weight ratio fails for the 0/1 variant. Consider a knapsack with $W=50$ and items: (60, 10, ratio=6), (100, 20, ratio=5), (120, 30, ratio=4). The greedy fractional solution (A, B, 2/3 of C) yields 240, but this isn't allowed in 0/1. The greedy 0/1 algorithm would take A (value 60, weight 10), then B (value 100, weight 20), then have 20 capacity left but could not take C (weight 30). Total value = 160. However, the true 0/1 optimal solution is to take B and C: value = 100 + 120 = 220. The greedy choice for the first item (the highest ratio) precluded a better overall combination.

The 0/1 Knapsack Problem is NP-Hard, requiring more complex techniques like Dynamic Programming (DP) to find an exact solution, which runs in pseudo-polynomial time $O(nW)$. The fractional version, solvable greedily in $O(n\log n)$, is in complexity class P. This highlights how a small change in problem constraints—divisibility—can fundamentally alter the computational complexity and solution strategy.

Common Pitfalls

1. Applying the Greedy Ratio Strategy to 0/1 Knapsack: As demonstrated, sorting by ratio and taking whole items does not guarantee an optimal solution for the 0/1 problem. This is the most frequent conceptual error. Remember, the greedy algorithm's correctness for the fractional version is not transferable.
2. Incorrect Sorting or Fraction Calculation: Always sort in decreasing order of the value-to-weight ratio. When calculating the final fraction, it's easy to mistakenly use the remaining value instead of the remaining capacity. The correct fraction is remaining_capacity / item_weight.
3. Overlooking Algorithm Efficiency: While implementing, a naive approach might involve repeatedly searching for the highest-ratio item, leading to $O(n^2)$ time. The standard efficient implementation requires a one-time sort ($O(n\log n)$) followed by a linear scan ($O(n)$).
4. Misunderstanding the Problem Scope: Assume fractional items are allowed only if the problem explicitly states it or uses language like "you can take parts of items." In many real-world and algorithmic contexts, the default assumption is the 0/1 variant.

Summary

• The Fractional Knapsack Problem is an optimization task where items can be taken in fractions, and the objective is to maximize total value without exceeding a weight limit.
• The optimal solution is achieved using a greedy algorithm that repeatedly takes as much as possible of the item with the highest value-to-weight ratio.
• The algorithm's optimality can be proven using an exchange argument, which shows that any solution not following the greedy order can be improved.
• This problem stands in sharp contrast to the 0/1 Knapsack Problem, where items are indivisible. The greedy ratio strategy fails for 0/1, which instead requires Dynamic Programming.
• The divisibility property makes the fractional version computationally easy (polynomial time), while the 0/1 version is NP-Hard, illustrating how problem constraints fundamentally impact complexity.