# Difference between revisions of "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