Teilsummenproblem

Dem Algorithmus zur Lösung des Teilsummenproblems werden die folgenden Daten übergeben:
$A[1,\dots ,n]$ und $b$. Alle Einträge von $A$ sowie auch $b$ sind dabei aus $\mathbb{N}$.

Gesucht wird die Teilmenge $I$ aus $A$, sodass die Summe der Elemente aus $I=b$ ist (sofern es eine solche Summe gibt).

$$I\subseteq \{1,\dots ,n\}\text{ sodass }\sum _{i\in I}A[i]=b$$

Beispiel

Gegeben ist das folgende Array:
$A=[5,4,10,4,2]$

Für $b=11$ gibt es eine Teilsumme und zwar: $5+4+2$
Für $b=3$ gibt es keine Teilsumme
Für $b\ge 26$ gibt es keine Lösungen, da die Summe aller Elemente von $A$ nur $25$ beträgt.

Naiver Algorithmus

Alle möglichen Teilsummen in $A$ ausprobieren. Da $A$ aus $n$ Elementen besteht und jedes Element entweder in der Teilsumme enthalten sein kann oder nicht gibt es $2^n$ mögliche Teilsummen.
Der naive Algorithmus ist also viel zu teuer.

Ansatz mit dynamischer Programmierung

Teilproblem

Es wird nun versucht das Teilproblem von $A[1,\dots ,i]$ zu lösen.
Dazu wird $T(i,s)$ definiert. $T(i,s)$ stellt sich genau die Frage: Ist $s$ Teilsumme von $A[1,\dots ,i]$ und gibt dementsprechend $0$ oder $1$ zurück.

Rekursion

Bei der Rekursion gibt es nun zwei Möglichkeiten. Die Teilsumme benutzt das Element $A[i]$ oder die Teilsumme benutzt das Element $A[i]$ nicht. Es entsteht also die folgende Rekursionsformel:

$$T(i,s)=T(i-1,s)\vee T(i-1,s-A[i])$$

Der erste Teil ($T(i-1,s)$) entspricht der Aussage, dass die Teilsumme das Elemente $A[i]$ nicht verwendet.
Der zweite Teil ($T(i-1,s-A[i])$) entspricht der Aussage, dass die Teilsumme das Element $A[i]$ verwendet. Für den Fall, dass bei der Subraktion $s-A[i]$ eine negative Zahl herauskommt kann $0$ zurückgegeben werden. Wenn das Element an der Stelle $i$ grösser als die gesuchte Teilsumme ist, so wird es von keiner Teilsumme verwendet werden.

Zudem müssen noch zwei Basisfälle definiert werden:
$T(i,0)=1$
$T(0,s)=0$ (für $s\ge 0$)

DP-Tabelle

Für den Fall $b=7$ und dem Array $A=[5,4,10,4,2]$ lässt sich die folgende DP-Tabelle aufstellen:

$$\begin{array}{cccccccccc}& T(i,s)& 0& 1& 2& 3& 4& 5& 6& 7\\ i=0& -& 1& 0& 0& 0& 0& 0& 0& 0\\ 1& 5& 1& 0& 0& 0& 0& 1& 0& 0\\ 2& 4& 1& 0& 0& 0& 1& 1& 0& 0\\ 3& 10& 1& 0& 0& 0& 1& 1& 0& 0\\ 4& 4& 1& 0& 0& 0& 1& 1& 0& 0\\ 5& 2& 1& 0& 1& 0& 1& 1& 1& \boxed{1}\end{array}$$

Die Lösung wird unten rechts in rot geschrieben. Eine $1$ bedeutet, dass es eine Teilsumme gibt. Um jetzt herauszufinden, was die einzelnen Summanden dafür sind kann man das Backtracking anwenden. Dazu gibt jeder Sprung nach links einen Summanden an.

$$\begin{array}{cccccccccc}& T(i,s)& 0& 1& 2& 3& 4& 5& 6& 7\\ i=0& -& \boxed{1}& 0& 0& 0& 0& 0& 0& 0\\ 1& 5& 1& 0& 0& 0& 0& \boxed{1}& 0& 0\\ 2& 4& 1& 0& 0& 0& 1& \boxed{1}& 0& 0\\ 3& 10& 1& 0& 0& 0& 1& \boxed{1}& 0& 0\\ 4& 4& 1& 0& 0& 0& 1& \boxed{1}& 0& 0\\ 5& 2& 1& 0& 1& 0& 1& 1& 1& \boxed{1}\end{array}$$

Die Summanden sind also $2$ und $5$

Laufzeitanalyse

Laufzeit: $\theta (n\cdot b)$
Speicher: $\theta (n\cdot b)$

Hier ist spannend zu beobachten, dass die Laufzeit von der Grösse der gesuchten Zahl $b$ abhängt. Dieses Verhalten nennt sich pseudo polynomielle Laufzeit.

Hier betrachtet man nun die Inputlänge. Dazu wird betrachtet, was die Anzahl der benötigten Bits für $b$ ist. Also der Logarithmus zur Basis $2$ von b: ${\log }_2(b)$. Einfachheitshalber wird angenommen, dass jeder Eintrag des Arrays je eine Zelle des RAMs benötigen.

Das ergibt dann eine Inputlänge von $\theta (n+{\log }_2(b))$.

Für $b=2^n$ ergibt das eine Inputlänge von $\theta (n)$ aber eine Laufzeit von $\theta (n\cdot 2^n)$, was ein exponentielles Wachstum ist.

Für $b=n^c$ ergibt das eine Inputlänge von $\theta (n)$ aber eine Laufzeit von $\theta (n^{c+1})$, was ein polynomielles Wachstum ist.

Es stellt sich nun also die Frage, ob es eine Möglichkeit gibt das ganze zu verbessern und für alle $b$ eine polynomielle Laufzeit zu erreichen.

Die Antwort darauf ist: Man weiss es nicht aber es gibt eine starke Vermutung, dass es nicht besser geht (P und NP).