Teilsummenproblem

Das Teilsummenproblem (auch Untermengensummenproblem, engl. subset sum problem) ist ein berühmtes Problem der Informatik und des Operations Research. Es ist ein spezielles Rucksackproblem.

Gegeben sei eine Menge von ganzen Zahlen I = { w 1 , w 2 , … , w n } {\displaystyle I=\{w_{1},w_{2},\dotsc ,w_{n}\}} . Gesucht ist eine Untermenge, deren Elementsumme maximal, aber nicht größer als eine gegebene obere Schranke c {\displaystyle c} ist (oft ist auch gefragt, die Schranke c {\displaystyle c} exakt zu erreichen).

Formal: Gesucht sind x 1 , … , x n ∈ { 0 , 1 } {\displaystyle x_{1},\dotsc ,x_{n}\in \{0,1\}} , die ∑ j = 1 n w j x j {\displaystyle \sum _{j=1}^{n}{w_{j}x_{j}}} maximieren unter der Nebenbedingung ∑ j = 1 n w j x j ≤ c {\displaystyle \sum _{j=1}^{n}{w_{j}x_{j}}\leq c} .

Das Problem ist NP-vollständig und somit vermutlich nicht effizient lösbar. Es kann mit der Branch-and-Bound-Methode gelöst werden.

Der Beweis der NP-Schwere erfolgt durch eine Reduktion von 3-SAT. Für eine gegebene Klauselmenge C 1 ∧ C 2 ∧ … C m {\displaystyle C_{1}\wedge C_{2}\wedge \ldots C_{m}} mit den Variablen x 1 … x n {\displaystyle x_{1}\ldots x_{n}} werden die Dezimalzahlen w 1 … w 2 n + 2 m {\displaystyle w_{1}\ldots w_{2n+2m}} sowie die Schranke c {\displaystyle c} anhand einer Tabelle konstruiert. Es wird vorausgesetzt, dass keine Klauseln vorhanden sind, die x i {\displaystyle x_{i}} und x i ¯ {\displaystyle {\overline {x_{i}}}} gleichzeitig enthalten; dies ist keine Einschränkung, da eine solche Klausel immer erfüllt wäre und somit weggelassen werden kann, ohne den Sinn zu verändern.

Beispielsweise wird die Formel ( x 1 ∨ x 2 ¯ ∨ x 3 ) ∧ ( x 1 ∨ x 2 ∨ x 3 ) ∧ ( x 1 ¯ ∨ x 2 ¯ ∨ x 3 ¯ ) {\displaystyle (x_{1}\vee {\overline {x_{2}}}\vee x_{3})\wedge (x_{1}\vee x_{2}\vee x_{3})\wedge ({\overline {x_{1}}}\vee {\overline {x_{2}}}\vee {\overline {x_{3}}})} wie folgt verarbeitet (eine Erklärung folgt nach der Tabelle).

	x 1 {\displaystyle x_{1}}	x 2 {\displaystyle x_{2}}	x 3 {\displaystyle x_{3}}	C 1 {\displaystyle C_{1}}	C 2 {\displaystyle C_{2}}	C 3 {\displaystyle C_{3}}
w 1 {\displaystyle w_{1}}	1	0	0	1	1	0
w 2 {\displaystyle w_{2}}	1	0	0	0	0	1
w 3 {\displaystyle w_{3}}	0	1	0	0	1	0
w 4 {\displaystyle w_{4}}	0	1	0	1	0	1
w 5 {\displaystyle w_{5}}	0	0	1	1	1	0
w 6 = 2 n {\displaystyle w_{6=2n}}	0	0	1	0	0	1
w 7 {\displaystyle w_{7}}	0	0	0	1	0	0
w 8 {\displaystyle w_{8}}	0	0	0	2	0	0
w 9 {\displaystyle w_{9}}	0	0	0	0	1	0
w 10 {\displaystyle w_{10}}	0	0	0	0	2	0
w 11 {\displaystyle w_{11}}	0	0	0	0	0	1
w 12 = 2 n + 2 m {\displaystyle w_{12=2n+2m}}	0	0	0	0	0	2
c {\displaystyle c}	1	1	1	4	4	4

