Paradigms for Optimization Problems - A Concise and Practical Introduction to Programming Algorithms in Java - page 192

circumvent this inherent diculty, we design faster algorithms that only report
approximate solutions instead of too-costly exact solutions. We end up by
presenting the most celebrated heuristic for getting guaranteed approximate
solutions: the greedy strategy . We exemplify the greedy methodology on
two problems: the knapsack and set cover problems,, which emphasize the
important fact that the same paradigm applied to these two distinct problems
yields different approximation ratios .

9.2 Exhaustive search

The paradigm of exhaustive search consists merely in exploring the full
configuration space by enumerating one by one all possible configurations,
and retaining the best one: the optimal solution. Eventually several optimal
solutions may exist. Exhaustive search is clearly the brute-force paradigm that
yields straightforward but often naive algorithms for solving a task at hand.
Let us explain its implementation by taking a case study: the knapsack.

9.2.1 Filling a knapsack

Consider a set of n objects O 1 , ..., O n with corresponding weights W 1 , ..., W n .

Suppose that object O i weights W i , where W i is measured in kilogram units
for all i

O

. Given a knapsack that can carry an overall weight W ,we
are asked to enumerate all possible choices for fully filling this sack. Objects
can be chosen only once; There is no allowed multiplicity of objects. In other
words, we are asked to find all possible object selections that yield an overall
weight of exactly W kilograms. W is called the capacity of the bag.
We can formulate this problem as computing
I ∗ = I

∈{ 1 , ..., n }

W i = W , ⊆{ 1 , ..., n } ,

i∈I

where I denote a subset of indices representing the object selection. That is,
find all index subsets so that their corresponding object weights sum up to the
knapsack capacity.
If we were given a priori a fixed number of objects n , we could simply check all
possible choices of selecting or not selecting objects by writing a sequence of
nested loops. For example, consider completely filling a knapsack of capacity
W = 11 by selecting objects in a set of n = 5 objects with the following