Fractional Knapsack — When Greedy Achieves Optimality

Imagine you are a thief breaking into a warehouse filled with valuable commodities. You have a knapsack that can carry at most W kilograms of goods. The warehouse contains n different items, each with a specific weight and value. Your objective is clear and ruthless: maximize the total value of goods you carry away, subject to the weight limitation of your knapsack.

This scenario, while morally questionable, encapsulates one of the most important optimization problems in computer science: the Knapsack Problem. Variations of this problem appear across resource allocation, financial portfolio optimization, cargo loading, bandwidth allocation, and countless other domains where limited capacity must be allocated among competing demands to maximize overall utility.

At the heart of every knapsack problem lies the concept of an item. Understanding what constitutes an item, and how items are characterized, is fundamental to formulating and solving these problems correctly.

Formal Definition:

An item i in the Fractional Knapsack problem is defined by a tuple (wᵢ, vᵢ) where:

• wᵢ (weight): A positive real number representing the item's weight, mass, or consumption of the constrained resource
• vᵢ (value): A positive real number representing the benefit, utility, or worth gained by selecting this item

Given n items, we have:

• Items: i ∈ {1, 2, 3, ..., n}
• Weights: w₁, w₂, ..., wₙ (all positive real numbers)
• Values: v₁, v₂, ..., vₙ (all positive real numbers)
• Capacity: W (maximum total weight the knapsack can hold)

The Two Fundamental Characteristics:

Every item embodies a cost (the weight it consumes) and a benefit (the value it provides). The challenge arises because:

1. Resources are finite: The knapsack capacity W is limited
2. Trade-offs are unavoidable: Including one heavy item may preclude including several lighter ones
3. Goals are competing: We want maximum value but must respect the weight constraint

This tension between cost and benefit, between greed and constraint, is what makes the knapsack problem both intellectually rich and practically relevant.

Concrete Interpretation:

Think of weight as 'what you pay' and value as 'what you get.' Different items offer different 'exchange rates' between these currencies. The optimization problem is essentially: given a fixed budget of weight, how do you allocate it across items to maximize total value received?

The relationship between an item's weight and its value is central to understanding knapsack problems. There is no fixed relationship — an item can be heavy and valuable, light and valuable, heavy and less valuable, or light and less valuable. This variability is what creates the optimization challenge.

Value Density — The Critical Ratio:

The value-to-weight ratio (also called value density or efficiency) of item i is:

ρᵢ = vᵢ / wᵢ

This ratio represents the value gained per unit of weight consumed. It answers the question: "How much bang do I get for each buck of capacity I spend?"

• Higher ratio → More efficient use of capacity
• Lower ratio → Less efficient use of capacity

Interpreting Value Density:

Look at the table above. The diamond ring has the highest value density — every gram carried returns enormous value. The copper wire has the lowest — it takes significant capacity for modest returns.

Key Insight: Value density alone doesn't determine the optimal selection. Consider a knapsack with capacity 10kg:

• Taking only the diamond ring: Weight = 0.1kg, Value = $1000 (but 9.9kg unused!)
• Taking gold bar + silver ingot + bronze statue won't fit (17kg total)
• Some combination must balance high-density items with capacity utilization

This nuance — that maximizing value isn't merely about picking the highest-density items — is crucial. In the Fractional Knapsack variant, we can fill remaining capacity with fractions of items, which fundamentally changes the optimization landscape.

The capacity constraint W is what transforms an trivial selection problem into an optimization challenge. Without this constraint, the solution would be obvious: take everything.

Formal Statement of the Constraint:

For a selection of items, the total weight must not exceed capacity:

∑(selected items) wᵢ ≤ W

In the Fractional Knapsack variant, if we take a fraction xᵢ (where 0 ≤ xᵢ ≤ 1) of each item i, the constraint becomes:

∑ᵢ₌₁ⁿ (xᵢ · wᵢ) ≤ W

Why Constraints Create Complexity:

The capacity constraint forces trade-off decisions. Each unit of capacity spent on one item is unavailable for others. This creates dependencies between decisions:

1. Opportunity cost: Taking item A means potentially not being able to take item B
2. Combinatorial explosion: With n items, there are potentially 2ⁿ possible subsets in the discrete case
3. Optimization pressure: We must choose wisely, not just greedily pick anything

The Fractional Relaxation:

In the Fractional Knapsack, we can take any fraction of an item. This means:

• If we can only fit 60% of an item, we take 60% and gain 60% of its value
• Items become infinitely divisible goods rather than discrete objects
• The decision space becomes continuous rather than combinatorial

