Problém batohu

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). +more 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 \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

Ř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. +more Ú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í

Kategorie:NP-úplné problémy Kategorie:Kryptografie