LS 2 /
Informatik
Datenstrukturen, Algorithmen und Programmierung 2 (DAP2)
LS 2 /
Informatik
Organisatorisches
Test (18.5.)


Bitte seien Sie um 12 Uhr im Audimax
Hilfsmittel: ein handbeschriebenes DIN A4 Blatt
Übungsgruppen


Wenn ihre Übungsgruppe wegen eines Feiertags ausfällt, gehen Sie in
eine andere
Falls Sie an keiner Übung teilnehmen, wird dies als Fehlen gewertet
2
LS 2 /
Informatik
Dynamische Programmierung
Fibonacci-Zahlen



F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)
3
LS 2 /
Informatik
Dynamische Programmierung
Fib(n)
1. if n=1 return 1
2. if n=2 return 1
3. return Fib(n-1) + Fib(n-2)
4
LS 2 /
Informatik
Dynamische Programmierung
Lemma
•
n
Die Laufzeit von Fib(n) ist W(1.6 ).
Beweis
•
Wir zeigen, dass die Laufzeit T(n) von Fib(n) größer als
1 1 5 


3  2 
n
.
5
LS 2 /
Informatik
Dynamische Programmierung
Lemma
•
n
Die Laufzeit von Fib(n) ist W(1.6 ).
Beweis
•
•
Wir zeigen, dass die Laufzeit T(n) von Fib(n) größer als


Damit folgt das Lemma wegen  1  5   1.6 .

2
1 1 5 


3  2 
n
.

6
LS 2 /
Informatik
Dynamische Programmierung
Lemma
•
n
Die Laufzeit von Fib(n) ist W(1.6 ).
Beweis
•
•
•
•
Wir zeigen, dass die Laufzeit T(n) von Fib(n) größer als


Damit folgt das Lemma wegen  1  5   1.6 .
 2 
Beweis per Induktion über n.
1 1 5 
(I.A.) Für n=1 ist T(1) ≥ 1 ≥ 3   2  .

1 1 5 


3  2 
n
.

7
LS 2 /
Informatik
Dynamische Programmierung
Lemma
•
n
Die Laufzeit von Fib(n) ist W(1.6 ).
Beweis
•
•
•
•
Wir zeigen, dass die Laufzeit T(n) von Fib(n) größer als


Damit folgt das Lemma wegen  1  5   1.6 .
 2 
Beweis per Induktion über n.
1 1 5 
(I.A.) Für n=1 ist T(1) ≥ 1 ≥ 3   2  .

Für n=2 ist T(2) ≥ 1 ≥
1 1 5 


3  2 
1 1 5 


3  2 
n
.

2
.
8
LS 2 /
Informatik
Dynamische Programmierung
Lemma
•
n
Die Laufzeit von Fib(n) ist W(1.6 ).
Beweis
•
(I.V.) Für m<n ist T(n) ≥
1 1 5 


3  2 
m
.
9
LS 2 /
Informatik
Dynamische Programmierung
Lemma
•
n
Die Laufzeit von Fib(n) ist W(1.6 ).
Beweis
1 1 5 


3  2 
m
•
(I.V.) Für m<n ist T(n) ≥
.
•
(I.S.) Wir haben T(n) ≥ T(n-1) + T(n-2) da der Algorithmus für n>2 Fib(n-1)
und Fib(n-2) rekursiv aufruft. Nach (I.V.) gilt somit
1 1 5 

T (n)  T (n  1)  T (n  2)   
3  2 
n 1
1 1 5 

  
3  2 
n2
10
LS 2 /
Informatik
Dynamische Programmierung
Lemma
•
n
Die Laufzeit von Fib(n) ist W(1.6 ).
Beweis
1 1 5 


3  2 
m
•
(I.V.) Für m<n ist T(n) ≥
.
•
(I.S.) Wir haben T(n) ≥ T(n-1) + T(n-2) da der Algorithmus für n>2 Fib(n-1)
und Fib(n-2) rekursiv aufruft. Nach (I.V.) gilt somit
1 1 5 

T (n)  T (n  1)  T (n  2)   
3  2 
1 1 5 

  
3  2 
n2
n 1
1 1 5 

  
3  2 
 1 5  1 1 5 
  

 1 


2  3  2 

n2
n
11
LS 2 /
Informatik
Dynamische Programmierung
Warum ist die Laufzeit so schlecht?

Betrachten wir Rekursionbaum für Aufruf Fib(6)
6
4
5
3
4
3
2
2
1
2
2
3
1
2
1
12
LS 2 /
Informatik
Dynamische Programmierung
Warum ist die Laufzeit so schlecht?

Betrachten wir Rekursionbaum für Aufruf Fib(6)
6
4
5
3
4
3
2
2
1
Bei der Berechnung von
Fib(6) wird Fib(3) dreimal
aufgerufen!
2
2
3
1
2
1
13
LS 2 /
Informatik
Dynamische Programmierung
Warum ist die Laufzeit so schlecht?

Betrachten wir Rekursionbaum für Aufruf Fib(6)
6
4
5
3
4
3
2
2
1
Es wird also mehrmals
dieselbe Rechnung
durchgeführt!
2
2
3
1
2
1
14
LS 2 /
Informatik
Dynamische Programmierung
Warum ist die Laufzeit so schlecht?

Betrachten wir Rekursionbaum für Aufruf Fib(6)
6
4
5
3
4
3
2
2
1
Bei großem n passiert dies
sehr häufig!
2
2
3
1
2
1
15
LS 2 /
Informatik
Dynamische Programmierung
Memoisation

