Student World

Takže, ač neradi, nějaké zboží budeme muset nechat na místě. Jak to udělat, abychom přenesli zboží v co nejvyšší hodnotě?

Dejme tomu, že nosnost batohu je 6 kg. Máme 4 předměty s následujícími vahami a cenami:

3…9

3…9

4…14

5…16

Problém batohu se někdy uvádí jako příklad úlohy, na níž nelze aplikovat tzv. hladový princip (princip horolezce). Tato metoda spočívá v tom, že v každém kroku uděláme „lokálně optimální“ volbu, která nám vzhledem k zadání dá po skočení „kola“ nejlepší pozici do dalšího průběhu. V batohové úloze by to znamenalo, že nejprve vybereme nejcennější předmět, který se ještě do batohu vejde, a v dalším kroku postupujeme stejně. To by znamenalo, že bychom vzali předmět č. 4, s hmotností 5 a cenou 16 – a do batohu by se nám už nic nevešlo. Když naložíme dva první předměty, přeneseme však celkem zboží v hodnotě 18.

Nelze použít ani modifikovaný postup horolezce, kdy u každého předmětu spočítáme poměr cena/váha a pak postupujeme od předmětu relativně nejcennějšího. V tomto případě by byl „nejcennější“ předmět číslo 3, naložili bychom ho do batohu – a zase konec, dokonce ještě s horším výsledkem než v prvním případě.

Úloha o batohu je každopádně řešitelná obtížně, protože patří mezi NP úplné problémy. K dispozici nicméně máme několik heuristických postupů, například tzv. prořezávání stromu. Napadá vás, jak postup řešit pro ještě jednoduché úlohy, kde již nelze použít „výčet“ možností v hlavě?

Zdroj: Jiří Vaníček a kolektiv: Teoretické základy informatiky, Kernberg Publishing, Praha 2007

O knize na stránkách vydavatele

autor Pavel Houser