29.10.2026 - Woche 7

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).

Link to original

Rucksackproblem

Link to original

P und NP

Link to original

Approximations Algorithmus anhand des Rucksackproblems

Es stellt sich raus, dass das Rucksackproblem ein NP vollständiges Problem ist. Somit ist eine Lösung des Problems wahrscheinlich nicht in polynomieller Laufzeit möglich. Es gibt aber Algorithmen, welche das Problem approximieren und so in besserer Laufzeit zu einem Ergebnis kommen, welches der eigentlichen Lösung des Problems sehr nahe ist.

Der Approximative Algorithmus nimmt folgende Input Werte: $w_i,p_i,W\in \mathbb{N}$
Des Weiteren wird die folgende Annahme getroffen: Alle $w_i\le W$
Diese Annahme ist aber harmlos, wenn $w_i>W$ ist, kann es ohnehin nicht verwendet werden.

Ausserdem gilt: $P_{opt}\ge p_{max}$ wobei $P_{opt}$ der Profit der optimalen Lösung ist und $p_{max}$ das maximale $p_i$

Das Ziel des Algorithmus ist es nun eine Lösung zu finden, welche fast optimal ist und in polynomineller Zeit gefunden werden kann.

Die Idee um das zu erreichen ist es zu runden.

Dazu wird $p_i$ durch ${\tilde{p}}_i$ ersetzt, wobei ${\tilde{p}}_i$ folgendermassen definert ist:

$${\tilde{p}}_i:=k\cdot \lfloor \frac{p_i}{k}\rfloor k\in \mathbb{N}$$

$w_i$ und $W$ bleiben unverändert $\to$ die selben Teilmengen wie davor passen in den Rucksack.

Beispiel

$k=10$ , Profite $p_i$: $112,78,1001,17,237$
Die gerundeten Profite ${\tilde{p}}_i$ : $110,70,1000,230$

Aus der Anwendung des Rundens folgen nun die folgenden Beobachtungen:

$$\begin{array}{rl}{p}_i-k& \stackrel{(1)}{\le }{\tilde{p}}_i\stackrel{(2)}{\le }{p}_i\le p_{\max }\stackrel{(3)}{\le }{P}_{\mathrm{opt}}\le P\stackrel{(4)}{\le }n\cdot p_{\max }\end{array}$$

Daraus folgen nun die folgenden beiden Varianten:

• $p_i\stackrel{\mathrm{DP}}{\to }OPT\subseteq \{1,\dots ,n\}$ , Profit $P_{opt}$, Laufzeit: $O(n\cdot P)$ (zu langsam)
• ${\tilde{p}}_i\stackrel{\mathrm{DP}}{\to }\widetilde{OPT}\subseteq \{1,\dots ,n\}$ , Profit ???, Laufzeit: $O(\frac{n\cdot \tilde{P}}{k})\le O(\frac{n^2\cdot p_{max}}{k})$

$\tilde{P}={\tilde{p}}_1+\dots +{\tilde{p}}_n$

Die Ungleichung: $O(\frac{n\cdot \tilde{P}}{k})\le O(\frac{n^2\cdot p_{max}}{k})$ gilt, da $\tilde{P}={\sum }_{i=1}^n{\tilde{p}}_i\le {\sum }_{i=1}^n{p}_i\stackrel{(4)}{\le }n\cdot p_{\max }$.

Es stellt sich nun allerdings die Frage, wie gut sich $\widetilde{OPT}$ für das ursprüngliche Rucksackproblem eignet.

$\widetilde{OPT}$ wird daher untersucht um festzustellen, wie gut es sich eignet.

Es ist bekannt, das $\widetilde{OPT}$ das Optimum für ${\tilde{p}}_i$ ist.
Für jede Teilmenge $I$, welche in den Rucksack passt gilt:

$$\sum _{i\in \widetilde{OPT}}{\tilde{p}}_i\ge \sum _{i\in I}{\tilde{p}}_i$$

Das gilt auch für $I=OPT$:

$$\sum _{i\in \widetilde{OPT}}{\tilde{p}}_i\ge \sum _{i\in OPT}{\tilde{p}}_i\text{\hspace{1em}(*)}$$

Daraus folgt dann:

$$\begin{array}{rl}\sum _{i\in \widetilde{OPT}}{p}_i& \stackrel{(2)}{\ge }\sum _{i\in \widetilde{OPT}}{\tilde{p}}_i\\ & \stackrel{(\ast )}{\ge }\sum _{i\in OPT}{\tilde{p}}_i\\ & \stackrel{(1)}{\ge }\sum _{i\in OPT}(p_i-k)\\ & \ge \left(\sum _{i\in OPT}{p}_i\right)-nk\\ & =P_{\mathrm{opt}}-nk\\ & \stackrel{(3)}{\ge }{P}_{\mathrm{opt}}-nk\cdot \frac{P_{\mathrm{opt}}}{p_{\max }}\\ & =P_{\mathrm{opt}}\cdot \left(1-\frac{nk}{p_{\max }}\right)\end{array}$$

Die Idee ist nun, dass ein (kleines) $ϵ>0$ gewählt wird und $k=\frac{\epsilon \cdot p_{max}}{n}$ gesetzt wird.
(Eigentlich müsste $k=\lceil \frac{\epsilon \cdot p_{\max }}{n}\rceil$ stehen, da $k\in \mathbb{N}$ ist. Einfachheitshalber wird die Rundung aber weggelassen.)

Daraus folgt nun:

$$\Rightarrow \mathrm{PROFIT}(\widetilde{OPT})=\sum _{i\in \widetilde{OPT}}{p}_i\ge P_{\mathrm{opt}}\cdot (1-\epsilon )$$

