# Programowanie dynamiczne ### Wstęp Dzielimy problem względem kilku parametrów (zwykle rozmiaru danych). Szukane rozwiązanie obliczamy jako funkcję rozwiązań tego samego problemu dla mniejszych danych. Można powiedzieć, że jeżeli jesteśmy napisać wzór rekurencyjny rozwiązujący problem to możemy znaleźć rozwiążanie używając DP (ang. Dynamic Programming). ### Kiedy działa? Problem musi mieć własność optymalnej podstruktury. To znaczy, że optymalne rozwiązanie jest funkcją rozwiązań podproblemów. ### Praktyka * Raczej nie ma tego na maturze. * Trzeba znaleźć wzór, czyli określić jak możemy sparametryzować problem i jak na podstawie podproblemów możemy uzyskać rozwiązanie dla zadanego wejścia. * Trudnością może być zbijanie złożoności, czyli tak naprawdę zmniejszanie przestrzeni stanów. Mniej stanów $\rightarrow$ mniej pętli $\rightarrow$ mniejsza złożoność ### Przykład $$ F_{n} = F_{n-1} + F_{n-2} $$ Brzmi znajomo? Aby obliczyć $F_n$ musimy znać $F_{n-1}$ oraz $F_{n-2}$. Dokładnie tak jak mówiliśmy, znając liczby Fibonacciego do $n$ jesteśmy w stanie obliczyć $F_{n+1}$ # Zachłanne ### Wstęp W podejściu zachłannym za każdym razem wybieramy ***lokalnie*** najlepiej. Podejmujemy w danym momencie najlepszą decyzję, ale **NIE ZAWSZE** prowadzi to do **globalnie** najlepszego rozwiązania. *czasem w życiu trzeba zrobić jeden krok w tył, aby zrobić dwa kroki do przodu* ### Kiedy działa? Algorytmów zachłannych najczęściej używamy w problemach optymalizacyjnych. Prowadzą one do niekoniecznie optymalnych rozwiązań, często dobrze je przybliżają. ### Praktyka * Raczej nie ma tego na maturze. * Łatwo się je pisze a ciężko dowodzi poprawność. * Dobre do aproksymacji. # Problem wydawania reszty Mamy wydać kwotę $C$ używając nominałów $w_1, w_2, \ldots, w_n$ tak by użyć jak najmniej monet. ### Podejście zachłanne Bierzemy największą monetę od reszty jaką jeszcze mamy do wydania. ### Podejście dynamiczne Jak możemy sparametryzować zadanie? Jakie możemy brać **mniejsze** instancje? ::: spoiler odp <br/>Mając dany zestaw nominałów możemy określić jako $T[k]$ rozwiązanie problemu wydania kwoty $k$ za pomocą danych nominałów <br/>Jak można wyliczyć $T[k]$ znając wartości $T[i]$ dla $i < k$ ? ::: spoiler odp $T[i] = \min\{T[i-1] + 1, T[i-2] + 1, T[i-5] + 1\}$ ::: #### Przykład: $C = 13$ $w = \{1, 2, 5\}$ ::: spoiler Rozwiązanie $5, 5, 2, 1$ ::: #### Przykład2: $C = 8$ $w = \{1, 4, 5\}$ ::: spoiler Rozwiązanie $5, 5, 2, 1$ ::: # Poblem plecakowy Mamy $N$ elementów każdy element ma swoją wartość $c_i$ i swoją wagę $w_i$. Chcemy zmieścić jak najwięcej wartości w plecaku o pojemności $B$. Formalniej: $$ \max \sum_{i=1}^N c_ix_i \\ \sum_{i=1}^N w_ix_i \leq B \\ x_i = \begin{cases} 1 \quad\text{gdy bierzemy } i\text{-ty element}\\ 0 \quad\text{gdy nie bierzemy go} \end{cases} $$ ### Podejście zachłanne Bierzemy element o największym współczynniku wartościowagi tj. $\frac{c_i}{w_i}$ nie przekraczający pojemności plecaka. Takie rozwiązanie daje 2-aproksymacje. ### Podejście dynamiczne Jak możemy sparametryzować zadanie? Jakie możemy brać **mniejsze** instancje? ::: spoiler odp <br/>Mając dany zestaw elementów możemy określić jako $P[k]$ rozwiązanie problemu spakowania plecaka o pojemności $k$ za pomocą danych elementów. <br/>Jak można wyliczyć $P[k]$ znając wartości $P[i]$ dla $i < k$ ? ::: spoiler odp $$P[k] = \max \{P[k - w_j] + c_j\}$$ ::: <br/>Jaki jest problem poprzedniego rozwiązania? ::: spoiler odp Każdy element możemy wziąć kilka razy. Chcielibyśmy móc tylko raz. ::: <br/> Jak uniknąć tego problemu? ::: spoiler odp Musimy ograniczyć możliwe do wzięcia elementy. Możemy oznaczyć $P[i][j]$ jako największą możliwą wartość plecaka o pojemności $j$ używając elementów o indeksach mniejszych lub równych $i$. ::: <br/> Pełne wzorki ::: spoiler Pełne wzorki $$ P[0][j] = 0\\ P[i][0] = 0\\ P[i][j] = P[i-1][j] \text{jeśli } w_i>j\\ P[i][j] = \max(P[i-1][j], c_i+P[i-1][j-w_i]) \text{jeśli } w_i\leq j $$ ::: ### Kod ::: spoiler C++ ```c++= #include <bits/stdc++.h> using namespace std; #define maxn 100 int dp[maxn][maxn]; int w[maxn]; int c[maxn]; int main(){ int n, b; cin >> n; for (int i = 1; i <= n; i++) cin >> w[i] >> c[i]; cin >> b; for (int i = 0; i <= n; i++) dp[i][0] = 0; FOR (Int j = 0; j <= b; j++) dp[0][j] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= b; j++) { if (w[i] > j) dp[i][j] = dp[i-1][j]; else dp[i][j] = max(dp[i-1][j], c[i] + dp[i-1][j-w[i]]); } } cout << dp[n][b]; return 0; } ``` ::: ::: spoiler python3 ```python3= def solve_knapsack(b, ws, cs): n = len(ws) dp = [[0] * (b+1) for _ in range(n + 2)] ws.insert(0,0) cs.insert(0,0) for i in range(1, n+1): for j in range(b+1): if ws[i] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], cs[i] + dp[i-1][j-ws[i]]) return dp[n][b] print(solve_knapsack(10, [8, 5, 3], [40, 20, 22])) ``` ::: ### Zadania https://files.wpmii.pl/2021-11-20-zadania.pdf?fbclid=IwAR3ByClGRarBRS-miHRv-Hop-mSGlyIHy4kOHQK30f0iaw9whiVQOSkt4-Q