TADM2E 1.5

<p>First-fit algorithm counterexample:</p> <p> <math>S = \{1, 2, 3\}</math> <br/> <math>T = 5</math> </p>

<p>Best-fit algorithm counterexample:</p> <p> <math>S = \{1, 2, 3\}</math> <br/> <math>T = 5</math> </p>

<p>Largest to smallest algorithm counterexample:</p> <p> <math>S = \{4, 3, 2\}</math> <br/> <math>T = 5</math> </p>

---

<p>Another counterexample:</p> If <math>t=11</math>, the solution would be the subset <math>\{2, 9\}</math> or <math>\{1, 10\}</math> which none of the algorithms found.

Using first-fit algorithm (left to right)

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

Using best-fit algorithm (smallest to largest)

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

Using largest to smallest

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

Back to Introduction ...