TADM2E 1.5

First-fit algorithm counterexample:

$ S = \{1, 2, 3\} $
$ T = 5 $

Best-fit algorithm counterexample:

$ S = \{1, 2, 3\} $
$ T = 5 $

Largest to smallest algorithm counterexample:

$ S = \{4, 3, 2\} $
$ T = 5 $

---

Another counterexample:

If $ S = \{1, 2, 5, 9, 10\} $ and $ T=11 $, the solution would be the subset $ \{2, 9\} $ or $ \{1, 10\} $ which none of the algorithms found.

Using first-fit algorithm (left to right)

Item added	Subset of $ S $	Sum
1	$ \{1\} $	1 < 11
2	$ \{1, 2\} $	3 < 11
5	$ \{1, 2, 5\} $	8 < 11
9	$ \{1, 2, 5, 9\} $	17 > 11

Using best-fit algorithm (smallest to largest)

Item added	Subset of $ S $	Sum
1	$ \{1\} $	1 < 11
2	$ \{1, 2\} $	3 < 11
5	$ \{1, 2, 5\} $	8 < 11
9	$ \{1, 2, 5, 9\} $	17 > 11

Using largest to smallest

Item added	Subset of $ S $	Sum
10	$ \{10\} $	10 < 11
9	$ \{9, 10\} $	19 > 11

Back to Introduction ...