Difference between revisions of "TADM2E 1.5"
From Algorithm Wiki
(Recovering wiki) |
(Well defining counterexample) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | <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 | + | 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. |
Using first-fit algorithm (left to right) | Using first-fit algorithm (left to right) | ||
| − | {| class= | + | {| class="wikitable" |
|- | |- | ||
! Item added | ! Item added | ||
| − | ! Subset of | + | ! Subset of <math>S</math> |
! Sum | ! Sum | ||
|- | |- | ||
| 1 | | 1 | ||
| − | | | + | | <math>\{1\}</math> |
| − | | 1 | + | | 1 < 11 |
|- | |- | ||
| 2 | | 2 | ||
| − | | | + | | <math>\{1, 2\}</math> |
| − | | 3 | + | | 3 < 11 |
|- | |- | ||
| 5 | | 5 | ||
| − | | | + | | <math>\{1, 2, 5\}</math> |
| − | | 8 | + | | 8 < 11 |
|- | |- | ||
| 9 | | 9 | ||
| − | | | + | | <math>\{1, 2, 5, 9\}</math> |
| − | | 17 | + | | 17 > 11 |
|} | |} | ||
Using best-fit algorithm (smallest to largest) | Using best-fit algorithm (smallest to largest) | ||
| − | {| class= | + | {| class="wikitable" |
|- | |- | ||
! Item added | ! Item added | ||
| − | ! Subset of | + | ! Subset of <math>S</math> |
! Sum | ! Sum | ||
|- | |- | ||
| 1 | | 1 | ||
| − | | | + | | <math>\{1\}</math> |
| − | | 1 | + | | 1 < 11 |
|- | |- | ||
| 2 | | 2 | ||
| − | | | + | | <math>\{1, 2\}</math> |
| − | | 3 | + | | 3 < 11 |
|- | |- | ||
| 5 | | 5 | ||
| − | | | + | | <math>\{1, 2, 5\}</math> |
| − | | 8 | + | | 8 < 11 |
|- | |- | ||
| 9 | | 9 | ||
| − | | | + | | <math>\{1, 2, 5, 9\}</math> |
| − | | 17 | + | | 17 > 11 |
|} | |} | ||
Using largest to smallest | Using largest to smallest | ||
| − | {| class= | + | {| class="wikitable" |
|- | |- | ||
! Item added | ! Item added | ||
| − | ! Subset of | + | ! Subset of <math>S</math> |
! Sum | ! Sum | ||
|- | |- | ||
| 10 | | 10 | ||
| − | | | + | | <math>\{10\}</math> |
| − | | 10 | + | | 10 < 11 |
|- | |- | ||
| 9 | | 9 | ||
| − | | | + | | <math>\{9, 10\}</math> |
| − | | 19 | + | | 19 > 11 |
|} | |} | ||
[[introduction-TADM2E|Back to ''Introduction ...'']] | [[introduction-TADM2E|Back to ''Introduction ...'']] | ||
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)
| Item added | Subset of $ S $ | Sum |
|---|---|---|
| 1 | $ \{1\} $ | 1 < 11 |
| 2 | $ \{1, 2\} $ | 3 < 11 |
| 5 | $ \{1, 2, 5\} $ | 8 < 11 |
| 9 | $ \{1, 2, 5, 9\} $ | 17 > 11 |
Using best-fit algorithm (smallest to largest)
| Item added | Subset of $ S $ | Sum |
|---|---|---|
| 1 | $ \{1\} $ | 1 < 11 |
| 2 | $ \{1, 2\} $ | 3 < 11 |
| 5 | $ \{1, 2, 5\} $ | 8 < 11 |
| 9 | $ \{1, 2, 5, 9\} $ | 17 > 11 |
Using largest to smallest
| Item added | Subset of $ S $ | Sum |
|---|---|---|
| 10 | $ \{10\} $ | 10 < 11 |
| 9 | $ \{9, 10\} $ | 19 > 11 |
