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.

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

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})$

[editovat] 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.

[editovat] Optimalizační problém batohu

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ší.

[editovat] Související články

Dynamické programování

Tento kryptografický článek je příliš stručný nebo neobsahuje důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte.

Problém batohu v jiných jazycích: Deutsch, English, Español, فارسی, Français, Italiano, 日本語, 한국어, Nederlands, Polski, Português, Русский, Svenska, Türkçe, Tiếng Việt, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Probl%C3%A9m_batohu“
Stránka byla naposledy upravena v Stránka byla naposledy editována 9. 7. 2008 v 15:24.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).