TADM2E 1.5

From Algorithm Wiki
Revision as of 16:08, 21 January 2019 by Landron (talk | contribs) (Well defining counterexample)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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 ...