Memoisation bezeichnet die Zwischenspeicherung der Ergebnisse von
Funktionsaufrufen eines rekursiven Algorithmus.
16
LS 2 /
Informatik
Dynamische Programmierung
Fib2(n)
1. Initialisiere Feld F[1..n]
2. for i 1 to n do
3.
F[i]  0
4. F[1]  1
5. F[2]  1
6. return FibMemo(n,F)
FibMemo(n,F)
1. if F[n]>0 then return F[n]
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
17
LS 2 /
Informatik
Dynamische Programmierung
Fib2(n)
1. Initialisiere Feld F[1..n]
2. for i 1 to n do
3.
F[i]  0
4. F[1]  1
5. F[2]  1
6. return FibMemo(n,F)
 Initialisiere Feld für Funktionswerte
FibMemo(n,F)
1. if F[n]>0 then return F[n]
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
18
LS 2 /
Informatik
Dynamische Programmierung
Fib2(n)
1. Initialisiere Feld F[1..n]
2. for i 1 to n do
3.
F[i]  0
4. F[1]  1
5. F[2]  1
6. return FibMemo(n,F)
 Initialisiere Feld für Funktionswerte
 Setze Feldeinträge auf 0
FibMemo(n,F)
1. if F[n]>0 then return F[n]
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
19
LS 2 /
Informatik
Dynamische Programmierung
Fib2(n)
1. Initialisiere Feld F[1..n]  Initialisiere Feld für Funktionswerte
2. for i 1 to n do
 Setze Feldeinträge auf 0
3.
F[i]  0
4. F[1]  1
 Setze F[1] auf korrekten Wert
5. F[2]  1
 Setze F[2] auf korrekten Wert
6. return FibMemo(n,F)
FibMemo(n,F)
1. if F[n]>0 then return F[n]
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
20
LS 2 /
Informatik
Dynamische Programmierung
Fib2(n)
1. Initialisiere Feld F[1..n]  Initialisiere Feld für Funktionswerte
2. for i 1 to n do
 Setze Feldeinträge auf 0
3.
F[i]  0
4. F[1]  1
 Setze F[1] auf korrekten Wert
5. F[2]  1
 Setze F[2] auf korrekten Wert
6. return FibMemo(n,F)
FibMemo(n,F)
1. if F[n]>0 then return F[n]
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
21
LS 2 /
Informatik
Dynamische Programmierung
Fib2(n)
1. Initialisiere Feld F[1..n]  Initialisiere Feld für Funktionswerte
2. for i 1 to n do
 Setze Feldeinträge auf 0
3.
F[i]  0
4. F[1]  1
 Setze F[1] auf korrekten Wert
5. F[2]  1
 Setze F[2] auf korrekten Wert
6. return FibMemo(n,F)
FibMemo(n,F)
1. if F[n]>0 then return F[n]
 Gib Wert zurück, falls
 schon berechnet
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
22
LS 2 /
Informatik
Dynamische Programmierung
Fib2(n)
1. Initialisiere Feld F[1..n]  Initialisiere Feld für Funktionswerte
2. for i 1 to n do
 Setze Feldeinträge auf 0
3.
F[i]  0
4. F[1]  1
 Setze F[1] auf korrekten Wert
5. F[2]  1
 Setze F[2] auf korrekten Wert
6. return FibMemo(n,F)
FibMemo(n,F)
1. if F[n]>0 then return F[n]
 Gib Wert zurück, falls
 schon berechnet
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)  Ansonsten berechne Wert
 und speichere Wert ab
23
3. return F[n]
LS 2 /
Informatik
Dynamische Programmierung
Fib2(n)
1. Initialisiere Feld F[1..n]  Initialisiere Feld für Funktionswerte
2. for i 1 to n do
 Setze Feldeinträge auf 0
3.
F[i]  0
4. F[1]  1
 Setze F[1] auf korrekten Wert
5. F[2]  1
 Setze F[2] auf korrekten Wert
6. return FibMemo(n,F)
FibMemo(n,F)
1. if F[n]>0 then return F[n]
 Gib Wert zurück, falls
 schon berechnet
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)  Ansonsten berechne Wert
 und speichere Wert ab
24
3. return F[n]
 Gib Wert zurück
