Java Reference
In-Depth Information
For this well-designed example, we have
c
∗
= 2 but
c
G
= log
2
, showing the
upper bound of
O
(log
n
) approximation factor. Note that this approximation
factor depends on
n
, the problem size. Remember that the 0-1 knapsack the
same greedy heuristic yielded a
constant
approximation factor.
Figure 9.5
A bad instance for which the greedy set cover heuristic poorly
behaves. This generic construction yields an approximation factor of
O
(log
n
)
Although that we have noticed that the greedy set cover heuristic yields only
a
O
(log
n
) competitive ratio, it is striking to know that no other algorithm can
beat this simple heuristic provided that some problem complexity property
holds in computer science, related to the famous
P
=
NP
? conjecture.
9.4 Dynamic programming: Optimal solution
for the 0-1 knapsack problem
To close this chapter on programming various combinatorial optimization
algorithms in Java, we will revisit the 0-1 knapsack problem. This time, we are
looking for an
exact solution
(not the constant factor approximation solution
we obtained from the greedy algorithm) without performing the prohibitive
exhaustive search. The conceptual idea to make this possible is to come up
with a mathematical
recurrence relation
that can then be used to
incrementally
build a bi-dimensional table from which we can retrieve the solution. Loosely
speaking, the 2D table will store
3
intermediate solutions. Consider
u
(
i, j
)the
utility function defined by selecting items among the first
i
objects with
an overall weight constraint of
j
units. The recurrence relation is found as
follows:
-
u
(1
,w
)=0if
w<W
1
(not enough room to put
O
1
in the sack) and
u
(1
,w
)=
U
1
whenever
w
W
1
.
3
Eventually, only a subset of the table may be computed by a process called
memoization
in dynamic programming.
≥
Search WWH ::
Custom Search