|
|
| 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>
| + | Back to [[Chapter 2]] |
| − | <p>
| |
| − | <math>S = \{4, 3, 2\}</math>
| |
| − | <br/>
| |
| − | <math>T = 5</math>
| |
| − | </p>
| |
| − | ----
| |
| − | <p>Another counterexample:</p>
| |
| − | 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)
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | ! 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)
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | ! 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
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | ! Item added
| |
| − | ! Subset of <math>S</math>
| |
| − | ! Sum
| |
| − | |-
| |
| − | | 10
| |
| − | | <math>\{10\}</math>
| |
| − | | 10 < 11
| |
| − | |-
| |
| − | | 9
| |
| − | | <math>\{9, 10\}</math>
| |
| − | | 19 > 11
| |
| − | |}
| |
| − | | |
| − | Back to [[Chapter 1]] | |