LS 2 /
Informatik
Dynamische Programmierung
Fib2(n)
1. Initialisiere Feld F[1..n]
2. for i 1 to n do
3.
F[i]  0
4. F[1]  1
5. F[2]  1
6. return FibMemo(n,F)
Laufzeit:
O(n)
O(n)
O(n)
O(1)
O(1)
1+T(n)
FibMemo(n,F)
1. if F[n]>0 then return F[n]
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
25
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
i:
1
2
3
4
5
6
F[i]: 1
1
0
0
0
0
26
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
i:
1
2
3
4
5
6
F[i]: 1
1
0
0
0
0
27
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
4
i:
1
2
3
4
5
6
F[i]: 1
1
0
0
0
0
28
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
4
3
i:
1
2
3
4
5
6
F[i]: 1
1
0
0
0
0
29
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
4
3
2
i:
1
2
3
4
5
6
F[i]: 1
1
0
0
0
0
30
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
4
3
2
i:
1
2
3
4
5
6
F[i]: 1
1
0
0
0
0
31
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
4
1
3
2
i:
1
2
3
4
5
6
F[i]: 1
1
0
0
0
0
32
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
4
1
3
2
i:
1
1
2
3
4
5
6
F[i]: 1
1
0
0
0
0
33
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
4
1
3
2
i:
1
1
1
2
3
4
5
6
F[i]: 1
1
0
0
0
0
34
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
4
2
1
3
2
i:
1
1
1
2
3
4
5
6
F[i]: 1
1
2
0
0
0
35
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
4
2
1
3
2
i:
2
1
1
1
2
3
4
5
6
F[i]: 1
1
2
0
0
0
36
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
4
2
1
3
2
i:
1
2
1
1
1
2
3
4
5
6
F[i]: 1
1
2
0
0
0
37
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
3
4
2
1
3
2
i:
1
2
1
1
1
2
3
4
5
6
F[i]: 1
1
2
3
0
0
38
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
3
4
2
1
3
2
i:
3
1
2
1
1
1
2
3
4
5
6
F[i]: 1
1
2
3
0
0
39
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
6
FibMemo(6,F)
5
3
4
2
1
3
2
i:
2
3
1
2
1
1
1
2
3
4
5
6
F[i]: 1
1
2
3
0
0
40
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
FibMemo(6,F)
5
3
4
2
1
3
2
i:
6
5
2
3
1
2
1
1
1
2
3
4
5
6
F[i]: 1
1
2
3
5
0
41
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
FibMemo(6,F)
5
3
4
2
1
3
2
i:
6
5
4
2
3
1
2
1
1
1
2
3
4
5
6
F[i]: 1
1
2
3
5
0
42
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
FibMemo(6,F)
5
3
4
2
1
3
2
i:
6
5
3
4
2
3
1
2
1
1
1
2
3
4
5
6
F[i]: 1
1
2
3
5
0
43
LS 2 /
Informatik
Dynamische Programmierung
8
Beispiel
•
FibMemo(6,F)
5
3
4
2
1
3
2
i:
6
5
3
4
2
3
1
2
1
1
1
2
3
4
5
6
F[i]: 1
1
2
3
5
8
44
LS 2 /
Informatik
Dynamische Programmierung
FibMemo(n,F)
1. if F[n]>0 then return F[n]
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
Laufzeit
•
Jeder Aufruf FibMemo(m,F) generiert höchstens einmal die rekursiven Aufrufe
FibMemo(m-1,F) und FibMemo(m-2,F)
45
LS 2 /
Informatik
Dynamische Programmierung
FibMemo(n,F)
1. if F[n]>0 then return F[n]
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
Laufzeit
•
•
Jeder Aufruf FibMemo(m,F) generiert höchstens einmal die rekursiven Aufrufe
FibMemo(m-1,F) und FibMemo(m-2,F)
Also wird für jedes m<n die Funktion FibMemo(m,F) höchstens zweimal
aufgerufen
46
LS 2 /
Informatik
Dynamische Programmierung
FibMemo(n,F)
1. if F[n]>0 then return F[n]
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
Laufzeit
•
•
•
Jeder Aufruf FibMemo(m,F) generiert höchstens einmal die rekursiven Aufrufe
FibMemo(m-1,F) und FibMemo(m-2,F)
Also wird für jedes m<n die Funktion FibMemo(m,F) höchstens zweimal
aufgerufen
Ohne die Laufzeit für die rekursiven Aufrufe benötigt FibMemo O(1) Zeit
47
LS 2 /
Informatik
Dynamische Programmierung
FibMemo(n,F)
1. if F[n]>0 then return F[n]
2. F[n]  FibMemo(n-1, F) + FibMemo(n-2, F)
3. return F[n]
Laufzeit
•
•
•
•
Jeder Aufruf FibMemo(m,F) generiert höchstens einmal die rekursiven Aufrufe
FibMemo(m-1,F) und FibMemo(m-2,F)
Also wird für jedes m<n die Funktion FibMemo(m,F) höchstens zweimal
aufgerufen
Ohne die Laufzeit für die rekursiven Aufrufe benötigt FibMemo O(1) Zeit
Wir zählen jeden Aufruf mit Parameter 1..n. Daher müssen wir den Aufwand für
die rekursiven Aufrufe nicht berücksichtigen. Damit ergibt sich eine Laufzeit von
48
T(n)=O(n)
LS 2 /
Informatik
Dynamische Programmierung
Beobachtung

Die Funktionswerte werden bottom-up berechnet
Grundidee der dynamischen Programmierung

Berechne die Funktionswerte iterativ und bottom-up
FibDynamischeProgrammierung(n)
1. Initialisiere Feld F[1..n]
2. F[1]  1
3. F[2]  1
4. for i  3 to n do
5.
F[i]  F[i-1] + F[i-2]
6. return F[i]
49
LS 2 /
Informatik
Dynamische Programmierung
Beobachtung

Die Funktionswerte werden bottom-up berechnet
Grundidee der dynamischen Programmierung

Berechne die Funktionswerte iterativ und bottom-up
FibDynamischeProgrammierung(n)
1. Initialisiere Feld F[1..n]
2. F[1]  1
3. F[2]  1
Laufzeit O(n)
4. for i  3 to n do
5.
F[i]  F[i-1] + F[i-2]
6. return F[i]
50
LS 2 /
Informatik
Dynamische Programmierung
Dynamische Programmierung


Formuliere Problem rekursiv
Löse die Rekursion „bottom-up“ durch schrittweises Ausfüllen einer Tabelle
der möglichen Lösungen
Wann ist dynamische Programmierung effizient?


Die Anzahl unterschiedlicher Funktionsaufrufe (Größe der Tabelle) ist klein
Bei einer „normalen Ausführung“ des rekursiven Algorithmus ist mit vielen
Mehrfachausführungen zu rechnen
51
LS 2 /
Informatik
Dynamische Programmierung
Analyse der dynamischen Programmierung


