Fractional knapsack
Updated:
⚠️ This post was created when I was in high school and is no longer maintained.
In this setting, the thief can take fractions of items, rather than having to make a binary (01) choice for each item. You can think of an item in the 01 knapsack problem as being like a gold ingot and an item in the fractional knapsack problem as more like gold dust. —— CRLS
1. Fractional Knapsack VS 01 Knapsack

Both knapsack problems exhibit the optimalsubstructure property.
 For the 01 problem, consider the most valuable load that weighs at most
W
pounds. If we remove item
j
from this load, the remaining load must be the most valuable load weighing at mostW  w_j
that the thief can take from then1
original items excluding itemj
.
 If we remove item
 For the comparable fractional problem,
 consider that if we remove a weight
w
of one itemj
from the optimal load, the remaining load must be the most valuable load weighing at mostW  w
that the thief can take from then1
original items plusw_j  w
pounds of item j (the remains of itemj
).
 consider that if we remove a weight
 As the Fig 16.2 in CRLS demonstrates, although the problems are similar, we can solve the fractional knapsack problem by a greedy strategy, but we cannot solve the 01 problem by such a strategy.
An example,
2 Intuition of the greedy choice

To solve the fractional problem, we first compute the value per pound
v_i = b_i / w_i
for each itemi
. 
Obeying a greedy strategy, the thief begins by taking as much as possible of the item with the greatest value per pound.

If the supply (
w_i  q_i
whereq_i
is the quantity that we took from the total amount of itemi
) of that item is exhausted and we can still carry more (weightLimit > currWeight
), we take as much as possible of the item with the next greatest value per pound, and so forth, until we reach our weight limit. 
Therefore, our goal lies in:
(x_i
here is the same concept as theq_i
above)
3. Pseudocode
struct Item {
double benifit;
double weight;
} item;
items := Array[item]
Algorithm FractionalKnapsack(items, weightLimit):
new values[1 ~ n]
new quantities[1 ~ n]
For i := 1 to n do
quantities[i] := 0
values[i] := items[i].benifits / items[i].weight
Sort(items, key=values, desc) // or using a maxheap
currWeight := 0
For j := 0 to n do
if currWeight < weightLimit then
availableLoad := weightLimits  currWeight
quantities[j] := Min(items[j].weight, availableLoad) > make greed choice
currWeight += quantities[j]
else
break
total := Reduce(quantities)
return total
4. Time Complexity

We could either represent the
items
set as a priority queue (with the highest priority for the highest benefit per weight value) using a maxheap, or 
we can sort the
items
inO(nlogn)
time anyway; 
T(n) = O(n) + O(nlgn) + O(n) ∈ O(nlgn)
Leave a comment