Porovnání metod řešení variant problému batohu

Abstract

Práce se zabývá kombinatorickou úlohou problému batohu, ve které je cílem vybrat optimální podmnožinu ze zadaných předmětů, tak aby byl součet jejich hodnot maximální a nepřekročily stanovené podmínky omezení. Úlohu lze aplikovat na velké množství situací v reálném světě, proto má v dnešní době mnoho variant a existuje více přístupů k řešení. Nejznámější varianty a metody řešení jsou v práci popsány, některé z nich jsou pak implementovány a otestovány. Praktická část popisuje způsob implementace algoritmů a testování. To probíhalo na dvou variantách problému batohu a na různých velikostech zadané množiny předmětů. Na základě naměřených výsledků jsou vyvozeny závěry a formulována doporučení různých metod řešení variant problému batohu a naznačen možný budoucí vývoj optimalizačních metod.