Korrektheit: Für uns wird es genügen, eine Korrektheit der rekursiven
Problemformulierung zu zeigen
(für einen vollständigen formalen Korrektheitsbeweis wäre auch noch die
korrekte Umsetzung des Auffüllens der Tabelle mittels Invarianten zu zeigen.
Dies ist aber normalerweise offensichtlich)
Laufzeit: Die Laufzeitanalyse ist meist recht einfach, da der Algorithmus
typischerweise aus geschachtelten for-Schleifen besteht
Hauptschwierigkeit bei der Algorithmenentwicklung

Finden der Rekursion
52
LS 2 /
Informatik
Dynamische Programmierung
Problem: Partition


Eingabe: Menge M mit n natürlichen Zahlen
Ausgabe: Ja, gdw. man M in zwei Mengen L und R partitionieren kann, so
dass S x = S x gilt; nein sonst
xL
xR
Beispiel

4, 7, 9, 10, 13, 23
53
LS 2 /
Informatik
Dynamische Programmierung
Problem: Partition


Eingabe: Menge M mit n natürlichen Zahlen
Ausgabe: Ja, gdw. man M in zwei Mengen L und R partitionieren kann, so
dass S x = S x gilt; nein sonst
xL
xR
Beispiel

4, 7, 9, 10, 13, 23
54
LS 2 /
Informatik
Dynamische Programmierung
Problem: Partition


Eingabe: Menge M mit n natürlichen Zahlen
Ausgabe: Ja, gdw. man M in zwei Mengen L und R partitionieren kann, so
dass S x = S x gilt; nein sonst
xL
xR
Beispiel


4, 7, 9, 10, 13, 23
4 + 7 + 9 + 13 = 33
55
LS 2 /
Informatik
Dynamische Programmierung
Problem: Partition


Eingabe: Menge M mit n natürlichen Zahlen
Ausgabe: Ja, gdw. man M in zwei Mengen L und R partitionieren kann, so
dass S x = S x gilt; nein sonst
xL
xR
Beispiel



4, 7, 9, 10, 13, 23
4 + 7 + 9 + 13 = 33
10 +23 = 33
56
LS 2 /
Informatik
Dynamische Programmierung
Problem: Partition


Eingabe: Menge M mit n natürlichen Zahlen
Ausgabe: Ja, gdw. man M in zwei Mengen L und R partitionieren kann, so
dass S x = S x gilt; nein sonst
xL
xR
Beispiel




4, 7, 9, 10, 13, 23
4 + 7 + 9 + 13 = 33
10 +23 = 33
Ausgabe: Ja
57
LS 2 /
Informatik
Dynamische Programmierung
Beobachtung

Sei M eine Menge mit n natürlichen Zahlen.
M kann genau dann in zwei Mengen L,R mit S x = S x partitioniert
xL
xR
werden, wenn es eine Teilmenge L von M gibt mit S x =W/2, wobei
W= S x die Summe aller Zahlen aus M ist.
xL
xM
58
LS 2 /
Informatik
Dynamische Programmierung
Beobachtung

Sei M eine Menge mit n natürlichen Zahlen.
M kann genau dann in zwei Mengen L,R mit S x = S x partitioniert
xL
xR
werden, wenn es eine Teilmenge L von M gibt mit S x =W/2, wobei
W= S x die Summe aller Zahlen aus M ist.
xL
xM
Neue Frage
•
Gibt es LM mit S x = W/2 ?
xL
59
LS 2 /
Informatik
Dynamische Programmierung
Allgemeinere Frage

Welche Zahlen lassen sich als Summe einer Teilmenge von M darstellen?
60
LS 2 /
Informatik
Dynamische Programmierung
Noch allgemeiner


Sei M(i) die Menge der ersten i Zahlen von M
Für jedes i: Welche Zahlen lassen sich als Summe einer Teilmenge von M(i)
darstellen?
Formulierung als Funktion


Sei G(i,j) = 1 , wenn man die Zahl j als Summe einer Teilmenge der ersten i
Zahlen aus M darstellen kann
Sei G(i,j) = 0 , sonst
61
LS 2 /
Informatik
Dynamische Programmierung
Noch allgemeiner


Sei M(i) die Menge der ersten i Zahlen von M
Für jedes i: Welche Zahlen lassen sich als Summe einer Teilmenge von M(i)
darstellen?
Formulierung als Funktion



Sei G(i,j) = 1 , wenn man die Zahl j als Summe einer Teilmenge der ersten i
Zahlen aus M darstellen kann
Sei G(i,j) = 0 , sonst
Sei G(0,0) = 1
(Man kann die Null als Summe über die leere Menge darstellen)
62
LS 2 /
Informatik
Dynamische Programmierung
Noch allgemeiner


Sei M(i) die Menge der ersten i Zahlen von M
Für jedes i: Welche Zahlen lassen sich als Summe einer Teilmenge von M(i)
darstellen?
Formulierung als Funktion




Sei G(i,j) = 1 , wenn man die Zahl j als Summe einer Teilmenge der ersten i
Zahlen aus M darstellen kann
Sei G(i,j) = 0 , sonst
Sei G(0,0) = 1
(Man kann die Null als Summe über die leere Menge darstellen)
Sei G(0,j) = 0 für j≠0
(Man kann keine Zahl ungleich 0 als Summe über die leere Menge darstellen)
63
LS 2 /
Informatik
Dynamische Programmierung
Noch allgemeiner