• Die Ziffern einer Zeile werden als Stellen einer Dezimalzahl aufgefasst.
• Die ersten 2n Zeilen sind lediglich eine Codierung der Formel selbst: w 1 = 100110 {\displaystyle w_{1}=100110} besagt, dass x 1 {\displaystyle x_{1}} in den Klauseln C 1 {\displaystyle C_{1}} und C 2 {\displaystyle C_{2}} , aber nicht C 3 {\displaystyle C_{3}} vorkommt. w 2 {\displaystyle w_{2}} setzt das für x 1 ¯ {\displaystyle {\overline {x_{1}}}} um, w 3 {\displaystyle w_{3}} für x 2 {\displaystyle x_{2}} , w 4 {\displaystyle w_{4}} für x 2 ¯ {\displaystyle {\overline {x_{2}}}} etc.
• Die Zeilen w 2 n + 1 {\displaystyle w_{2n+1}} bis w 2 n + 2 m {\displaystyle w_{2n+2m}} sind "Korrekturzeilen", die nur auf der Diagonalen jeweils abwechselnd den Wert 1 oder 2 haben.
• Die Zahl c {\displaystyle c} besteht nur aus n Einsen und m Vieren. Dies bewirkt, dass bei Addition der Spaltenwerte, an den ersten n Stellen nur entweder w 1 {\displaystyle w_{1}} oder w 2 {\displaystyle w_{2}} ; w 3 {\displaystyle w_{3}} oder w 4 {\displaystyle w_{4}} etc. ausgewählt werden kann, wodurch in der Formel x i {\displaystyle x_{i}} auf true oder false gesetzt wird. Die Vieren sind so gewählt, dass zusätzlich zu den beiden Korrekturwerten, die zusammen nur 1+2=3 ergeben, noch mindestens eine der Variablen in den Klauseln vorhanden sein muss, um auf 4 zu kommen. Sind mehr Variablen verfügbar, können entsprechend Korrekturzeilen weggelassen werden.

Besitzt nun die boolesche Formel eine erfüllende Belegung, so nehmen wir falls x i {\displaystyle x_{i}} =true die Zahl w 2 i − 1 {\displaystyle w_{2i-1}} auf; falls x i {\displaystyle x_{i}} =false die Zahl w 2 i {\displaystyle w_{2i}} . Damit sind schon die Einsen in c {\displaystyle c} korrekt. Da alle Klauseln erfüllt sind, ist in den gerade hinzugefügten Zahlen in jeder Klausel mindestens eine erfüllte Variable vorhanden, somit sind die Spaltensummen im rechten Teil schon mindestens 1 und höchstens 3. Nun muss man nur noch die Korrekturvariablen geeignet wählen, um auf 4 zu kommen. Mit der konstruierten Menge ist es so möglich, genau c {\displaystyle c} zu erreichen, wenn die Formel erfüllbar ist.

Wenn nun c {\displaystyle c} genau erreicht werden kann, so muss die Teilmenge der w i {\displaystyle w_{i}} zunächst jeweils genau ein w 1 {\displaystyle w_{1}} oder w 2 {\displaystyle w_{2}} ; w 3 {\displaystyle w_{3}} oder w 4 {\displaystyle w_{4}} etc. enthalten, weil sonst die Einsen in c {\displaystyle c} nicht erfüllt wären. Somit ist gewährleistet, dass eine Variable tatsächlich true oder false (und nicht keins oder beides) ist. Durch diese Auswahl der Teilmenge muss dann auch jede Klausel erfüllt sein, denn wenn in einer Klausel keine Variable durch die Belegung erfüllt wäre, so würde die Addition nicht die notwendige Vier in c {\displaystyle c} ergeben. Daher ist die boolesche Formel insgesamt erfüllbar.

• Soma, Nei Y. Toth, Paolo: An exact algorithm for the subset sum problem. European Journal of Operational Research 136 S. 57–66
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, und Clifford Stein. Algorithmen – Eine Einführung. Oldenbourg-Verlag, 2004. ISBN 3-486-27515-1. Seiten 1017ff.