0/1 – KNAPSACK
We are given n objects and a knapsack. Each object i has a positive weight wi and a
positive value Vi. The knapsack can carry a weight not exceeding W. Fill the knapsack so
that the value of objects in the knapsack is optimized.
A solution to the knapsack problem can be obtained by making a sequence of decisions
on the variables x1, x2, . . . . , xn. A decision on variable xi involves determining which of
the values 0 or 1 is to be assigned to it. Let us assume that
decisions on the xi are made in the order xn, xn-1, . . . .x1. Following a decision on x n, we
may be in one of two possible states:
the capacity remaining in m – wn and a profit of pn has accrued. It is clear that the
remaining decisions xn-1, . . . , x1 must be optimal with respect to the problem state
resulting from the decision on xn. Otherwise, xn,. . . . , x1 will not be optimal. Hence, the
principal of optimality holds.
Fn (m) = max {fn-1 (m), fn-1 (m - wn) + pn} ------------------------------------ 1
For arbitrary fi (y), i > 0, this equation generalizes to:
Fi (y) = max {fi-1 (y), fi-1 (y - wi) + pi} --------------------------------------- 2
Equation-2 can be solved for fn (m) by beginning with the knowledge fo (y) = 0 for all y
and fi (y) = - ∞, y < 0. Then f1, f2, . . . fn can be successively computed using equation–2.
When the wi’s are integer, we need to compute fi (y) for integer y, 0 ≤ y ≤ m. Since f i (y)
= - ∞ for y < 0, these function values need not be computed explicitly. Since each f i can
be computed from fi - 1 in Θ (m) time, it takes Θ (m n) time to compute fn. When the wi’s
are real numbers, fi (y) is needed for real numbers y such that 0≤ y ≤ m. So, f i cannot be
explicitly computed for all y in this range. Even when the w i’s are integer, the explicit Θ
(m n) computation of fn may not be the most efficient computation. So, we explore an
alternative method for both cases.
The fi (y) is an ascending step function; i.e., there are a finite number of y’s, 0 = y1
< y2 < . . . . < yk, such that fi (y1) < fi (y2) < . . . . . < fi (yk); fi (y) = - ∞ , y < y1;
fi (y) = f (yk), y > yk; and fi (y) = fi (yj), yj < y < yj+1. So, we need to compute only f i (yj), 1
≤ j ≤ k. We use the ordered set Si = {(f (yj), yj) | 1 ≤ j ≤ k} to represent fi (y). Each number
of Si is a pair (P, W), where P = fi (yj) and W = yj.
Notice that S0 = {(0, 0)}. We can compute Si+1 from Si by first computing:
Si1 = {(P, W) | (P – pi, W – wi) ϵ Si}
Now, Si+1 can be computed by merging the pairs in Si and Si1 together.
Note that if Si+1 contains two pairs (Pj, Wj) and (Pk, Wk) with the property that Pj ≤ Pk and
Wj ≥ Wk, then the pair (Pj, Wj) can be discarded because of equation-2. Discarding or
purging rules such as this one are also known as dominance rules. Dominated tuples get
purged. In the above, (Pk, Wk) dominates (Pj, Wj).
Example 1:
Consider the knapsack instance n = 3, (w1, w2, w3) = (2, 3, 4), (P1, P2, P3) = (1, 2, 5) and
M = 6.
Solution:
Initially, fo (x) = 0, for all x and fi (x) = - ∞ if x < 0.
Fn (M) = max {fn-1 (M), fn-1 (M - wn) + pn}
F3 (6) = max (f2 (6), f2 (6 – 4) + 5} = max {f2 (6), f2 (2) + 5}
F2 (6) = max (f1 (6), f1 (6 – 3) + 2} = max {f1 (6), f1 (3) + 2}
F1 (6) = max (f0 (6), f0 (6 – 2) + 1} = max {0, 0 + 1} = 1
F1 (3) = max (f0 (3), f0 (3 – 2) + 1} = max {0, 0 + 1} = 1
Therefore, F2 (6) = max (1, 1 + 2} = 3
F2 (2) = max (f1 (2), f1 (2 – 3) + 2} = max {f1 (2), - ∞ + 2}
F1 (2) = max (f0 (2), f0 (2 – 2) + 1} = max {0, 0 + 1} = 1
F2 (2) = max {1, - ∞ + 2} = 1
Finally, f3 (6) = max {3, 1 + 5} = 6