Sei M(i) die Menge der ersten i Zahlen von M
Für jedes i: Welche Zahlen lassen sich als Summe einer Teilmenge von M(i)
darstellen?
Formulierung als Funktion




Sei G(i,j) = 1 , wenn man die Zahl j als Summe einer Teilmenge der ersten i
Zahlen aus M darstellen kann
Sei G(i,j) = 0 , sonst
Sei G(0,0) = 1
(Man kann die Null als Summe über die leere Menge darstellen)
Sei G(0,j) = 0 für j≠0
(Man kann keine Zahl ungleich 0 als Summe über die leere Menge darstellen)
64
LS 2 /
Informatik
Dynamische Programmierung
Beispiel
•
•
•
M = {13, 7, 10, 15}
G(1,20) = 0, da man 20 nicht als Summe einer Teilmenge der ersten Zahl aus
M darstellen kann
G(2,20) = 1, da man 20= 13 +7 als Summe einer Teilmenge der erste beiden
Zahlen aus M darstellen kann
65
LS 2 /
Informatik
Dynamische Programmierung
Formulierung als Funktion




Sei G(i,j) = 1 , wenn man die Zahl j als Summe einer Teilmenge der ersten i
Zahlen aus M darstellen kann
Sei G(i,j) = 0 , sonst
Sei G(0,0) = 1
(Man kann die Null als Summe über die leere Menge darstellen)
Sei G(0,j) = 0 für j≠0
(Man kann keine Zahl ungleich 0 als Summe über die leere Menge darstellen)
66
LS 2 /
Informatik
Dynamische Programmierung
Formulierung als Funktion




Sei G(i,j) = 1 , wenn man die Zahl j als Summe einer Teilmenge der ersten i
Zahlen aus M darstellen kann
Sei G(i,j) = 0 , sonst
Sei G(0,0) = 1
(Man kann die Null als Summe über die leere Menge darstellen)
Sei G(0,j) = 0 für j≠0
(Man kann keine Zahl ungleich 0 als Summe über die leere Menge darstellen)
Rekursion
•
•
G(i,j) = 1, wenn G(i-1,j) =1 oder (j≥M[i] und G(i-1,j-M[i]) = 1)
G(i,j) = 0, sonst
67
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemoInit(M)
1. W0
2. for i  1 to length[M] do
3.
W  W+ M[i]
4. if W ist ungerade then return 0
5. Initialisiere Feld G[0..length[M]][0..W]
6. for i  0 to length[M] do
7.
G[i,0]  1
8.
for j  1 to W do
9.
G[i,j]  -1
10. for j  1 to W do
11.
G[0,j]  0
12. if PartitionMemo(M,G, n, W/2)=1 then return 1
13. else return 0
68
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemoInit(M)
1. W0
 Berechne W
2. for i  1 to length[M] do
3.
W  W+ M[i]
4. if W ist ungerade then return 0
5. Initialisiere Feld G[0..length[M]][0..W]
6. for i  0 to length[M] do
7.
G[i,0]  1
8.
for j  1 to W do
9.
G[i,j]  -1
10. for j  1 to W do
11.
G[0,j]  0
12. if PartitionMemo(M,G, n, W/2)=1 then return 1
13. else return 0
69
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemoInit(M)
1. W0
 Berechne W
2. for i  1 to length[M] do
3.
W  W+ M[i]
4. if W ist ungerade then return 0
 Keine 2 gleich großen Teilmengen
5. Initialisiere Feld G[0..length[M]][0..W]
6. for i  0 to length[M] do
7.
G[i,0]  1
8.
for j  1 to W do
9.
G[i,j]  -1
10. for j  1 to W do
11.
G[0,j]  0
12. if PartitionMemo(M,G, n, W/2)=1 then return 1
70
13. else return 0
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemoInit(M)
1. W0
 Berechne W
2. for i  1 to length[M] do
3.
W  W+ M[i]
4. if W ist ungerade then return 0
 Keine 2 gleich großen Teilmengen
5. Initialisiere Feld G[0..length[M]][0..W]
 Initialisiere Feld G
6. for i  0 to length[M] do
 Setze dabei G[i,0] auf 1 und
7.
G[i,0]  1
 Setze dabei G[0,j], j>0, auf 0
8.
for j  1 to W do
 G[i,j] = -1 heißt, Funktionswert noch
9.
G[i,j]  -1
 nicht bekannt
10. for j  1 to W do
11.
G[0,j]  0
12. if PartitionMemo(M,G, n, W/2)=1 then return 1
71
13. else return 0
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemoInit(M)
1. W0
 Berechne W
2. for i  1 to length[M] do
3.
W  W+ M[i]
4. if W ist ungerade then return 0
 Keine 2 gleich großen Teilmengen
5. Initialisiere Feld G[0..length[M]][0..W]
 Initialisiere Feld G
6. for i  0 to length[M] do
 Setze dabei G[i,0] auf 1 und
7.
G[i,0]  1
 Setze dabei G[0,j], j>0, auf 0
8.
for j  1 to W do
 G[i,j] = -1 heißt, Funktionswert noch
9.
G[i,j]  -1
 nicht bekannt
10. for j  1 to W do
11.
G[0,j]  0
12. if PartitionMemo(M,G, n, W/2)=1 then return 1
72
13. else return 0
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemoInit(M)
1. W0
 Berechne W
2. for i  1 to length[M] do
3.
W  W+ M[i]
4. if W ist ungerade then return 0
 Keine 2 gleich großen Teilmengen
