algorithm
Programowanie dynamiczne
Szukaj…
Wprowadzenie
Programowanie dynamiki jest szeroko stosowaną koncepcją i często jest wykorzystywane do optymalizacji. Odnosi się to do uproszczenia skomplikowanego problemu poprzez rozbicie go na prostsze podproblemy w sposób rekurencyjny, zwykle podejście oddolne. Istnieją dwa kluczowe atrybuty, które musi mieć problem, aby programowanie dynamiczne mogło mieć zastosowanie „Optymalna podstruktura” i „Nakładające się podproblemy”. Aby osiągnąć optymalizację, programowanie Dynamics wykorzystuje koncepcję o nazwie Zapamiętywanie
Uwagi
Programowanie dynamiczne to ulepszenie Brute Force, zobacz ten przykład, aby zrozumieć, w jaki sposób można uzyskać rozwiązanie do programowania dynamicznego od Brute Force.
Rozwiązanie do programowania dynamicznego ma 2 główne wymagania:
Nakładające się problemy
Optymalna podbudowa
Nakładające się podproblemy oznaczają, że wyniki mniejszych wersji problemu są wielokrotnie wykorzystywane w celu znalezienia rozwiązania pierwotnego problemu
Optymalna podbudowa oznacza, że istnieje metoda obliczenia problemu na podstawie jego podproblemów.
Rozwiązanie do programowania dynamicznego składa się z 2 głównych elementów: stanu i przejścia
Państwo odnosi się do podproblemu pierwotnego problemu.
Przejście to metoda rozwiązania problemu na podstawie jego podproblemów
Czas potrzebny na rozwiązanie do programowania dynamicznego można obliczyć jako No. of States * Transition Time . Zatem jeśli rozwiązanie ma stany N^2 , a przejściem jest O(N) , wówczas rozwiązanie zajmie z grubsza czas O(N^3) .
Problem z plecakiem
0-1 Plecak
Problem plecakowy stanowi problem, gdy dany zestaw elementów, każdy o wadze, wartości i dokładnie 1 kopii , określa, które elementy należy uwzględnić w kolekcji, tak aby całkowita waga była mniejsza lub równa danej limit, a całkowita wartość jest tak duża, jak to możliwe.
Przykład C ++:
Realizacja :
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
Wyjście :
3
Oznacza to, że maksymalna wartość, którą można osiągnąć, wynosi 3, co osiąga się wybierając (2,1) i (3,2).
Nieograniczony plecak
Problem niezwiązanego plecaka to problem polegający na tym, że biorąc pod uwagę zestaw przedmiotów, każdy o wadze, wartości i nieskończonych kopiach , określa się liczbę każdego elementu do uwzględnienia w kolekcji, tak aby całkowita waga była mniejsza lub równa podanemu limitowi a całkowita wartość jest tak duża, jak to możliwe.
Przykład Python (2.7.11):
Realizacja :
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
Złożoność tej implementacji wynosi O(nC) , gdzie n jest liczbą elementów.
Test :
w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]
print unbounded_knapsack(w, v, 13)
Wyjście :
20
Oznacza to, że maksymalna wartość, którą można osiągnąć, to 20, którą osiąga się wybierając (5, 8), (5, 8) i (3, 4).
Algorytm planowania ważonego zadania
Algorytm planowania zadań ważonych można również określić jako algorytm wyboru działań ważonych.
Problem polega na tym, że biorąc pod uwagę niektóre zadania z czasem rozpoczęcia i zakończenia oraz zyskiem, jaki osiągniesz po zakończeniu zadania, jaki jest maksymalny zysk, jaki możesz osiągnąć, biorąc pod uwagę, że nie można równolegle wykonać dwóch zadań?
Ten wygląda jak Selekcja aktywności za pomocą Chciwego Algorytmu, ale jest dodatkowy zwrot. Oznacza to, że zamiast maksymalizować liczbę zakończonych zleceń, koncentrujemy się na osiągnięciu maksymalnego zysku. Liczba wykonanych zadań nie ma tutaj znaczenia.
Spójrzmy na przykład:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Zadania są oznaczone nazwą, czasem rozpoczęcia i zakończenia oraz zyskiem. Po kilku iteracjach możemy dowiedzieć się, czy wykonamy Job-A i Job-E , możemy uzyskać maksymalny zysk wynoszący 17. Teraz, jak to sprawdzić za pomocą algorytmu?
Pierwszą rzeczą, którą robimy, jest sortowanie zadań według czasu ich zakończenia w kolejności nie malejącej. Dlaczego to robimy? Dzieje się tak, ponieważ jeśli wybieramy zadanie, którego ukończenie zajmuje mniej czasu, pozostawiamy najwięcej czasu na wybranie innych zadań. Mamy:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Będziemy mieć dodatkową tymczasową tablicę Acc_Prof o rozmiarze n (tutaj n oznacza całkowitą liczbę zadań). Będzie to zawierało maksymalny skumulowany zysk z wykonania zadań. Nie rozumiesz? Poczekaj i patrz. Zainicjujemy wartości tablicy z zyskiem każdego zadania. Oznacza to, że Acc_Prof [i] na początku zatrzyma zysk z wykonania i-tego zadania.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Teraz oznaczmy pozycję 2 za pomocą i , a pozycję 1 oznaczymy za pomocą j . Naszą strategią będzie iteracja j od 1 do i-1, a po każdej iteracji będziemy zwiększać i o 1, aż i stanie się n + 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Sprawdzamy, czy Job [i] i Job [j] nakładają się, to znaczy, jeśli czas zakończenia Job [j] jest dłuższy niż czas rozpoczęcia Job [i] , to tych dwóch zadań nie można wykonać razem. Jeśli jednak się nie pokrywają, sprawdzimy, czy Acc_Prof [j] + Profit [i]> Acc_Prof [i] . W takim przypadku zaktualizujemy Acc_Prof [i] = Acc_Prof [j] + Profit [i] . To jest:
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
Tutaj Acc_Prof [j] + Zysk [i] reprezentuje skumulowany zysk z wykonania tych dwóch zadań razem. Sprawdźmy to w naszym przykładzie:
Tutaj Job [j] pokrywa się z Job [i] . Więc nie można tego zrobić razem. Ponieważ nasze j jest równe i-1 , zwiększamy wartość i do i + 1 , czyli 3 . I tworzymy 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Teraz Job [j] i Job [i] nie pokrywają się. Łączna kwota zysku, jaki możemy osiągnąć, wybierając te dwa zadania, to: Acc_Prof [j] + zysk [i] = 5 + 5 = 10, co jest większe niż Acc_Prof [i] . Dlatego aktualizujemy Acc_Prof [i] = 10 . Zwiększamy również j o 1. Otrzymujemy,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Tutaj Job [j] pokrywa się z Job [i], a j jest również równe i-1 . Zatem zwiększamy i o 1 i tworzymy j = 1 . Dostajemy
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Teraz Job [j] i Job [i] nie pokrywają się, otrzymujemy skumulowany zysk 5 + 4 = 9 , który jest większy niż Acc_Prof [i] . Aktualizujemy Acc_Prof [i] = 9 i zwiększamy wartość j o 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Znów Job [j] i Job [i] nie pokrywają się. Skumulowany zysk wynosi: 6 + 4 = 10 , czyli więcej niż Acc_Prof [i] . Ponownie aktualizujemy Acc_Prof [i] = 10 . Zwiększamy j o 1. Otrzymujemy:
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Jeśli będziemy kontynuować ten proces, po iteracji po całej tabeli za pomocą i , nasza tabela będzie w końcu wyglądać następująco:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Kilka kroków zostało pominiętych, aby skrócić dokument.
Jeśli przejdziemy przez tablicę Acc_Prof , możemy ustalić maksymalny zysk wynoszący 17 ! Pseudo-kod:
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
Złożoność zapełniania tablicy Acc_Prof wynosi O (n 2 ). Przejście przez tablicę przyjmuje O (n) . Zatem całkowita złożoność tego algorytmu wynosi O (n 2 ).
Teraz, jeśli chcemy dowiedzieć się, które zadania zostały wykonane, aby uzyskać maksymalny zysk, musimy przejść przez tablicę w odwrotnej kolejności, a jeśli Acc_Prof pasuje do maxProfit , wypchniemy nazwę zadania do stosu i odejmujemy Zysk to zadanie od maxProfit . Będziemy to robić, dopóki nasz maxProfit> 0 lub dotrzemy do punktu początkowego tablicy Acc_Prof . Pseudo-kod będzie wyglądał następująco:
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
Złożoność tej procedury wynosi: O (n) .
Należy pamiętać, że jeśli istnieje wiele harmonogramów prac, które mogą zapewnić nam maksymalny zysk, za pomocą tej procedury możemy znaleźć tylko jeden harmonogram prac.
Edytuj odległość
Opis problemu wygląda tak, jakbyśmy otrzymali dwa ciągi str1 i str2, a następnie ile minimalnej liczby operacji można wykonać na str1, które zostaną przekonwertowane na str2.
Implementacja w Javie
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()];
}
}
Wynik
3
Najdłuższa wspólna kolejność
Jeśli otrzymamy dwa ciągi, musimy znaleźć najdłuższą wspólną podsekwencję występującą w obu z nich.
Przykład
LCS dla sekwencji wejściowych „ABCDGH” i „AEDFHR” to „ADH” o długości 3.
LCS dla sekwencji wejściowych „AGGTAB” i „GXTXAYB” to „GTAB” o długości 4.
Implementacja w Javie
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()];
}
}
Wynik
4
Liczba Fibonacciego
Podejście oddolne do drukowania n-tej liczby Fibonacciego za pomocą programowania dynamicznego.
Drzewo rekurencyjne
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)
Pokrywające się pod-problemy
Tutaj fib (0), fib (1) i fib (3) są nakładającymi się na siebie problemami. Fib (0) powtarza się 3 razy, fib (1) powtarza się 5 razy, a fib (3) powtarza się 2 czasy.
Realizacja
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];
}
Złożoność czasu
Na)
Najdłuższe wspólne podciągi
Biorąc pod uwagę 2 łańcuchy str1 i str2, musimy znaleźć długość najdłuższego wspólnego podłańcucha między nimi.
Przykłady
Wejście: X = „abcdxyz”, y = „xyzabcd” Wyjście: 4
Najdłuższym wspólnym podciągiem jest „abcd” i ma on długość 4.
Dane wejściowe: X = „zxabcdezy”, y = „yzabcdezx” Dane wyjściowe: 6
Najdłuższym wspólnym podciągiem jest „abcdez” i ma on długość 6.
Implementacja w Javie
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;
}
Złożoność czasu
O (m * n)