Problém batohu
Z Wikipedie, otevřené encyklopedie
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 
, množinu A. Pokoušíme se řešit rovnici (určit vektor ),tak aby platilo 
[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ší.