5. Initialisiere Feld G[0..length[M]][0..W]
 Initialisiere Feld G
6. for i  0 to length[M] do
 Setze dabei G[i,0] auf 1 und
7.
G[i,0]  1
 Setze dabei G[0,j], j>0, auf 0
8.
for j  1 to W do
 G[i,j] = -1 heißt, Funktionswert noch
9.
G[i,j]  -1
 nicht bekannt
10. for j  1 to W do
11.
G[0,j]  0
12. if PartitionMemo(M,G, n, W/2)=1 then return 1
73
13. else return 0
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemo(M,G, i, j)
1. if j<0 return 0
2. if G[i,j]≠-1 then return G[i,j]
3. if PartitionMemo(M,G,i-1,j)=1
or PartitionMemo(M,G,i-1,j-M[i]) then G[i,j]=1
4. else G[i,j]=0
5. return G[i,j]
74
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemo(M,G, i, j)
 Gibt es Teilmenge S von M[1..i] mit S x = j ?
xL
1. if j<0 return 0
2. if G[i,j]≠-1 then return G[i,j]
3. if PartitionMemo(M,G,i-1,j)=1
or PartitionMemo(M,G,i-1,j-M[i]) then G[i,j]=1
4. else G[i,j]=0
5. return G[i,j]
75
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemo(M,G, i, j)
 Gibt es Teilmenge S von M[1..i] mit S x = j ?
xL
1. if j<0 return 0
 Wenn j ungültig gib false zurück
2. if G[i,j]≠-1 then return G[i,j]
3. if PartitionMemo(M,G,i-1,j)=1
or PartitionMemo(M,G,i-1,j-M[i]) then G[i,j]=1
4. else G[i,j]=0
5. return G[i,j]
76
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemo(M,G, i, j)
 Gibt es Teilmenge S von M[1..i] mit S x = j ?
xL
1. if j<0 return 0
 Wenn j ungültig gib false zurück
2. if G[i,j]≠-1 then return G[i,j]
 G[i,j] bereits berechnet?
3. if PartitionMemo(M,G,i-1,j)=1
or PartitionMemo(M,G,i-1,j-M[i]) then G[i,j]=1
4. else G[i,j]=0
5. return G[i,j]
77
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemo(M,G, i, j)
 Gibt es Teilmenge S von M[1..i] mit S x = j ?
xL
1. if j<0 return 0
 Wenn j ungültig gib false zurück
2. if G[i,j]≠-1 then return G[i,j]
 G[i,j] bereits berechnet?
3. if PartitionMemo(M,G,i-1,j)=1
 Sonst, berechne G[i,j] nach
or PartitionMemo(M,G,i-1,j-M[i]) then G[i,j]=1  Rekursion
4. else G[i,j]=0
5. return G[i,j]
78
LS 2 /
Informatik
Dynamische Programmierung
PartitionMemo(M,G, i, j)
 Gibt es Teilmenge S von M[1..i] mit S x = j ?
xL
1. if j<0 return 0
 Wenn j ungültig gib false zurück
2. if G[i,j]≠-1 then return G[i,j]
 G[i,j] bereits berechnet?
3. if PartitionMemo(M,G,i-1,j)=1
 Sonst, berechne G[i,j] nach
or PartitionMemo(M,G,i-1,j-M[i]) then G[i,j]=1  Rekursion
4. else G[i,j]=0
5. return G[i,j]
79
LS 2 /
Informatik
Dynamische Programmierung
PartitionDynamicProg(M)
1. W0
2. for i  1 to length[M] do
3.
W  W+ M[i]
4. if W ist ungerade then return 0
5. Initialisiere Feld G[0..length[M]][0..W]
6. for i  0 to length[M] do
7.
for j  0 to W/2 do
8.
if j=0 then G[i,j]  1
9.
else if i=0 then G[i,j]  0
10.
else if G[i-1,j] = 1 or (M[i]≤j und G[i-1,j-M[i]]) then G[i,j]  1
11.
else G[i,j]  0
12. return G[length[M],W/2]
80
LS 2 /
Informatik
Dynamische Programmierung
PartitionDynamicProg(M)
1. W0
 Berechnen von W und
2. for i  1 to length[M] do
 Initialisierung von G
3.
W  W+ M[i]
4. if W ist ungerade then return 0
5. Initialisiere Feld G[0..length[M]][0..W]
6. for i  0 to length[M] do
7.
for j  0 to W/2 do
8.
if j=0 then G[i,j]  1
9.
else if i=0 then G[i,j]  0
10.
else if G[i-1,j] = 1 or (M[i]≤j und G[i-1,j-M[i]]) then G[i,j]  1
11.
else G[i,j]  0
12. return G[length[M],W/2]
81
LS 2 /
Informatik
Dynamische Programmierung
PartitionDynamicProg(M)
1. W0
 Berechnen von W und
2. for i  1 to length[M] do
 Initialisierung von G
3.
W  W+ M[i]
4. if W ist ungerade then return 0
5. Initialisiere Feld G[0..length[M]][0..W]
6. for i  0 to length[M] do
 Berechnung
7.
for j  0 to W/2 do
 von G
