1.5

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

First-fit algorithm counterexample:


Best-fit algorithm counterexample:


Largest to smallest algorithm counterexample:



Another counterexample:

If and , the solution would be the subset or which none of the algorithms found.


Using first-fit algorithm (left to right)

Item added Subset of Sum
1 1 < 11
2 3 < 11
5 8 < 11
9 17 > 11


Using best-fit algorithm (smallest to largest)

Item added Subset of Sum
1 1 < 11
2 3 < 11
5 8 < 11
9 17 > 11


Using largest to smallest

Item added Subset of Sum
10 10 < 11
9 19 > 11

Back to Chapter 1