TADM2E 1.5

From Algorithm Wiki
Revision as of 18:13, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

<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 ...