This relaxation is what makes the greedy approach work perfectly. In the discrete (0/1) variant, we cannot take partial items, which destroys the greedy property — but we'll explore that contrast in a later page.

Let us now precisely state the Fractional Knapsack problem in mathematical terms. This formal specification removes all ambiguity and provides the foundation for algorithmic solutions.

Given:

• n items, each item i ∈ {1, 2, ..., n}
• Weight of item i: wᵢ > 0
• Value of item i: vᵢ > 0
• Knapsack capacity: W > 0

Decision Variables:

• xᵢ ∈ [0, 1]: The fraction of item i to include (0 means exclude entirely, 1 means include entirely)

Objective Function (Maximize):

maximize ∑ᵢ₌₁ⁿ (xᵢ · vᵢ)

Subject to Constraints:

1. Capacity constraint: ∑ᵢ₌₁ⁿ (xᵢ · wᵢ) ≤ W
2. Fraction bounds: 0 ≤ xᵢ ≤ 1 for all i ∈ {1, 2, ..., n}

Interpreting the Formulation:

• Objective: We want to maximize total value harvested, which is the sum of (fraction taken × item value) across all items

• Capacity constraint: The total weight of all fractional selections must not exceed the knapsack's capacity

• Fraction bounds: We cannot take negative amounts (xᵢ ≥ 0) or more than an item exists (xᵢ ≤ 1)

Why This Is an Optimization Problem:

The problem asks for the best possible allocation — the one achieving maximum value while respecting constraints. There may be many feasible solutions (allocations that satisfy constraints), but we seek the optimal one.

Feasible Solutions vs. Optimal Solutions:

• Feasible solution: Any assignment of x₁, x₂, ..., xₙ satisfying all constraints
• Optimal solution: A feasible solution achieving the maximum possible objective value

Our goal is to find an optimal solution efficiently — ideally in polynomial time.

Let's work through a concrete example to solidify understanding. This example will serve as a running case study throughout the module.

Problem Instance:

You have a knapsack with capacity W = 50 kg. Three items are available:

Observation 1: Total Weight Exceeds Capacity

Total weight of all items = 10 + 20 + 30 = 60 kg, but capacity = 50 kg. We cannot take everything — a selection must be made.

Observation 2: Items Ranked by Value Density

Item A > Item B > Item C in value density. Per unit of weight, Item A delivers the most value.

Observation 3: The Non-Obvious Optimal

What should we take? Let's explore some candidate solutions:

Candidate 1: Take only highest-density item (A)

• Take all of A: Weight = 10kg, Value = $60
• Remaining capacity: 40kg (wasted if we stop here)
• Total value: $60 — clearly suboptimal!

Candidate 2: Take A entirely, then as much of B and C as possible

• Take all of A: 10kg, $60
• Take all of B: 20kg, $100
• Remaining: 20kg; take 20/30 = 2/3 of C: ~$80
• Total: 10 + 20 + 20 = 50kg; Value = 60 + 100 + 80 = $240

Candidate 3: Take only the highest-value item (C)

• Take all of C: 30kg, $120
• Remaining: 20kg; take all of B: 20kg, $100
• Total: 50kg; Value = $220

Candidate 2 ($240) beats Candidate 3 ($220). The greedy-by-density approach is the winner here.

The Fractional Knapsack model appears disguised in numerous real-world optimization scenarios. Recognizing these instances is key to applying the solution pattern effectively.

The knapsack problem belongs to a family of related optimization problems. Understanding how Fractional Knapsack differs from its cousins clarifies when the greedy approach applies.

Other Related Problems:

• Unbounded Knapsack: Can take unlimited copies of each item. Also solvable by DP, not greedy.
• Multi-dimensional Knapsack: Multiple constraints (weight, volume, etc.). Significantly harder.
• Subset Sum: Special case where vᵢ = wᵢ; asking if we can exactly hit capacity W.

Why Fractionality Matters:

The ability to take fractions fundamentally changes the problem's structure. In 0/1 Knapsack, you might face scenarios where the best items don't fit together optimally. Taking a high-density item might waste capacity that could be better used by smaller items.

In Fractional Knapsack, you never waste capacity (assuming total weight exceeds W). You simply fill remaining capacity with the next-best item, taking exactly as much as fits. This 'greedy stays optimal' property comes precisely from fractionality.

We have established the foundational concepts of the Fractional Knapsack problem. Let's consolidate what we've learned:

What's Next:

Now that we understand the problem structure — items, weights, values, capacity, and optimization objective — we're ready to explore the solution strategy. The next page examines taking fractions in depth: what it means algorithmically, how partial selections are computed, and why this capability is the linchpin that makes greedy algorithms optimal for this problem.