Difference between revisions of "TADM2E 1.5"

Latest revision as of 16:08, 21 January 2019

First-fit algorithm counterexample:

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

Best-fit algorithm counterexample:

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

Largest to smallest algorithm counterexample:

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

Another counterexample:

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

Using first-fit algorithm (left to right)

Using best-fit algorithm (smallest to largest)

Using largest to smallest

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

@@ Line 21: / Line 21: @@
 ----
 <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.
+If <math>S = \{1, 2, 5, 9, 10\}</math> and <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.