# 1.5

First-fit algorithm counterexample:

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

Best-fit algorithm counterexample:

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

Largest to smallest algorithm counterexample:

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

Another counterexample:

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

Using first-fit algorithm (left to right)

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

Using best-fit algorithm (smallest to largest)

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

Using largest to smallest

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

Back to Chapter 1