Knapsack Variants

Overview

The knapsack problem models resource allocation with a capacity constraint. Given $n$ items, each with weight $w_i$ and value $v_i$, and a knapsack with capacity $W$, select items to maximise total value without exceeding capacity. Two variants are considered: the 0/1 knapsack (items cannot be split) and the fractional knapsack (items can be split arbitrarily).

The 0/1 variant requires dynamic programming; the fractional variant is solved greedily. Understanding why greedy works for one and not the other is a central lesson in algorithm design.

0/1 Knapsack (DP)

Each item is either taken in full or left behind. The DP recurrence:

Let $\text{OPT}(i, w)$ be the maximum value achievable using items $1$ through $i$ with capacity $w$:

$\text{OPT}(i, w) = \begin{cases} 0 & \text{if } i = 0 \text{ or } w = 0 \\[4pt] \text{OPT}(i-1, w) & \text{if } w_i > w \\[4pt] \max\big(\text{OPT}(i-1, w),\; v_i + \text{OPT}(i-1, w - w_i)\big) & \text{if } w_i \le w \end{cases}$

The two choices at each step: exclude item $i$ (value unchanged, capacity unchanged), or include item $i$ (gain $v_i$, consume $w_i$ of capacity).

Example

$W = 7$, items: $(w_1=3, v_1=4)$, $(w_2=4, v_2=5)$, $(w_3=2, v_3=3)$.

DP table (rows = items considered, columns = capacity):

	$w=0$	1	2	3	4	5	6	7
$i=0$	0	0	0	0	0	0	0	0
$i=1$	0	0	0	4	4	4	4	4
$i=2$	0	0	0	4	5	5	5	9
$i=3$	0	0	3	4	5	7	8	9

Optimal: take items 1 and 3, total weight $3+2=5 \le 7$, total value $4+3=7$.

Complexity

Time: $\Theta(nW)$. Space: $\Theta(nW)$ or $\Theta(W)$ with space optimisation (only previous row needed). This is pseudo-polynomial: polynomial in the numeric value $W$, but not in the input size $\log W$. If $W$ is large, the algorithm is impractical.

Fractional Knapsack (Greedy)

Items can be split arbitrarily. The greedy strategy:

1. Compute value per unit weight: $v_i / w_i$ for each item.
2. Sort items by this ratio (descending).
3. Take as much as possible of the highest-ratio item; if capacity remains, move to the next.

sort items by v_i / w_i descending
total = 0
for each item (sorted):
    if W >= w_i:
        take all of item; W -= w_i; total += v_i
    else:
        take fraction W / w_i; total += (W / w_i) * v_i; break

Time: $\Theta(n \log n)$ for sorting, $\Theta(n)$ for selection.

Example (Same Items)

$(w_1=3, v_1=4, v/w = 1.33)$, $(w_2=4, v_2=5, v/w = 1.25)$, $(w_3=2, v_3=3, v/w = 1.5)$. Capacity $W = 7$.

1. Item 3: ratio 1.5, take all → value 3, capacity left 5.
2. Item 1: ratio 1.33, take all → value 4, capacity left 2.
3. Item 2: ratio 1.25, take $2/4 = 0.5$ → value 2.5.

Total: $3 + 4 + 2.5 = 9.5$. (Compare 0/1 optimum: 7.)

Why Greedy Works for Fractional

The proof is straightforward: if any optimal solution does not fill capacity with the highest-ratio item first, we can exchange a lower-ratio item for an equal weight of the higher-ratio item and increase total value. So an optimal solution must greedily take the highest-ratio items.

Why Greedy Fails for 0/1

The all-or-nothing constraint is the culprit. A high-ratio item might be so heavy that taking it leaves capacity that can only be filled with low-value items, whereas skipping it allows two medium-ratio items that together yield more value. The greedy algorithm cannot “regret” the choice later — it has no lookahead.

In the earlier example, a greedy-by-ratio approach for 0/1 would take item 3 (ratio 1.5), then item 1 (ratio 1.33), resulting in total weight 5 and value 7. It cannot fit item 2 (weight 4, would exceed 7). The DP found the same optimum here, but a different example can break greedy:

Items: $(1, 2, \text{ratio } 2.0)$, $(2, 3, \text{ratio } 1.5)$, $W = 2$. Greedy takes item 1 (value 2, weight 1), leaving capacity for nothing else. Optimal: take item 2 (value 3). Greedy fails.

Comparison

Property	0/1 Knapsack	Fractional Knapsack
Can split items?	No	Yes
Solution method	DP	Greedy
Time	$\Theta(nW)$ (pseudo-polynomial)	$\Theta(n \log n)$
Greedy works?	No	Yes
Optimal substructure	Yes	Yes
Greedy choice property	No	Yes

Summary

Property	Value
0/1 knapsack	DP, $\Theta(nW)$ pseudo-polynomial
Fractional knapsack	Greedy by value/weight ratio, $\Theta(n \log n)$
Why greedy fails for 0/1	All-or-nothing constraint blocks lookahead
Why greedy works for fractional	Can always exchange lower-ratio for higher-ratio material
Space optimisation	0/1 can be $\Theta(W)$ instead of $\Theta(nW)$