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

Máme číslo M, vektor $\stackrel{\to <!--\; \to \; -->}{x}$, množinu A. Pokoušíme se řešit rovnici (určit vektor $\stackrel{\to <!--\; \to \; -->}{x}$), tak aby platilo: $M=x_1{a}_1+x_2{a}_2+\cdots <!--\; \cdots \; -->+x_n{a}_n|a_i\in <!--\; \in \; -->A,\stackrel{\to <!--\; \to \; -->}{x}=(x_1\cdots <!--\; \cdots \; -->x_n)$

Poznámky

Ř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

Máme batoh, který má pevně danou nosnost. Máme množinu věcí, které mají svoji cenu a hmotnost. Ú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

• Dynamické programování

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.