1.5

First-fit algorithm counterexample:

[math]\displaystyle{ S = \{1, 2, 3\} }[/math]
[math]\displaystyle{ T = 5 }[/math]

Best-fit algorithm counterexample:

[math]\displaystyle{ S = \{1, 2, 3\} }[/math]
[math]\displaystyle{ T = 5 }[/math]

Largest to smallest algorithm counterexample:

[math]\displaystyle{ S = \{4, 3, 2\} }[/math]
[math]\displaystyle{ T = 5 }[/math]

---

Another counterexample:

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

Using first-fit algorithm (left to right)

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

Using best-fit algorithm (smallest to largest)

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

Using largest to smallest

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

Back to Chapter 1