Problém batohu

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Problém batohu

Problém batohu je NP-úplný problém kombinatorické optimalizace.

Nechť je dáno n závaží, z nichž každé má jednoznačně určenou hmotnost. Některá z nich vybereme, a dáme je do uzavřeného batohu, který je neprůhledný (a který má sám nulovou hmotnost). Potom batoh zvážíme a určíme celkovou hmotnost, ze které se pokusíme určit, která závaží jsou uvnitř batohu.

Formální znění problému[editovat | editovat zdroj]

Máme číslo M, vektor \vec x, množinu A. Pokoušíme se řešit rovnici (určit vektor \vec x), tak aby platilo: M = x_{1}a_{1} + x_{2}a_{2} + \cdots +x_{n}a_{n} | a_{i}\in A, \vec x = (x_{1} \cdots x_{n})

Poznámky[editovat | editovat zdroj]

Řešení nemusí existovat, nebo nemusí být jednoznačné. Problém se využívá v konstrukci některých algoritmů asymetrické kryptografie.

Optimalizační problém batohu[editovat | editovat zdroj]

Máme batoh, který má pevně danou nosnost. Máme množinu věcí, které mají svou cenu a váhu. Úkolem je dát do batohu některé věci tak, aby součet vah nepřekročil nosnost a přitom součet cen byl co největší.

Související články[editovat | editovat zdroj]