Obsah:
Definícia - Čo znamená problém Knapsack?
Problém s batohom je problém s optimalizáciou, ktorý sa používa na ilustráciu problému a riešenia. Názov odvodzuje zo scenára, v ktorom je obmedzený počet položiek, ktoré je možné umiestniť do batohu s pevnou veľkosťou. Vzhľadom na množinu predmetov s konkrétnymi hmotnosťami a hodnotami je cieľom získať čo najviac hodnoty do batohu vzhľadom na obmedzenie hmotnosti batohu.
Techopedia vysvetľuje problém s batohom
Problém batohu je príkladom problému kombinovanej optimalizácie, témy z matematiky a informatiky o hľadaní optimálneho objektu zo súboru objektov. Toto je problém, ktorý sa študoval už viac ako storočie a je to bežne používaný príklad problému v kombinatorickej optimalizácii, kde je potrebný optimálny objekt alebo konečné riešenie, kde nie je možné dôkladné vyhľadávanie. Problém možno nájsť v skutočných scenároch, ako je rozdelenie zdrojov vo finančných obmedzeniach alebo dokonca pri výbere investícií a portfólií. Nachádza sa tiež v oblastiach ako je aplikovaná matematika, teória zložitosti, kryptografia, kombinatorika a informatika. Je to jednoducho najdôležitejší problém v logistike.
Pri problémoch s batohom majú dané položky minimálne dva atribúty - hodnotu položky, ktorá ovplyvňuje jej dôležitosť, a jej hmotnosť alebo objem, čo je jej limitujúcim aspektom. Keďže nie je možné dôkladné vyhľadávanie, je možné problémy rozdeliť na menšie čiastkové problémy a spustiť ich rekurzívne. Toto sa nazýva optimálna podštruktúra. Toto riešenie sa týka vždy len jednej položky a aktuálnej hmotnosti, ktorá je v batohu stále k dispozícii. Riešiteľ problému sa musí iba rozhodnúť, či vezme položku alebo nie na základe váhy, ktorú je stále možné akceptovať. Ak sa však jedná o program, opätovné výpočty nie sú nezávislé a spôsobili by problémy. Tu sa dajú použiť techniky dynamického programovania. Riešenia každého čiastkového problému sa ukladajú tak, aby sa výpočet musel uskutočniť iba raz.
