1.5

From The Algorithm Design Manual Solution Wiki
Revision as of 20:10, 31 August 2020 by Algowikiadmin (talk | contribs) (Created page with "<p>First-fit algorithm counterexample:</p> <p> <math>S = \{1, 2, 3\}</math> <br/> <math>T = 5</math> </p> <p>Best-fit algorithm counterexample:</p> <p> <math>S = \{1, 2, 3\}<...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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