1.5

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

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