Java Reference
In-Depth Information
only for a knapsack of size k
1
). We then fill in the succeeding rows from i = 2 to
n, left to right, as follows.
if P(n 1;K) has a solution,
then P(n;K) has a solution
else if P(n 1;K k
n
) has a solution
then P(n;K) has a solution
else P(n;K) has no solution.
In other words, a new slot in the array gets its solution by looking at two slots in
the preceding row. Since filling each slot in the array takes constant time, the total
cost of the algorithm is (nK).
Example16.3
Solve the Knapsack Problem for K = 10 and five items
with sizes 9, 2, 7, 4, 1. We do this by building the following array.
0 1 2 3 4 5 6 7 8 9 10
k
1
= 9 O I
k
2
= 2 O I O
k
3
= 7 O O I I=O
k
4
= 4 O O I I O O
k
5
= 1 O I O I O I O I=O I
O
I
Key:
-: No solution for P(i;k).
O: Solution(s) for P(i;k) with i omitted.
I: Solution(s) for P(i;k) with i included.
I/O: Solutions for P(i;k) with i included AND omitted.
For example, P(3; 9) stores value I/O. It contains O because P(2; 9)
has a solution. It contains I because P(2; 2) = P(2; 9 7) has a solution.
Since P(5; 10) is marked with an I, it has a solution. We can determine
what that solution actually is by recognizing that it includes the 5th item
(of size 1), which then leads us to look at the solution for P(4; 9). This
in turn has a solution that omits the 4th item, leading us to P(3; 9). At
this point, we can either use the third item or not. We can find a solution
by taking one branch. We can find all solutions by following all branches
when there is a choice.
16.1.2 All-Pairs Shortest Paths
We next consider the problem of finding the shortest distance between all pairs of
vertices in the graph, called the all-pairs shortest-paths problem. To be precise,
for every u; v 2 V, calculate d(u, v).