Da $\epsilon$ klein ist, ist die Lösung fast so gut wie $P_{opt}$.

Die Laufzeit ist nun:

$$O\left(\frac{n^2{p}_{\max }}{k}\right)\le O\left(\frac{n^2{p}_{\max }}{\epsilon \cdot p_{\max }/n}\right)\le O\left(\frac{n^3}{\epsilon }\right)$$

Also ist die Laufzeit polynominell in $n\text{ und }\frac{1}{\epsilon }$

Link to original

Längste Aufsteigende Teilfolge

Das Ziel des Algorithmus ist es, die längste Teilfolge in einem Array zu finden, welche kontinuierlich aufsteigt.

Im Array $A=[2,13,17,9,11,4,78,28,15,25,99]$ ist die längste aufsteigende Teilfolge (LAT) z.B.
$LAT=2,9,11,15,25,99$ und hat die Länge $6$.

Gegeben ist dem Algorithmus ein Array $A[1,\dots ,n]$ von Integern und es wird angenommen, das kein Wert doppelt im Array ist.

Gesucht ist die längste aufsteigende Teilfolge wie am Beispiel oben illustriert.

Ansatz mit dynamischer Programmierung

Versuch 1

Beim Versuch 1 wird für $LAT(i)$ immer die längste AT von $A[1,\dots ,i]$ verwendet.

Beispiel

$A=[1,2,5,3,4]$
Das Array $A$ hat die folgenden LATs:

$LAT(1)=1$
$LAT(2)=1,2$
$LAT(3)=1,2,5$
$LAT(4)=1,2,5$
$LAT(5)=1,2,3,4$

Das Problem tritt hier zwischen $LAT(4)$ und $LAT(5)$ auf. Dieser Schritt ist mit Rekursion nicht bzw. nur schwer zu implementieren.

Versuch 2

Versuch 2 geht ähnlich vor, wie dies auch schon in Versuch 1 der Fall war. Allerdings merkt man sich beim zweiten Versuch alle Endungen einer LAT in $A[1,\dots ,i]$.

Beispiel

$A=[1,8,9,5,6,7]$

$LAT(1)=1$
$LAT(2)=1,8$
$LAT(3)=1,8,9$ (eindeutig)
$LAT(4)=1,8,9$ (eindeutig)
$LAT(5)=1,8,9\text{ und }1,5,6$

Auch hier ist dies nur schwer mit Rekursion zu implementieren.

Versuch 3

Die Idee bei Versuch 3 ist, dass man sich auch kürzere ATs in $A[1,\dots ,i]$ merkt.

$E(i,l)$ ist also definiert, als “Es gibt eine AT der Länge $l$, die in Position $i$ endet”. $E(i,l)$ gibt entweder $1$ zurück wenn die AT in $i$ endet oder $0$ wenn sie es nicht tut.

Die Rekursion sieht dann für $l\ge 2$ folgendermassen aus:

$$E(i,l)=\{\begin{array}{ll}1,& \text{falls es }j<i\text{ gibt mit }E(j,l-1)=1\\ & \text{und }A[j]<A[i]\\ 0,& \text{sonst}\end{array}$$

Der Basisfall lautet hier folgendermassen:
$E(i,1)=1$ für alle $i\in \{1,\dots ,n\}$

Laufzeitanalyse

$O({\sum }_{l=1}^n{\sum }_{i=1}^n(i-1))\le O({\sum }_{l=1}^n\frac{n(n-1)}{2})\le O(n^3)$

Wenn man sich die LATs noch einmal anschaut, so sieht man, dass es immer sinnvoller ist, die Folge $1,5,6$ zu verwenden und nicht $1,8,9$. Denn jedes Element, mit welchem man die Folge $1,8,9$ fortsetzen kann, setzt auch die Folge $1,5,6$ fort. Hingegen können Elemente, welche $>6$ aber $<9$ sind noch an die Folge $1,5,6$ angefügt werden, jedoch nicht an $1,8,9$.

Versuch 4

Der vierte Versuch macht sich genau das oben beobachtete zu Nutzen und soll so die Laufzeit verbessern.

$M(i,l)$ ist die kleinstmögliche Endung einer AT der Länge $l$ in $A[1,\dots ,i]$. Falls keine solche AT existiert wird dafür $\infty$ geschrieben.

Die Rekursion sieht dann für $l\ge 2$ folgendermassen aus:

$$M(i,l)=\{\begin{array}{ll}A[i],& \text{falls }M(i-1,l-1)<A[i]<M(i-1,l)\\ M(i-1,l),& \text{sonst}\end{array}$$

Die beiden Basisfälle lauten:

$$M(1,l)=\{\begin{array}{ll}A[1],& l=1\\ \infty ,& l>1\end{array}$$

Hier ist nun eine Laufzeit von $O(n^2)$ möglich.

Beispiel

$A=[1,8,9,5,6,7]$

Auch hier kann man wieder einige Eigenschaften entdecken, welche die Implementierung noch einmal verbessern:

• Die Zeilen sind immer sortiert.
• Pro Zeile wird immer maximal ein Wert geändert.
• Der Wert, welcher geändert werden muss kann mit der Binären Suche in $O(\log (n))$ durchgeführt werden.
• Wenn für jede Zeile dasselbe Array verwendet wird und die Einträge nur überschrieben werden, dauert das Update einer Zeile nur $O(\log (n))$
• Bei $n$ Zeilen kommt man somit auf eine Gesamtlaufzeit von $O(n\log (n)$

Wenn man nun die Elemente der LAT haben möchte, so muss man für jedes Element des Arrays den Vorgänger speichern. Wichtig ist, dass es der Vorgänger zum Zeitpunkt des Einfügen dieses Elementes ist.

Link to original