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

Cross check:38 remaining weight 0
We interpret the procedure extracting the result by manually running procedure
InterpretArray() in Table 9.2.
9.5 Optimization paradigms: Overview of
complexity analysis
In this chapter, we have presented four basic combinatorial optimization
problems:
1. plain knapsack filling problem,
2. eight queen puzzle,
3. set cover problem,
4. maximal utility knapsack problem.
For solving these tasks, we have considered heuristics for finding either an exact
or an approximation of the optimal solution. The properties of these generic
algorithms are quickly summarized below:
Exhaustive search. Explore the full configuration space using a simple recursive
procedure, which usually requires exponential time for enumerating all
potential solutions.
Backtracking. Structure the space of a potential solution and incrementally
build the solution until we reach a dead end. Then backtrack by changing
the configuration of previous states. Complexity does not asymptotically
change; it is still exponential in the worst case.
Greedy algorithm. Construct the solution iteratively by choosing at each step
the current best set. Greedy heuristics are polynomial in the input size.
The greedy SCP algorithm takes cubic time.
Dynamic programing. Build a table from a recurrence relation and extract the
solution by reading the table backward. The complexity is polynomial (that
is, requires O ( Wn ) time and space) if we consider W as a parameter.
Dynamic programming faces limitations when W is too large. We then
prefer to solve it using the constant 2-approximation greedy algorithm.
Finally, let us stress that even if the greedy heuristic seems a bit naive, computer
scientists do not have better algorithms on hand. Finding a better algorithm
is actually one of the hottest, if not the most challenging, open problem in