8.
if j=0 then G[i,j]  1
9.
else if i=0 then G[i,j]  0
10.
else if G[i-1,j] = 1 or (M[i]≤j und G[i-1,j-M[i]]) then G[i,j]  1
11.
else G[i,j]  0
12. return G[length[M],W/2]
82
LS 2 /
Informatik
Dynamische Programmierung
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
i
0
1
2
3
4
5
83
LS 2 /
Informatik
Dynamische Programmierung
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
i
0
1
1
2
3
4
5
84
LS 2 /
Informatik
Dynamische Programmierung
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
1
0
0
0
0
0
0
0
0
0
0
i
0
1
2
3
4
5
85
LS 2 /
Informatik
Dynamische Programmierung
M[1]=1
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
i
2
3
4
5
86
LS 2 /
Informatik
Dynamische Programmierung
M[1]=1
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
i
2
3
4
5
87
LS 2 /
Informatik
Dynamische Programmierung
M[1]=1
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
i
2
3
4
5
88
LS 2 /
Informatik
Dynamische Programmierung
M[2]=4
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
i
3
4
5
89
LS 2 /
Informatik
Dynamische Programmierung
M[2]=4
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
i
3
4
5
90
LS 2 /
Informatik
Dynamische Programmierung
M[2]=4
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
i
3
4
5
91
LS 2 /
Informatik
Dynamische Programmierung
M[2]=4
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
i
3
4
5
92
LS 2 /
Informatik
Dynamische Programmierung
M[2]=4
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
i
3
4
5
93
LS 2 /
Informatik
Dynamische Programmierung
M[2]=4
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
i
3
4
5
94
LS 2 /
Informatik
Dynamische Programmierung
M[3]=3
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
i
4
5
95
LS 2 /
Informatik
Dynamische Programmierung
M[3]=3
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
1
i
4
5
96
LS 2 /
Informatik
Dynamische Programmierung
M[3]=3
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
1
0
i
4
5
97
LS 2 /
Informatik
Dynamische Programmierung
M[3]=3
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
1
0
1
i
4
5
98
LS 2 /
Informatik
Dynamische Programmierung
M[3]=3
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
1
0
1
1
1
i
4
5
99
LS 2 /
Informatik
Dynamische Programmierung
M[3]=3
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
1
0
1
1
1
0
i
4
5
100
LS 2 /
Informatik
Dynamische Programmierung
M[3]=3
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
1
0
1
1
1
0
1
1
i
4
5
101
LS 2 /
Informatik
Dynamische Programmierung
M[3]=3
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
1
0
1
1
1
0
1
1
0
0
i
4
5
102
LS 2 /
Informatik
Dynamische Programmierung
M[4]=5
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
1
0
1
1
1
0
1
1
0
0
4
1
i
5
103
LS 2 /
Informatik
Dynamische Programmierung
M[4]=5
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
1
0
1
1
1
0
1
1
0
0
4
1
1
0
1
1
1
1
1
1
1
1
i
5
104
LS 2 /
Informatik
Dynamische Programmierung
M[5]=7
Beispiel: M = 1, 4, 3, 5, 7
j
0
1
2
3
4
5
6
7
8
9
10
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
2
1
1
0
0
1
1
0
0
0
0
0
3
1
1
0
1
1
1
0
1
1
0
0
4
1
1
0
1
1
1
1
1
1
1
1
5
1
1
0
1
1
1
1
1
1
1
1
i
105
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis

PartitionDynamicProg berechnet zunächst die Summe W der Elemente
aus M. Ist diese ungerade, so kann es keine Partition in zwei gleich große
Teilmengen geben.
106
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis





PartitionDynamicProg berechnet zunächst die Summe W der Elemente
aus M. Ist diese ungerade, so kann es keine Partition in zwei gleich große
Teilmengen geben.
Ansonsten berechnet der Algorithmus die Funktion G, mit
G[i,0]= 1 für alle i
G[0,j]= 0 für alle j>0
G[i,j] = 1, gdw. G[i-1,j]=1 oder (j≥M[i] und G[i-1,j-M[i]]=1)
107
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis






PartitionDynamicProg berechnet zunächst die Summe W der Elemente
aus M. Ist diese ungerade, so kann es keine Partition in zwei gleich große
Teilmengen geben.
Ansonsten berechnet der Algorithmus die Funktion G, mit
G[i,0]= 1 für alle i
G[0,j]= 0 für alle j>0
G[i,j] = 1, gdw. G[i-1,j]=1 oder (j≥M[i] und G[i-1,j-M[i]]=1)
Der Algorithmus gibt 1 zurück, gdw. G[length[M],W/2] = 1.
108
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis






PartitionDynamicProg berechnet zunächst die Summe W der Elemente
aus M. Ist diese ungerade, so kann es keine Partition in zwei gleich große
Teilmengen geben.
Ansonsten berechnet der Algorithmus die Funktion G, mit
G[i,0]= 1 für alle i
G[0,j]= 0 für alle j>0
G[i,j] = 1, gdw. G[i-1,j]=1 oder (j≥M[i] und G[i-1,j-M[i]]=1)
Der Algorithmus gibt 1 zurück, gdw. G[length[M],W/2] = 1.
109
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis


Wir zeigen per Induktion über i:
G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i] darstellen kann
110
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis



Wir zeigen per Induktion über i:
G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i] darstellen kann
(I.A.) Für i=0, j=0 kann man j als Summe der leeren Teilmenge darstellen
Für i=0, j>0, kann man j nicht als Summe einer Teilmenge der leeren
Menge darstellen
111
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis




Wir zeigen per Induktion über i:
G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i] darstellen kann
(I.A.) Für i=0, j=0 kann man j als Summe der leeren Teilmenge darstellen
Für i=0, j>0, kann man j nicht als Summe einer Teilmenge der leeren
Menge darstellen
(I.V.) Für alle k<i und alle j wird G[k,j] korrekt berechnet
112
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis





