# Difference between revisions of "TADM2E 1.5"

From Algorithm Wiki

(Recovering wiki) |
(Well defining counterexample) |
||

Line 21: | Line 21: | ||

---- | ---- | ||

<p>Another counterexample:</p> | <p>Another counterexample:</p> | ||

− | If <math> | + | 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. |

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