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 Chapter 1