Table of Contents
The fractional knapsack problem is a classic optimization problem in computer science and operations research. The goal is to fill a knapsack of fixed capacity with items of given weights and values, to maximize the total value while not exceeding the capacity.
As the name suggests, the fractional knapsack problem allows taking fractions of items, unlike the 0-1 knapsack problem which requires each item to be either fully taken or left out. This seemingly small difference creates major changes in how we approach these problems algorithmically.
In this comprehensive guide, we will take a deep dive into the greedy algorithm for the fractional knapsack problem. We will cover:
- What is the fractional knapsack problem
- Greedy algorithms and optimal substructure
- Intuition and workings of the greedy algorithm
- Proof of optimality
- Time and space complexity
- Counterexamples where greedy fails
- Implementations in Java, Python and C#
- Analysis of case studies and examples
So let‘s get started!
What is the Fractional Knapsack Problem?
Formally, the fractional knapsack problem is defined as:
Given a set of $n$ items, each with a weight $w_i$ and a value $v_i$, and a knapsack with capacity $W$, find fractions of items to include in the knapsack such that the total weight is <= $W$ and the total value is maximized.
For example, consider the following 5 items:
Item | Weight | Value
-----------------------
1 12 4
2 2 2
3 1 1
4 1 2
5 4 10And a knapsack with capacity $W = 15$.
What‘s the optimal way to fill this knapsack to maximize value while keeping weight <= 15?
The key things to note are:
- We can take fractional parts of items, not just 0 or 1. For example, we can take 0.6 of item 1.
- We want to maximize total value while keeping the weight less than knapsack capacity $W$.
This is what makes the fractional knapsack problem different from its 0-1 counterpart. The fractions allow more flexibility but also require different algorithms.
Greedy Algorithms and Optimal Substructure
Now let‘s talk about how we can solve this problem optimally and efficiently.
Greedy algorithms are a common approach for optimization problems. The key ideas behind greedy algorithms are:
- At every step, pick the locally optimal solution.
- Hope that this choice leads to the globally optimal solution.
Another requirement for greedy algorithms to work is optimal substructure. A problem has optimal substructure if an optimal solution can be constructed from optimal solutions to its subproblems.
For example, consider the following simple greedy algorithm:
- Sort items by value/weight ratio in decreasing order.
- Go through items and add them until knapsack is full.
Seems very intuitive! At every step we are locally optimizing by choosing the item with best value/weight.
But why does this lead to the optimal solution? This is because the fractional knapsack problem satisfies optimal substructure.
Once we prove this property, we can show the greedy algorithm is in fact optimal.
Intuition Behind Greedy Algorithm
Let‘s build some intuition on why the greedy algorithm outlined above works.
We sort items based on value per unit weight, also known as the cost effectiveness of that item. Items with higher unit value are more cost effective for us – they give more value per unit capacity they take up.
Our goal is to maximize total value. By always picking items with highest unit value first, we maximize how much "value per weight" we are able to fit in the knapsack.
This ensures that for the capacity available, we are always filling it with items that give maximum value per unit weight occupied. Hence we end up with the optimal solution.
Let‘s walk through an example to build intuition. Consider the following instance:
Item | Weight | Value
----------------------
A 3 30
B 1 10
C 2 15And knapsack capacity $W = 4$.
The value per unit weights are:
- A: 10
- B: 10
- C: 7.5
The greedy algorithm first sorts them to get {A, B, C} in descending value per unit weight order.
We first take item A. This uses 3 units of capacity and gives 30 units of value.
We still have 1 unit of capacity left. Item B has the next highest value per unit weight, which is 10. So we take it and get value 10.
Now the knapsack is full. Was this optimal?
Let‘s compare to any other solution, say take {B, C} which fills knapsack too. This would give value 10 + 15 = 25.
The greedy solution gave 30 + 10 = 40 value in total. So it does indeed give the optimal solution!
Let‘s formalize this intuition.
Proof of Optimality
We will now prove that the greedy algorithm outlined before is optimal by showing that it satisfies optimal substructure.
Theorem: The greedy algorithm which sorts items by value/weight ratio and adds fractions greedily in that order, gives an optimal solution.
Proof: Let the greedy algorithm solution be $S = (x_1, x_2, …, x_n)$ where $x_i$ is the fraction of item $i$ selected by the algorithm.
Now consider any other solution $S′$, such that:
- $S′$ fits in the knapsack (sums of fractions multiply with weights fits capacity)
- $S′$ has total value >= the total value of greedy solution $S$.
Our aim is to show that $S′$ cannot have higher value than $S$.
Let‘s look at the first item where $S‘$ differs from $S$.
- Say first $k$ items in both solutions are same fractions.
- At $(k+1)^{th}$ item, $S‘$ takes fraction $y{k+1}$ while $S$ takes $x{k+1}$.
Since $S‘$ took a different fraction, it means by greedy choice criteria that:
valuePerUnitWeight(item k+1) >= valuePerUnitWeight(any remaining items)Now let‘s create an intermediate solution $S′′$:
- First $k$ items in $S‘‘$ are same as in $S‘$
- Items after $k+1$ are same fractions as in greedy solution $S$.
$S‘‘$ has total value = Value of $S′$ (first k items same) + Value of remaining items from $S$ (same fractions).
But we constructed $S‘‘$ such that value per unit weight of $k+1$ item was highest. So swapping fraction of $k+1$ item from $y{k+1}$ to $x{k+1}$ would either keep value the SAME or INCREASE it.
In essence, $S‘‘$ has total value >= $S‘$.
But $S‘‘$ takes same objects as $S$, just possibly different fractions. Since $S$ was constructed greedily, $S$ must have higher value than $S‘‘$.
Combining the above:
Value(S) >= Value(S‘‘) >= Value(S‘)Therefore, greedy solution $S$ has the optimal value. ∎
This completes our proof by contradiction. The key insight was that by greedy choice, we ensure that fraction swapped items don‘t reduce value. This allows us to construct an equal or higher solution matching the greedy fractions.
Having proven optimality, let‘s analyze the algorithm‘s complexity.
Time and Space Complexity
The greedy algorithm has the following outline:
- Calculate value per unit weight for each item O(n)
- Sort items by value/weight ratio O(nlogn)
- Iterate through items adding fractions O(n)
Step 1 and 3 take linear time. Step 2 takes nlogn with efficient sorting. So overall complexity is O(nlogn).
The space complexity is O(1) – only constant extra storage needed for fractions of items.
So this greedy approach is both optimal and efficient. In fact, it has the best possible asymptotic time complexity. This makes it the standard algorithm to use for fractional knapsack.
Limitations and Counterexamples
Greedy algorithms fail when the problem does not satisfy optimal substructure. Are there cases where this greedy algorithm can fail?
Interestingly, for the fractional knapsack problem, the greedy algorithm is always optimal! Researchers have proved that the fractional knapsack problem exhibits optimal substructure.
This means that unlike other problems, the greedy approach is guaranteed to solve fractional knapsack optimally. There are no counterexamples where it fails. This is great news computationally!
However, there are slight variants of fractional knapsack where it does fail:
1. Negative Weights
If items are allowed to have negative weights (i.e they add capacity), then greedy can fail by taking too much negative weight too early when it may not be optimal later.
2. Rounding Required
If the fractions need to be rounded at the end to ensure integer amounts of items, greedy fails as it is too "short sighted" in rounding early on without looking ahead.
But for the standard definition of fractional knapsack with positive weights and continuous quantities, the greedy approach is mathematically guaranteed to succeed!
Code Implementations
Let‘s now look at implementations in various languages to solidify understanding.
Java
import java.util.*;
class Item {
int weight, value;
Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
}
class Solution {
static double fractionalKnapsack(int W, Item arr[], int n) {
Arrays.sort(arr, (a, b) -> Double.compare(b.value*1.0/b.weight, a.value*1.0/a.weight));
int curWeight = 0;
double finalvalue = 0.0;
for (int i = 0; i < n; i++) {
if (curWeight + arr[i].weight <= W) {
curWeight += arr[i].weight;
finalvalue += arr[i].value;
} else {
int remain = W - curWeight;
finalvalue += arr[i].value * ((double) remain / arr[i].weight);
break;
}
}
return finalvalue;
}
public static void main(String[] args) {
int W = 15;
Item[] arr = {new Item(12, 4),
new Item(2, 2),
new Item(1, 1),
new Item(1, 2),
new Item(4, 10)};
int n = arr.length;
System.out.println(fractionalKnapsack(W, arr, n));
}
}This implements the greedy algorithm directly as per the rough outline discussed before.
Time complexity is O(nLogn) to sort items and space O(1).
Python
class Item:
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.cost = value / weight
def fractionalKnapsack(W, Items, n):
Items.sort(key = lambda x: x.cost, reverse=True)
curWeight = 0
finalvalue = 0
for i in range(n):
if curWeight + Items[i].weight <= W:
curWeight += Items[i].weight
finalvalue += Items[i].value
else:
remain = W - curWeight
finalvalue += Items[i].value * (remain / Items[i].weight)
break
return finalvalue
W = 15
arr = [Item(12, 4),
Item(2, 2),
Item(1, 1),
Item(1, 2),
Item(4, 10)]
n = len(arr)
print(fractionalKnapsack(W, arr, n))Same idea as Java, using sorted() and custom Item class. O(nLogn) and O(1) complexity.
C#
using System;
class Item {
public int weight, value;
public Item(int weight, int value)
{
this.weight = weight;
this.value = value;
}
};
class Solution {
static double fractionalKnapsack(int W, Item [] arr, int n) {
Array.Sort(arr, (x, y) =>
Double.Compare(x.value * 1.0 / x.weight,
y.value * 1.0 / y.weight) * -1);
int curWeight = 0;
double finalvalue = 0.0;
for (int i = 0; i < n; i++) {
if (curWeight + arr[i].weight <= W) {
curWeight += arr[i].weight;
finalvalue += arr[i].value;
}
else {
int remain = W - curWeight;
finalvalue += (double)remain /
arr[i].weight * arr[i].value;
break;
}
}
return finalvalue;
}
public static void Main() {
int W = 15;
Item[] arr = {new Item(12,4),
new Item(2,2),
new Item(1,1),
new Item(1,2),
new Item(4,10)};
int n = arr.Length;
Console.WriteLine(fractionalKnapsack(W, arr, n));
}
}Same overall working using C#‘s Array.Sort() and reverse parameter.
The implementations in other languages follow the same greedy approach overall.
Analysis on Case Studies
Finally, let‘s apply the fractional knapsack algorithm to some concrete examples to gain more insight. Consider the following case study:
Item | Weight | Value
----------------------
A 20 100
B 30 120
C 60 200 And knapsack capacity W = 100.
First, calculate value per unit weight:
A -> 100/20 = 5
B -> 120/30 = 4
C -> 200/60 = ~3.33Sorting them by decreasing order, we get {A, B, C}.
The greedy algorithm starts with item A. We take it fully.
Current weight is 20 and value is 100.
Next is item B. We can fully take it too.
Now current weight is 20 + 30 = 50. Value is 100 + 120 = 220.
For item C, only 50 capacity remains in knapsack. So we take 50/60 = 0.83 fraction of it.
Adding the remaining value 0.83 * 200 = 166.
The total value is 100 + 120 + 166 = 386.
We can verify that this is indeed the maximum possible value that can be achieved with this knapsack capacity.
Let‘s take another example with 2 items:
Item | Weight | Value
----------------------
A 3 30
B 5 45And capacity W = 7.
Value per unit weights are:
- A -> 10 per unit
- B -> 9 per unit
The greedy algorithm first fully takes item A (weight 3, value 30).
4 capacity remains, so we take 4/5 = 0.8 fractions of item B (adding 0.8 * 45 = 36 value).
The total value is 30 + 36 = 66.
Analyzing case studies in this way helps build deeper insight into the algorithm‘s workings.
Conclusion
The fractional knapsack problem is an interesting optimization problem that comes up in domains like resource allocation and load balancing. Unlike the 0-1 knapsack, the fractional version allows taking fractions of items rather than all or nothing.
In this post, we took a deep dive into the greedy algorithm for solving fractional knapsack optimally. The key ideas included:
- Intuition behind sorting by cost effectiveness
- Proof of optimality by optimal substructure
- Linear time and constant space complexity
- Code implementations demonstrating the core greedy logic
- Analysis of case studies to build further insight
Greedy algorithms work quite well in practice thanks to their speed and simplicity. For fractional knapsack, we saw that the greedy method is ironclad – no counter cases exist where it fails to deliver the optimum. This reliability along with efficiency makes it the best approach known theoretically and practically.