algorithm
Dynamische Programmierung
Suche…
Einführung
Dynamics-Programmierung ist ein weit verbreitetes Konzept und wird häufig zur Optimierung verwendet. Es bezieht sich auf die Vereinfachung eines komplizierten Problems, indem es rekursiv in einfachere Unterprobleme zerlegt wird, in der Regel einen Bottom-Up-Ansatz. Es gibt zwei Hauptattribute, die ein Problem aufweisen muss, damit die dynamische Programmierung anwendbar ist "Optimale Unterstruktur" und "Überlappende Unterprobleme". Zur Optimierung der Dynamics-Programmierung wird ein Konzept namens "Memorization" verwendet
Bemerkungen
Dynamic Programming ist eine Verbesserung von Brute Force. In diesem Beispiel erfahren Sie, wie Sie eine Dynamic Programming-Lösung von Brute Force erhalten.
Eine dynamische Programmierlösung hat zwei Hauptanforderungen:
Überlappende Probleme
Optimale Unterkonstruktion
Überlappende Teilprobleme bedeuten, dass Ergebnisse kleinerer Versionen des Problems mehrfach wiederverwendet werden, um zur Lösung des ursprünglichen Problems zu gelangen
Optimale Unterstruktur bedeutet, dass es eine Methode gibt, um ein Problem aus seinen Unterproblemen zu berechnen.
Eine dynamische Programmierlösung besteht aus zwei Hauptkomponenten, dem Zustand und dem Übergang
Der Staat verweist auf ein Teilproblem des ursprünglichen Problems.
Der Übergang ist die Methode, um ein Problem basierend auf seinen Unterproblemen zu lösen
Die Zeit, die eine Dynamic Programming Solution benötigt, kann als No. of States * Transition Time berechnet werden. Wenn also eine Lösung N^2 -Zustände hat und der Übergang O(N) , würde die Lösung ungefähr O(N^3) Zeit O(N^3) .
Rucksack Problem
0-1 Rucksack
Das Rucksackproblem ist ein Problem, wenn ein Satz von Elementen mit jeweils einem Gewicht, einem Wert und genau einer Kopie angegeben wird , welche Elemente in eine Sammlung aufgenommen werden sollen, sodass das Gesamtgewicht kleiner oder gleich einem bestimmten Wert ist limit und der Gesamtwert ist so groß wie möglich.
C ++ - Beispiel:
Umsetzung :
int knapsack(vector<int> &value, vector<int> &weight, int N, int C){
int dp[C+1];
for (int i = 1; i <= C; ++i){
dp[i] = -100000000;
}
dp[0] = 0;
for (int i = 0; i < N; ++i){
for (int j = C; j >= weight[i]; --j){
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
}
}
return dp[C];
}
Test :
3 5
5 2
2 1
3 2
Ausgabe :
3
Das heißt, der Maximalwert kann 3 erreicht werden, was durch Auswahl von (2,1) und (3,2) erreicht wird.
Ungebundener Rucksack
Das Unbounded Knapsack Problem ist ein Problem, das bei einem Satz von Gegenständen, jeder mit einem Gewicht, einem Wert und unendlichen Kopien , die Anzahl jedes Gegenstandes bestimmt, der in eine Sammlung aufgenommen werden soll, so dass das Gesamtgewicht kleiner oder gleich einem bestimmten Grenzwert ist und der Gesamtwert ist so groß wie möglich.
Python (2.7.11) Beispiel:
Umsetzung :
def unbounded_knapsack(w, v, c): # weight, value and capactiy
m = [0]
for r in range(1, c+1):
val = m[r-1]
for i, wi in enumerate(w):
if wi > r:
continue
val = max(val, v[i] + m[r-wi])
m.append(val)
return m[c] # return the maximum value can be achieved
Die Komplexität dieser Implementierung ist O(nC) , wobei n die Anzahl der Elemente ist.
Test :
w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]
print unbounded_knapsack(w, v, 13)
Ausgabe :
20
Das heißt, der Maximalwert ist 20, was durch Auswahl von (5, 8), (5, 8) und (3, 4) erreicht wird.
Gewichteter Job Scheduling-Algorithmus
Der gewichtete Job Scheduling-Algorithmus kann auch als gewichteter Aktivitätsauswahlalgorithmus bezeichnet werden.
Das Problem ist, wenn bestimmte Jobs mit ihrer Start- und Endzeit und einem Gewinn, den Sie nach Beendigung des Jobs erzielen, erzielt werden. Was ist der maximale Gewinn, den Sie erzielen können, wenn keine zwei Jobs gleichzeitig ausgeführt werden können?
Dieses sieht aus wie die Aktivitätsauswahl mit Greedy-Algorithmus, aber es gibt eine zusätzliche Wendung. Das heißt, anstatt die Anzahl der erledigten Jobs zu maximieren, konzentrieren wir uns auf den maximalen Gewinn. Die Anzahl der ausgeführten Jobs spielt hier keine Rolle.
Schauen wir uns ein Beispiel an:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | A | B | C | D | E | F |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 6 | 4 | 2 | 5 | 11 | 5 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Die Jobs werden mit einem Namen, ihrer Start- und Endzeit und ihrem Gewinn gekennzeichnet. Nach einigen Iterationen können wir herausfinden, ob wir Job-A und Job-E ausführen, und wir können den maximalen Gewinn von 17 erzielen. Nun, wie kann man das mit einem Algorithmus herausfinden?
Als erstes sortieren wir die Jobs nach ihrer Endzeit in nicht abnehmender Reihenfolge. Warum machen wir das? Wenn wir einen Job auswählen, dessen Ausführung weniger Zeit in Anspruch nimmt, haben wir die meiste Zeit für die Auswahl anderer Jobs. Wir haben:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Wir haben ein zusätzliches temporäres Array Acc_Prof der Größe n (Hier bezeichnet n die Gesamtzahl der Jobs). Dieser enthält den maximalen kumulierten Gewinn der Ausführung der Jobs. Verstehe es nicht Warten Sie und schauen Sie zu. Wir initialisieren die Werte des Arrays mit dem Gewinn der einzelnen Jobs. Das bedeutet, dass Acc_Prof [i] zunächst den Gewinn der Ausführung eines i-ten Jobs hält.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Bezeichnen wir nun Position 2 mit i und Position 1 wird mit j bezeichnet . Unsere Strategie besteht darin, j von 1 nach i-1 zu iterieren und nach jeder Iteration i um 1 zu erhöhen, bis i zu n + 1 wird .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Wir prüfen , ob Job [i] und Job [j] überlappen, das heißt, wenn die Zeit von Job [j] größer als Job [i] ‚s Startzeit, dann diesen beiden Arbeitsplätze nicht zusammen getan werden kann. Wenn sie sich jedoch nicht überschneiden, prüfen wir, ob Acc_Prof [j] + Profit [i]> Acc_Prof [i] ist . Wenn dies der Fall ist, werden wir Acc_Prof [i] = Acc_Prof [j] + Profit [i] aktualisieren. Das ist:
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
Hier steht Acc_Prof [j] + Profit [i] für den kumulierten Gewinn, wenn diese beiden Jobs zusammen ausgeführt werden. Schauen wir uns unser Beispiel an:
Hier überschneidet sich Job [j] mit Job [i] . Diese können also nicht zusammen gemacht werden. Da unser j gleich i-1 ist , erhöhen wir den Wert von i auf i + 1 , dh 3 . Und wir machen j = 1 .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nun überschneiden sich Job [j] und Job [i] nicht. Der Gesamtgewinn, den wir durch die Auswahl dieser beiden Jobs erzielen können, ist: Acc_Prof [j] + Profit [i] = 5 + 5 = 10, was größer als Acc_Prof [i] ist . Also aktualisieren wir Acc_Prof [i] = 10 . Wir erhöhen auch j um 1. Wir bekommen,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Hier überschneidet sich Job [j] mit Job [i] und j ist auch gleich i-1 . Also erhöhen wir i um 1 und machen j = 1 . Wir bekommen,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nun überschneiden sich Job [j] und Job [i] nicht, wir erhalten den kumulierten Gewinn 5 + 4 = 9 , der größer als Acc_Prof [i] ist . Wir aktualisieren Acc_Prof [i] = 9 und erhöhen j um 1.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Wieder überlappen sich Job [j] und Job [i] nicht. Der kumulierte Gewinn beträgt: 6 + 4 = 10 , was größer als Acc_Prof [i] ist . Wir aktualisieren erneut Acc_Prof [i] = 10 . Wir erhöhen j um 1. Wir erhalten:
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Wenn wir diesen Prozess fortsetzen, nachdem wir die gesamte Tabelle mit i durchlaufen haben, sieht unsere Tabelle schließlich folgendermaßen aus:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Einige Schritte wurden übersprungen, um das Dokument zu verkürzen.
Wenn wir das Array Acc_Prof durchlaufen , können wir herausfinden, dass der maximale Gewinn 17 beträgt! Der Pseudo-Code:
Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
for j -> 1 to i-1
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
endfor
endfor
maxProfit = 0
for i -> 1 to n
if maxProfit < Acc_Prof[i]
maxProfit = Acc_Prof[i]
return maxProfit
Die Belegung des Acc_Prof- Arrays ist komplex ( O 2 ). Die Array-Durchquerung nimmt O (n) an . Die Gesamtkomplexität dieses Algorithmus beträgt also O (n 2 ).
Wenn wir nun herausfinden möchten, welche Jobs ausgeführt wurden, um den maximalen Profit zu erzielen, müssen wir das Array in umgekehrter Reihenfolge durchlaufen. Wenn Acc_Prof mit dem maxProfit übereinstimmt , verschieben wir den Namen des Jobs in einen Stack und ziehen Profit ab dieser Job von maxProfit . Wir werden dies tun, bis maxProfit> 0 ist oder wir den Anfangspunkt des Acc_Prof- Arrays erreichen. Der Pseudo-Code sieht folgendermaßen aus:
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
if maxProfit is equal to Acc_Prof[i]
S.push(Job[i].name
maxProfit = maxProfit - Job[i].profit
endif
endfor
Die Komplexität dieses Verfahrens ist: O (n) .
Eine Sache, die wir berücksichtigen sollten: Wenn es mehrere Jobzeitpläne gibt, mit denen wir maximalen Profit erzielen können, können wir mit diesem Verfahren nur einen Jobzeitplan finden.
Abstand bearbeiten
Die Problemanweisung sieht so aus, wenn wir zwei Zeichenfolgen str1 und str2 erhalten, wie viele minimale Operationen können für str1 ausgeführt werden, die in str2 konvertiert werden.
Implementierung in Java
public class EditDistance {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "march";
String str2 = "cart";
EditDistance ed = new EditDistance();
System.out.println(ed.getMinConversions(str1, str2));
}
public int getMinConversions(String str1, String str2){
int dp[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0)
dp[i][j] = j;
else if(j==0)
dp[i][j] = i;
else if(str1.charAt(i-1) == str2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
}
}
}
return dp[str1.length()][str2.length()];
}
}
Ausgabe
3
Längste häufige Folge
Wenn wir die beiden Zeichenketten erhalten, müssen wir die längste gemeinsame Untersequenz finden, die in beiden vorhanden ist.
Beispiel
LCS für Eingangssequenzen "ABCDGH" und "AEDFHR" ist "ADH" der Länge 3.
LCS für Eingangssequenzen "AGGTAB" und "GXTXAYB" ist "GTAB" der Länge 4.
Implementierung in Java
public class LCS {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "AGGTAB";
String str2 = "GXTXAYB";
LCS obj = new LCS();
System.out.println(obj.lcs(str1, str2, str1.length(), str2.length()));
System.out.println(obj.lcs2(str1, str2));
}
//Recursive function
public int lcs(String str1, String str2, int m, int n){
if(m==0 || n==0)
return 0;
if(str1.charAt(m-1) == str2.charAt(n-1))
return 1 + lcs(str1, str2, m-1, n-1);
else
return Math.max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1));
}
//Iterative function
public int lcs2(String str1, String str2){
int lcs[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0 || j== 0){
lcs[i][j] = 0;
}
else if(str1.charAt(i-1) == str2.charAt(j-1)){
lcs[i][j] = 1 + lcs[i-1][j-1];
}else{
lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
}
}
}
return lcs[str1.length()][str2.length()];
}
}
Ausgabe
4
Fibonacci-Nummer
Bottom-Up-Ansatz zum Drucken der n-ten Fibonacci-Nummer mithilfe der dynamischen Programmierung.
Rekursiver Baum
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
Überlappende Unterprobleme
Hier sind fib (0), fib (1) und fib (3) die überlappenden Unterprobleme. Fib (0) wird 3 Mal wiederholt, Fib (1) wird 5 mal und Fib (3) 2 wiederholt mal.
Implementierung
public int fib(int n){
int f[] = new int[n+1];
f[0]=0;f[1]=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
Zeitkomplexität
Auf)
Längster gemeinsamer Untergrund
Bei 2 string str1 und str2 müssen wir die Länge des längsten gemeinsamen Teilstrings zwischen ihnen ermitteln.
Beispiele
Eingabe: X = "abcdxyz", y = "xyzabcd" Ausgabe: 4
Der längste gemeinsame Teilstring ist "abcd" und hat die Länge 4.
Eingabe: X = "zxabcdezy", y = "yzabcdezx" Ausgabe: 6
Der längste gemeinsame Teilstring ist "abcdez" und hat die Länge 6.
Implementierung in Java
public int getLongestCommonSubstring(String str1,String str2){
int arr[][] = new int[str2.length()+1][str1.length()+1];
int max = Integer.MIN_VALUE;
for(int i=1;i<=str2.length();i++){
for(int j=1;j<=str1.length();j++){
if(str1.charAt(j-1) == str2.charAt(i-1)){
arr[i][j] = arr[i-1][j-1]+1;
if(arr[i][j]>max)
max = arr[i][j];
}
else
arr[i][j] = 0;
}
}
return max;
}
Zeitkomplexität
O (m * n)