Wir zeigen per Induktion über i:
G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i] darstellen kann
(I.A.) Für i=0, j=0 kann man j als Summe der leeren Teilmenge darstellen
Für i=0, j>0, kann man j nicht als Summe einer Teilmenge der leeren
Menge darstellen
(I.V.) Für alle k<i und alle j wird G[k,j] korrekt berechnet
(I.S.) Z.z. G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i]
darstellen kann.
113
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis

(I.S.) Z.z. G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i]
darstellen kann.
114
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis


(I.S.) Z.z. G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i]
darstellen kann.
„<=“ Kann man j als Summe einer Teilmenge von M[1..i], so
kann man j entweder als Teilmenge von M[1..i-1] darstellen oder als
M[i] vereinigt mit einer Teilmenge von M[1..i-1
115
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis


(I.S.) Z.z. G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i]
darstellen kann.
„<=“ Kann man j als Summe einer Teilmenge von M[1..i], so
kann man j entweder als Teilmenge von M[1..i-1] darstellen oder als
M[i] vereinigt mit einer Teilmenge von M[1..i-1]. Im ersten Fall folgt aus (I.V.),
dass G[i-1,j]=1 ist und somit auch G[i,j]=1.
116
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis


(I.S.) Z.z. G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i]
darstellen kann.
„<=“ Kann man j als Summe einer Teilmenge von M[1..i], so
kann man j entweder als Teilmenge von M[1..i-1] darstellen oder als
M[i] vereinigt mit einer Teilmenge von M[1..i-1]. Im ersten Fall folgt aus (I.V.),
dass G[i-1,j]=1 ist und somit auch G[i,j]=1. Im zweiten Fall muss die
Teilmenge von M[1..i-1] Summe j-M[i] haben.
117
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis


(I.S.) Z.z. G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i]
darstellen kann.
„<=“ Kann man j als Summe einer Teilmenge von M[1..i], so
kann man j entweder als Teilmenge von M[1..i-1] darstellen oder als
M[i] vereinigt mit einer Teilmenge von M[1..i-1]. Im ersten Fall folgt aus (I.V.),
dass G[i-1,j]=1 ist und somit auch G[i,j]=1. Im zweiten Fall muss die
Teilmenge von M[1..i-1] Summe j-M[i] haben. Nach (I.V.) ist dann aber
G[i-1,j-M[i]]=1 und somit G[i,j] = 1.
118
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis



(I.S.) Z.z. G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i]
darstellen kann.
„<=“ Kann man j als Summe einer Teilmenge von M[1..i], so
kann man j entweder als Teilmenge von M[1..i-1] darstellen oder als
M[i] vereinigt mit einer Teilmenge von M[1..i-1]. Im ersten Fall folgt aus (I.V.),
dass G[i-1,j]=1 ist und somit auch G[i,j]=1. Im zweiten Fall muss die
Teilmenge von M[1..i-1] Summe j-M[i] haben. Nach (I.V.) ist dann aber
G[i-1,j-M[i]]=1 und somit G[i,j] = 1.
„=>“ Ist G[i,j]=1, so war entweder G[i-1,j]=1 oder G[i-1,j-M[i]]=1. Nach (I.V.)
kann man entweder j oder j-M[i] als Teilmenge von M[1..i-1] darstellen. Somit
119
kann man j als Teilmenge von M[1..i] darstellen.
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis



(I.S.) Z.z. G[i,j] = 1, gdw. man j als Summe einer Teilmenge von M[1..i]
darstellen kann.
„<=“ Kann man j als Summe einer Teilmenge von M[1..i], so
kann man j entweder als Teilmenge von M[1..i-1] darstellen oder als
M[i] vereinigt mit einer Teilmenge von M[1..i-1]. Im ersten Fall folgt aus (I.V.),
dass G[i-1,j]=1 ist und somit auch G[i,j]=1. Im zweiten Fall muss die
Teilmenge von M[1..i-1] Summe j-M[i] haben. Nach (I.V.) ist dann aber
G[i-1,j-M[i]]=1 und somit G[i,j] = 1.
„=>“ Ist G[i,j]=1, so war entweder G[i-1,j]=1 oder G[i-1,j-M[i]]=1. Nach (I.V.)
kann man entweder j oder j-M[i] als Teilmenge von M[1..i-1] darstellen. Somit
120
kann man j als Teilmenge von M[1..i] darstellen.
LS 2 /
Informatik
Dynamische Programmierung
Lemma 22

Algorithmus PartitionDynamicProg ist korrekt.
Beweis

Somit gilt G[length[M],W/2] = 1 gdw. man j als Summe einer Teilmenge von
M[1..length[M]] darstellen kann.
121
LS 2 /
Informatik
Dynamische Programmierung
Satz 23

Sei M eine Menge von n natürlichen Zahlen und R die Summe der Zahlen aus
M. Algorithmus PartitionDynamicProg löst Partition in Zeit O(nW).
Beweis
•
•
Die Korrektheit des Algorithmus folgt aus Lemma 22.
Die Laufzeit ist offensichtlich O(nW).
122
LS 2 /
Informatik
Dynamische Programmierung
Bemerkung


Partition ist ein NP-vollständiges Problem
Damit gibt es wahrscheinlich keinen polynomieller Algorithmus für Partition
Warum ist unser Algorithmus nicht polynomiell?


Die Laufzeit hängt von W ab
Sind die Zahlen aus M exponentiell groß, so ist die Laufzeit ebenfalls
exponentiell
123

F[i] - TU Dortmund, Informatik 2