# TADM2E 1.5

From Algorithm Wiki

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 |