Subset Sum
aus Wikipedia, der freien Enzyklopädie
Subset Sum ("Untermengensumme") ist ein berühmtes Problem der Informatik und des Operations Research. Es ist ein spezielles Rucksackproblem.
[Bearbeiten] Problembeschreibung
Gegeben sei eine Menge von Ganzzahlen I = {w1,w2,...,wn}. Gesucht ist eine Untermenge, deren Summe maximal, aber nicht größer als c ist.
Formal: 
so dass 
mit 
Das Problem ist NP-schwer und somit nicht ohne weiteres lösbar. Es kann mit dem Verfahren Branch and Bound gelöst werden.
Das verwandte Problem, dass c exakt erreicht werden muss, ist NP-vollständig. Algorithmen, die das Ursprungsproblem in schneller Zeit lösen können, gehen davon aus, dass es exakt gelöst werden kann.
[Bearbeiten] Literatur
- Soma, Nei Y. Toth, Paolo: An exact algorithm for the subset sum problem. European Journal of Operational Research 136 S. 57-66
