TADM2E 1.5
From Algorithm Wiki
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 |
