Problém dvou loupežníků

Problém dvou loupežníků je v matematické informatice NP-úplný problém, jak rozdělit kořist (oceněné věci) mezi dva loupežníky tak, aby lup byl rozdělen rovným dílem (součet hodnot věcí v jedné skupině byl roven součtu hodnot věcí v druhé skupině).

Praktický příkladEditovat

Mějme zadáno   čísel. Otázka zní: Lze zadaná čísla rozdělit do dvou skupin tak, aby součet čísel v obou skupinách byl stejný (tj. aby se dva loupežníci mohli spravedlivě rozdělit o kořist   oceněných věcí)?

Pokud je čísel málo, řešení lze nalézt celkem snadno — pomocí prozkoumání všech možných rozdělení čísel do dvou skupin. Počet možných rozdělení do dvou skupin však roste exponenciálně, a pokud bychom si vzali např.  , pak stavový prostor v rozumném čase neprojdeme ani na výkonném počítači.

Související článkyEditovat