U poglavlju 4.8 videli smo da je jedna od najopasnijih odlika rekurzivno implementiranih funkcija neefikasnost koja nastaje usled rekurzivnih poziva ponovljenih za iste vrednosti argumenata (engl. overlapping recursive calls). Tipičan primer je izračunavanje elemenata Fibonačijevog niza, gde naivna rekurzivna implementacija dovodi do eksponencijalne složenosti. U ovom poglavlju prikazađemo tehniku dinamičkog programiranja, koja predstavlja sistematičan način da se reši problem ponovljenih rekurzivnih poziva.
Naredna naivna implementacija funkcije koja izračunava \(n\)-ti element Fibonačijevog niza zanemaruje činjenicu da je prilikom izračunavanja vrednosti fib(n-1) već izračunala vrednost fib(n-2), pa tu vrednost izračunava iznova, što dovodi do ogromne neefikasnosti.
int fib(int n) {
if (n == 0 || n == 1)
return n;
else
return fib(n-1) + fib(n-2);
}Da bi se izbegla suvišna izračunavanja moguće je koristiti tehniku memoizacije, koja podrazumeva da se u posebnoj strukturi podataka čuvaju svi rezultati već završenih rekurzivnih poziva. Pri svakom ulasku u funkciju konsultuje se ova struktura i, ako je rezultat već poznat, vraća se prethodno izračunat rezultat. U našem slučaju postoji jedan parameter rekurzivne funkcije, pa možemo koristiti niz memo (bilo globalni, bilo prosleđen kao dodatni parametar rekurzivne funkcije). Pošto vremenska složenost izračunavanja vrednosti u slučaju izlaza iz rekurzije pripada klasi \(O(1)\), memoizacija se može preskočiti za \(n=0\) i \(n=1\).
int fib(int n, vector<int>& memo) {
if (n == 0 || n == 1)
return n;
if (memo[n])
return memo[n];
return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}
int fib(int n) {
vector<int> memo(n+1, 0);
return fib(n, memo);
}U ovoj varijanti funkcije, poziv za svaku vrednost parametra \(n\) izvršava se tačno dva puta (osim za vrednosti \(0\), \(n\) i \(n-1\), za koje se poziv izvršava samo jednom), pa je složenost izračunavanja linearna tj. \(O(n)\). Na primer, tokom izračunavanja vrednosti fib(n-1) biće izračunata i memoizovana vrednost fib(n-2), pa će poziv fib(n-2) samo pročitati i vratiti ranije izračunatu vrednost. Stablo rekurzivnih poziva memoizovane funkcije za \(n=5\) prikazano je na slici 21.
Drugi pristup rešavanja problema suvišnih izračunavanja naziva se dinamičko programiranje1, koje podrazumeva da se rekurzija eliminiše i zameni induktivnom konstrukcijom. Prilikom rekurzivnog rešavanja vrši se poziv funkcije koja treba da izračuna rešenje polaznog problema, a zatim se taj problem svodi na jednostavnije potprobleme koji se zatim rešavaju novim pozivima iste funkcije. Potproblemi se rešavaju samo kada je to potrebno, tj. samo kada funkcija izvrši rekurzivni poziv. Kod dinamičkog programiranja, obično se unapred vrši rešavanje svih potproblema manje dimenzije, bez provere da li će njihovo rešavanje zaista biti neophodno (u praksi se često pokazuje da jeste). Na osnovu rešenih potproblema manje dimenzije, kreira se rešenje problema veće dimenzije, sve dok se ne kreira i rešenje glavnog problema. Implementacije rešenja dinamičkim programiranjem ne uključuju rekurzivne funkcije (mada je veza između rešenja problema veće i potproblema manje dimenzije i dalje suštinski rekurentna). Na primer, gore navedena funkcija fib može se zameniti iterativnom funkcijom koja od početnih elemenata niza postepeno kreira dalje elemente niza. Iako je potrebno izračunati vrednost funkcije fib samo za parametar \(n\), izračunavaju se vrednosti funkcije fib za sve parametre manje od ili jednake \(n\).
int fib(int n) {
if (n == 0 || n == 1)
return n;
vector<int> f(n+1, 0);
f[0] = 0; f[1] = 1;
for (int i = 2; i <= n; i++)
f[i] = f[i-1] + f[i-2];
return f[n];
}Primetimo da za izračunavanje \(n\)-tog elementa niza nije neophodno pamtiti sve elemente niza do indeksa \(n\) već samo dva prethodna, pa se funkcija može implementirati i jednostavnije:
int fib(int n) {
unsigned i, fpp, fp, f;
if (n == 0 || n == 1)
return n;
fpp = 0; fp = 1;
for (i = 2; i <= n; i++) {
f = fpp + fp;
fpp = fp;
fp = f;
}
return f;
}U narednim primerima ćemo videti da se isti niz koraka koji je sproveden u ovom primeru (memoizacija ili dinamičko programiranje naviše, praćeno memorijskom optimizacijom) može sprovesti i na drugim problemima kod kojih dolazi do ponovljenih rekurzivnih poziva.
Čest zadatak je da se prebroje kombinatorni objekti tj. da se odredi koliko postoji objekata (nizova, lista, drveta i slično) koji zadovoljavaju neko zadato svojstvo. U ovakvim problemima često dolazi do ponavljanja rekurzivnih poziva i oni se zato često rešavaju tehnikom dinamičkog programiranja.
Particija pozitivnog prirodnog broja \(n\) je rastavljanje broja \(n\) na zbir nekoliko pozitivnih prirodnih brojeva pri čemu je redosled sabiraka nebitan (stoga možemo pretpostaviti da je taj redosled ili uvek nerastući ili uvek neopadajući). Na primer, ako je redosled nerastući, particije broja \(4\) su \(1+1+1+1\), \(2+1+1\), \(2+2\), \(3+1\), \(4\). Napisati program koji određuje broj particija za dati prirodan broj \(n\).
Prva i jedina linija standardnog ulaza sadrži prirodan broj \(n\) (\(n \leq 100\)).
Na standardnom izlazu prikazati u prvoj liniji broj particija prirodnog broja \(n\).
6
11
Particije sa neopadajuće sortiranim sabircima su: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3, 1+1+2+2, 1+1+4, 1+2+3, 1+5, 2+2+2, 2+4, 3+3 i 6.
100
190569292
Rekurzivne procedure koje nabrajaju sve particije se mogu prilagoditi tako da izračunaju broj particija.
Svaka particija ima svoj prvi sabirak. Svakoj particiji broja \(n\) kojoj je prvi sabirak \(s\) (pri čemu je \(1 \leq s \leq n\)) jednoznačno odgovara neka particija broja \(n-s\). Nametnućemo uslov da su sabirci u svakoj particiji sortirani nerastuće. Zato, ako je prvi sabirak \(s\), svi sabirci iza njega moraju da budu manji ili jednaki od \(s\). Zato nam nije dovoljno samo da umemo da prebrojimo sve particije broja \(n-s\), već je potrebno da ojačamo induktivnu hipotezu. Označimo sa \(p_{n,s_{\mathit{max}}}\) broj particija broja \(n\) u kojima su svi sabirci manji ili jednaki od \(s_{\mathit{max}}\).
Bazu indukcije čini slučaj \(n=0\), jer broj nula ima samo jednu particiju koja ne sadrži sabirke. Dakle, važi da je \(p_{0,s_{\mathit{max}}} = 1\). Ako je \(n\) veće od nula i \(s_{\mathit{max}}=0\), tada ne postoji ni jedna particija, jer od sabiraka koji su svi jednaki nuli (jer svi moraju da budu manji ili jednaki \(s_{\mathit{max}}\)) ne možemo nikako napraviti neki pozitivan broj. Dakle, za \(n > 0\) važi da je \(p_{n,0} = 0\).
Induktivni korak možemo ostvariti na više načina. Najjednostavniji je sledeći. Prilikom izračunavanja \(p_{n, s_{\mathit{max}}}\) možemo razmatrati dva slučaja: da se u zbiru ne javlja sabirak \(s_{\mathit{max}}\) ili da se u zbiru javlja sabirak \(s_{\mathit{max}}\). Ako se u zbiru ne javlja sabirak \(s_{\mathit{max}}\), tada je najveći sabirak \(s_{\mathit{max}}-1\) i broj takvih particija je \(p_{n, s_{\mathit{max}}-1}\). Drugi slučaj je moguć samo kada je \(n \geq s_{\mathit{max}}\) i broj takvih particija je \(p_{n-s_{\mathit{max}}, s_{\mathit{max}}}\). Na osnovu ovoga, dobijamo narednu rekurzivnu funkciju.
// particije broja n u kojima je najveci sabirak jednak smax
int brojParticija(int n, int smax) {
if (n == 0) return 1;
if (smax == 0) return 0;
int broj = brojParticija(n, smax - 1);
if (n >= smax)
broj += brojParticija(n - smax, smax);
return broj;
}
int brojParticija(int n) {
// particije broja n u kojima je najveći sabirak jednak n
return brojParticija(n, n);
}#include <iostream>
using namespace std;
// particije broja n u kojima je najveci sabirak jednak smax
int brojParticija(int n, int smax) {
if (n == 0) return 1;
if (smax == 0) return 0;
int broj = brojParticija(n, smax - 1);
if (n >= smax)
broj += brojParticija(n - smax, smax);
return broj;
}
int brojParticija(int n) {
// particije broja n u kojima je najveći sabirak jednak n
return brojParticija(n, n);
}
int main() {
int n;
cin >> n;
cout << brojParticija(n) << endl;
}Rekurzivnu funkciju za izračunavanje broja particija možemo dobiti i tako što na tekuće mesto u particiji postavljamo sve moguće kandidate za proširivanje tekuće particije (to su svi brojevi \(s\) od \(1\) do manjeg od brojeva \(s_{\mathit{max}}\) i \(n\)) i nastavljamo generisanje particija broja \(n-s\) kod kojih je najveći sabirak jednak \(s\).
// particije broja n u kojima je najveći sabirak jednak smax
int brojParticija(int n, int smax) {
if (n == 0) return 1;
if (smax == 0) return 0;
int broj = 0;
for (int s = min(smax, n); s >= 1; s--)
broj += brojParticija(n - s, s);
return broj;
}
int brojParticija(int n) {
// particije broja n u kojima je najveći sabirak jednak n
return brojParticija(n, n);
}#include <iostream>
#include <algorithm>
using namespace std;
// particije broja n u kojima je najveći sabirak jednak smax
int brojParticija(int n, int smax) {
if (n == 0) return 1;
if (smax == 0) return 0;
int broj = 0;
for (int s = min(smax, n); s >= 1; s--)
broj += brojParticija(n - s, s);
return broj;
}
int brojParticija(int n) {
// particije broja n u kojima je najveći sabirak jednak n
return brojParticija(n, n);
}
int main() {
int n;
cin >> n;
cout << brojParticija(n) << endl;
}Sva rešenja zasnovana na prostoj rekurziji su neefikasna, jer dolazi do ponavljanja identičnih rekurzivnih poziva i mogu se popraviti dinamičkim programiranjem. Prikažimo to na primeru brojanja nerastuće uređenih permutacija u kojima vršimo dva rekurzivna poziva.
Krenimo sa memoizacijom. Uvodimo matricu dimenzije \((n+1) \times (n+1)\) koju popunjavamo vrednostima \(-1\), čime označavamo da rezultat poziva funkcije još nije poznat. Pre nego što krenemo sa izračunavanjem proveravamo da li je u matrici vrednost različita od \(-1\) i ako jeste, vraćamo tu upamćenu vrednost. Pre svake povratne vrednosti funkcije rezultat pamtimo u matrici. Fleksibilnosti radi, matricu možemo implementirati kao vektor vektora, a ako je brzina alokacije memorije bitan faktor a poznato je gornje ograničenje vrednosti \(n\), onda možemo upotrebiti i statički alociranu matricu.
int brojParticija(int n, int smax, vector<vector<int>>& memo) {
if (memo[n][smax] != -1)
return memo[n][smax];
if (n == 0) return memo[n][smax] = 1;
if (smax == 0) return memo[n][smax] = 0;
int broj = brojParticija(n, smax-1, memo);
if (n >= smax)
broj += brojParticija(n-smax, smax, memo);
return memo[n][smax] = broj;
}
int brojParticija(int n) {
vector<vector<int>> memo(n + 1);
for (int i = 0; i <= n; i++)
memo[i].resize(n+1, -1);
return brojParticija(n, n, memo);
}#include <iostream>
#include <vector>
using namespace std;
int brojParticija(int n, int smax, vector<vector<int>>& memo) {
if (memo[n][smax] != -1)
return memo[n][smax];
if (n == 0) return memo[n][smax] = 1;
if (smax == 0) return memo[n][smax] = 0;
int broj = brojParticija(n, smax-1, memo);
if (n >= smax)
broj += brojParticija(n-smax, smax, memo);
return memo[n][smax] = broj;
}
int brojParticija(int n) {
vector<vector<int>> memo(n + 1);
for (int i = 0; i <= n; i++)
memo[i].resize(n+1, -1);
return brojParticija(n, n, memo);
}
int main() {
int n;
cin >> n;
cout << brojParticija(n) << endl;
}Umesto memoizacije možemo upotrebiti i dinamičko programiranje naviše. Prikažimo tabelu vrednosti funkcije za \(n=7\).
n\smax 0 1 2 3 4 5 6 7 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 2 0 1 2 2 2 2 2 2 3 0 1 2 3 3 3 3 3 4 0 1 3 4 5 5 5 5 5 0 1 3 5 6 7 7 7 6 0 1 4 7 9 10 11 11 7 0 1 4 8 11 13 14 15
Na osnovu baze indukcije znamo da će svi elementi prve vrste biti jednaki \(1\), a da će u prvoj koloni svi elementi osim početnog biti jednaki \(0\). Jedan od načina da se matrica popunjava je postepeno uvećavajući vrednost \(n\), tj. popunjavajući vrstu po vrstu.
Element \(p_{n,s}\) zavisi od elemenata \(p_{n, s-1}\) i (ako je \(n \geq s\)) \(p_{n-s, s}\) i ako se vrste popunjavaju odozgo naniže i sleva nadesno, prilikom njegovog izračunavanja oba elementa od kojih zavisi su već izračunata, što daje korektan algoritam.
int brojParticija(int N) {
// alociramo matricu
vector<vector<int>> dp(N+1);
for (int n = 0; n <= N; n++)
dp[n].resize(N+1);
// popunjavamo prvu vrstu
for (int smax = 0; smax <= N; smax++)
dp[0][smax] = 1;
// popunjavamo preostale elemente prve kolone
for (int n = 1; n <= N; n++)
dp[n][0] = 0;
// popunjavamo jednu po jednu vrstu
for (int n = 1; n <= N; n++)
for (int smax = 1; smax <= N; smax++) {
dp[n][smax] = dp[n][smax-1];
if (n >= smax)
dp[n][smax] += dp[n-smax][smax];
}
return dp[N][N];
}#include <iostream>
#include <vector>
using namespace std;
int brojParticija(int N) {
// alociramo matricu
vector<vector<int>> dp(N+1);
for (int n = 0; n <= N; n++)
dp[n].resize(N+1);
// popunjavamo prvu vrstu
for (int smax = 0; smax <= N; smax++)
dp[0][smax] = 1;
// popunjavamo preostale elemente prve kolone
for (int n = 1; n <= N; n++)
dp[n][0] = 0;
// popunjavamo jednu po jednu vrstu
for (int n = 1; n <= N; n++)
for (int smax = 1; smax <= N; smax++) {
dp[n][smax] = dp[n][smax-1];
if (n >= smax)
dp[n][smax] += dp[n-smax][smax];
}
return dp[N][N];
}
int main() {
int n;
cin >> n;
cout << brojParticija(n) << endl;
return 0;
}I vremenska i memorijska složenost prethodnog algoritma je \(O(n^2)\). Iako se matrica popunjava vrstu po vrstu, to nije moguće popraviti (jer elementi zavise od elemenata koji se javljaju ne samo u prethodnoj, već i u ranijim vrstama, tako da je potrebno da istovremeno čuvamo sve prethodne vrste). Međutim, ako matricu popunjavamo kolonu po kolonu odozgo naniže, možemo dobiti memorijsku složenost \(O(n)\) – vremenska složenost ostaje \(O(n^2)\). Naime, svaki element zavisi od elementa u istoj vrsti u prethodnoj koloni i elementa u istoj koloni u nekoj od prethodnih vrsta, tako da ako kolone popunjavamo odozgo naniže, možemo čuvati samo dve uzastopne kolone. Zapravo, možemo čuvati i samo jednu kolonu, ako njeno popunjavanje organizujemo tako da se tokom ažuriranja svi elementi pre tekuće vrste odnose na vrednosti tekuće kolone, a od tekuće vrste do kraja odnose na vrednosti prethodne kolone. Primetimo da se u delu gde je \(n < s_{\mathit{max}}\), vrednosti između dve susedne kolone ne menjaju. Time dobijamo narednu optimizovanu implementaciju.
int brojParticija(int N) {
vector<int> dp(N+1, 0);
dp[0] = 1;
for (int smax = 1; smax <= N; smax++)
for (int n = smax; n <= N; n++)
dp[n] += dp[n-smax];
return dp[N];
}#include <iostream>
#include <vector>
using namespace std;
int brojParticija(int N) {
vector<int> dp(N+1, 0);
dp[0] = 1;
for (int smax = 1; smax <= N; smax++)
for (int n = smax; n <= N; n++)
dp[n] += dp[n-smax];
return dp[N];
}
int main() {
int n;
cin >> n;
cout << brojParticija(n) << endl;
return 0;
}Dinamičko programiranje se često primenjuje u rešavanju optimizacionih zadataka (zadataka u kojima se traži da se odredi najmanja ili najveća vrednost koja zadovoljava neki uslov). Da bi optimizacioni zadatak mogao da se rešava dinamičkim programiranjem, potrebno je formulisati njegovo rekurzivno rešenje, što znači da problem mora da zadovoljava takozvano svojstvo optimalne podstrukture. To znači da se optimalno rešenje polaznog problema može odrediti na osnovu optimalnih rešenja potproblema istog oblika, ali manje dimenzije.
Na primer, najkraći put izmeću tačke \(A\) i tačke \(B\) koji prolazi preko tačke \(C\) se dobija tako što se iskombinuju najkraći put između tačke \(A\) i tačke \(C\) i nakraći put između tačke \(C\) i tačke \(B\), što znači da problem određivanja najkraćih puteva ima svojstvo optimalne podstrukture i može se rešavati dinamičkim programiranjem (na toj tehnici je zasnovan Dajkstrin algoritam, koji je jedan od najčuvenijih algoritama za rešvanje tog problema).
Međutim, najjeftiniji avionski let od aerodroma \(A\) do aerodroma \(B\) preko aerodroma \(C\) ne mora da bude kombinacija najjeftinijih letova od \(A\) do \(C\) i od \(C\) do \(B\) (zbog posebnih popusta koje avio-kompanije nude za povezane letove), tako da se problem određivanja najjeftinijeg leta nema svojstvo optimalne podstrukture i ne može se rešavati dinamičkim programiranjem.
Date su vrednosti \(n\) vrsta novčića. Napisati program koji određuje minimalan broj novčića potrebnih za isplatu datog iznosa \(S\), pri čemu se može se koristiti i više novčića iste vrste i svake vrste novčića ima proizvoljno mnogo. Vrednosti novčića i iznos za isplatu dati su u istoj valuti.
Prva linija standardnog ulaza zadrži prirodan broj \(S\) (\(S \leq 1000\)). Druga linija sadrži prirodan broj \(n\) (\(n \leq 100\)), u sledećih \(n\) linija nalaze se prirodni brojevi koji predstavljaju vrednosti za svaku vrstu novčića, svaka vrednost u posebnoj liniji.
Na standardnom izlazu prikazati u jednoj liniji minimalan broj novčića potreban ѕa isplatu iznosa \(S\).
7 3 1 3 2
3
Isplata za iznos \(7\) sa najmanje novčića je \(3, 3, 1\).
12 3 1 9 6
2
Isplata za iznos \(12\) sa najmanje novčića je \(6, 6\).
Iznos \(0\) se može naplatiti sa \(0\) novčića. U suprotnom, ako je niz raspoloživih novčića prazan, iznos nije moguće naplatiti. U suprotnom analiziramo da li je u isplatu uključen bar jedan novčić poslednje vrste. Ako nije, pokušavamo da naplatimo iznos bez korišćenja poslednje vrste novčića, tj. sa prefiksnom niza novčića bez poslednjeg elementa. Ako jeste, tada iznos mora biti veći ili jednak od novčića poslednje vrste i tada preostali iznos pokušavamo da naplatimo ponovo korišćenjem svih vrsta novčića. Ako sa sa \(f(n, s)\) najmanji broj novčića da se naplati iznos \(s\) pomoću novčića koji pripadaju prefiksu dužine \(n\) polaznog niza, tada važi:
\[\begin{align*} f(n, 0) &= 0, \\ f(0, s) &= +\infty, \quad \textrm{za}\ s > 0\\ f(n, s) &= f(n-1, s), \quad \textrm{za}\ s < v_{n-1}\\ f(n, s) &= \min{(f(n-1, s), 1 + f(n, s-v_{n-1}))}, \quad\ \textrm{za}\ s \geq v_{n-1} \end{align*}\]
Na osnovu ovoga je veoma jednostavno definisati rekurzivnu funkciju koja izračunava traženi najmanji broj novčića.
// najmanji broj novčića potreban da se naplati iznos S
// pomoću n vrednosti novčića datih u nizu v
int minBrojNovcica(int v[], int n, int s) {
// iznos 0 se plaća sa 0 novčića
if (s == 0)
return 0;
// ako nema novčića pozitivan iznos nije moguće platiti
if (n == 0)
return INF;
// rešenje ako se ne uzme ni jedan novčić poslednje vrste
int br = minBrojNovcica(v, n-1, s);
// ako je iznos veći od novčića poslednje vrste
if (s >= v[n-1])
// rešenje ako se uzme bar jedan novčić poslednje vrste
br = min(br, minBrojNovcica(v, n, s - v[n-1]) + 1);
// vraćamo rezultat
return br;
}#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_S = 2000;
const int MAX_V = 100;
const int INF = MAX_S + 1;
// najmanji broj novčića potreban da se naplati iznos S
// pomoću n vrednosti novčića datih u nizu v
int minBrojNovcica(int v[], int n, int s) {
// iznos 0 se plaća sa 0 novčića
if (s == 0)
return 0;
// ako nema novčića pozitivan iznos nije moguće platiti
if (n == 0)
return INF;
// rešenje ako se ne uzme ni jedan novčić poslednje vrste
int br = minBrojNovcica(v, n-1, s);
// ako je iznos veći od novčića poslednje vrste
if (s >= v[n-1])
// rešenje ako se uzme bar jedan novčić poslednje vrste
br = min(br, minBrojNovcica(v, n, s - v[n-1]) + 1);
// vraćamo rezultat
return br;
}
int main() {
// učitavamo iznos i niz novčića
int S;
cin >> S;
int n;
cin >> n;
int v[MAX_V];
for(int i = 0; i < n; i++)
cin >> v[i];
// izračunavamo i ispisujemo minimum
int br = minBrojNovcica(v, n, S);
cout << (br == INF ? -1 : br) << endl;
return 0;
}Jasno je da u prethodnoj funkciji može doći do ponavljanja istih rekurzivnih poziva, što se može rešiti tehnikom dinamičkog programiranja. Pošto funkcija ima dva promenljiva parametra, moguće je upotrebiti matricu za memoizaciju.
// matrica koju koristimo za memoizaciju
int memo[MAX_V][MAX_S + 1];
int minBrojNovcica(int v[], int n, int s){
// već smo računali vrednost za (n, s)
if (memo[n][s] != 0)
return memo[n][s];
if (s == 0)
return memo[n][s] = 0;
if (n == 0)
return memo[n][s] = INF;
int br = minBrojNovcica(v, n-1, s);
if (s >= v[n-1])
br = min(br, minBrojNovcica(v, n, s - v[n-1]) + 1);
// vraćamo rezultat pamteći ga pritom u nizu
return memo[n][s] = br;
}#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_V = 100;
const int MAX_S = 2000;
const int INF = MAX_S + 1;
// matrica koju koristimo za memoizaciju
int memo[MAX_V][MAX_S + 1];
int minBrojNovcica(int v[], int n, int s){
// već smo računali vrednost za (n, s)
if (memo[n][s] != 0)
return memo[n][s];
if (s == 0)
return memo[n][s] = 0;
if (n == 0)
return memo[n][s] = INF;
int br = minBrojNovcica(v, n-1, s);
if (s >= v[n-1])
br = min(br, minBrojNovcica(v, n, s - v[n-1]) + 1);
// vraćamo rezultat pamteći ga pritom u nizu
return memo[n][s] = br;
}
int main() {
// učitavamo iznos i niz vrednosti novčića
int S, N;
int v[MAX_V];
cin >> S >> N;
for (int i = 0; i < N; i++)
cin >> v[i];
// izračunavamo i ispisujemo najmanji broj novčića
int br = minBrojNovcica(v, N, S);
cout << (br == INF ? -1 : br) << endl;
return 0;
}Prilikom dinamičkog programiranja naviše, matricu možemo popunjavati vrstu po vrstu i tako smanjiti memorijsku složenost.
Vremenska složenost ovog rešenja je \(O(S \cdot N)\), gde je \(S\) iznos, a \(N\) broj vrsta novčića, dok je memorijska složenost \(O(S)\).
int minBrojNovcica(int v[], int N, int S) {
int dp[MAX_S + 1];
// analizu pokrećemo sa 0 vrsta novčića
dp[0] = 0;
for (int s = 1; s <= S; s++)
dp[s] = INF;
// uključujemo jednu po jednu vrstu novčića
for (int n = 1; n <= N; n++) {
// ažuriramo vrednosti svih iznosa u čijem plaćanju može
// učestvovati iznos v[n-1]
for (int s = v[n-1]; s <= S; s++)
dp[s] = min(dp[s], dp[s - v[n-1]] + 1);
}
return dp[S];
}#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_V = 100;
const int MAX_S = 2000;
const int INF = MAX_S + 1;
int minBrojNovcica(int v[], int N, int S) {
int dp[MAX_S + 1];
// analizu pokrećemo sa 0 vrsta novčića
dp[0] = 0;
for (int s = 1; s <= S; s++)
dp[s] = INF;
// uključujemo jednu po jednu vrstu novčića
for (int n = 1; n <= N; n++) {
// ažuriramo vrednosti svih iznosa u čijem plaćanju može
// učestvovati iznos v[n-1]
for (int s = v[n-1]; s <= S; s++)
dp[s] = min(dp[s], dp[s - v[n-1]] + 1);
}
return dp[S];
}
int main() {
int S, N;
int v[MAX_V];
cin >> S >> N;
for (int i = 0; i < N; i++)
cin >> v[i];
int br = minBrojNovcica(v, N, S);
cout << (br == INF ? -1 : br) << endl;
return 0;
}Drugo moguće rešenje razmatra sve mogućnosti za poslednji upotrebljeni novčić. To može biti bilo koji novčić koji je manji od tekućeg iznosa koji treba naplatiti, nakon čega se preostali iznos i dalje naplaćuje pomoću svih mogućih novčića. Ako sa \(f(s)\) obeležimo najmanji broj novčića potrebnih da se naplati iznos \(s\), pri čemu se mogu koristiti svi raspoloživi novčići, dobijamo sledeću rekurentnu vezu.
\[\begin{align*} f(0) &= 0, \\ f(s) &= \min_{v_i \leq s}{(1 + f(s-v_i))} \end{align*}\]
Ako je iznos pozitivan, ali manji od svih novčića koje imamo na raspolaganju tada je minimum jednak \(+\infty\). I u ovom slučaju veoma jednostavno možemo definisati rekurzivnu funkciju.
int minBrojNovcica(int v[], int n, int s) {
// iznos 0 se naplaćuje sa 0 novčića
if (s == 0)
return 0;
// minimalni broj novčića da se naplati iznos s
// (pretpostavljamo da iznos nije moguće naplatiti)
int br = INF;
// razmatramo sve mogućnosti za poslednji novčić
for (int i = 0; i < n; i++)
// da li je u iznos s moguće uključiti novčić i?
if (v[i] <= s)
// određujemo rekurzivno broj novčića za preostali iznos
// ažuriramo minimum ako je to potrebno
br = min(br, minBrojNovcica(v, n, s-v[i]) + 1);
// vraćamo rezultat
return br;
}#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_S = 2000;
const int MAX_V = 100;
const int INF = MAX_S + 1;
int minBrojNovcica(int v[], int n, int s) {
// iznos 0 se naplaćuje sa 0 novčića
if (s == 0)
return 0;
// minimalni broj novčića da se naplati iznos s
// (pretpostavljamo da iznos nije moguće naplatiti)
int br = INF;
// razmatramo sve mogućnosti za poslednji novčić
for (int i = 0; i < n; i++)
// da li je u iznos s moguće uključiti novčić i?
if (v[i] <= s)
// određujemo rekurzivno broj novčića za preostali iznos
// ažuriramo minimum ako je to potrebno
br = min(br, minBrojNovcica(v, n, s-v[i]) + 1);
// vraćamo rezultat
return br;
}
int main() {
// učitavamo iznos i niz novčića
int N, S;
int v[MAX_V];
cin >> S >> N;
for(int i = 0; i < N; i++)
cin >> v[i];
// izračunavamo i ispisujemo minimum
int br = minBrojNovcica(v, N, S);
cout << (br == INF ? -1 : br) << endl;
return 0;
}Pošto dolazi do ponavljanja istih rekurzivnih poziva potrebno je da upotrebimo dinamičko programiranje. Pošto je samo jedan parametar promenljiv, za memoizaciju je dovoljno samo da koristimo niz.
// niz koji koristimo za memoizaciju (inicijalizovan na 0)
int memo[MAX_S + 1];
int minBrojNovcica(int v[], int n, int S) {
// vraćamo ranije izračunati rezultat za iznos S
if (memo[S] != 0)
return memo[S];
if (S == 0)
return memo[S] = 0;
int br = INF;
for (int i = 0; i < n; i++)
if (v[i] <= S)
br = min(br, minBrojNovcica(v, n, S-v[i]) + 1);
// vraćamo rezultat, pamteći ga pritom u nizu memo
return memo[S] = br;
}#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_S = 2000;
const int MAX_V = 100;
const int INF = MAX_S + 1;
// niz koji koristimo za memoizaciju (inicijalizovan na 0)
int memo[MAX_S + 1];
int minBrojNovcica(int v[], int n, int S) {
// vraćamo ranije izračunati rezultat za iznos S
if (memo[S] != 0)
return memo[S];
if (S == 0)
return memo[S] = 0;
int br = INF;
for (int i = 0; i < n; i++)
if (v[i] <= S)
br = min(br, minBrojNovcica(v, n, S-v[i]) + 1);
// vraćamo rezultat, pamteći ga pritom u nizu memo
return memo[S] = br;
}
int main() {
// učitavamo iznos i niz novčića
int n, S;
int v[MAX_V];
cin >> S >> n;
for(int i = 0; i < n; i++)
cin >> v[i];
// izračunavamo i ispisujemo minimum
int br = minBrojNovcica(v, n, S);
cout << (br == INF ? -1 : br) << endl;
return 0;
}Prilikom dinamičkog programiranja naviše niz popunjavamo sleva nadesno.
int minBrojNovcica(int v[], int n, int S) {
int dp[MAX_S + 1];
// iznos 0 se naplaćuje sa 0 novčića
dp[0] = 0;
// analiziramo sve pozitivne iznose do S
for (int s = 1; s <= S; s++) {
// analiziramo uključivanje jedne po jedne vrsta novčića
dp[s] = INF;
for (int i = 0; i < n; i++)
if (v[i] <= s)
dp[s] = min(dp[s], dp[s-v[i]] + 1);
}
return dp[S];
}#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_S = 2000;
const int MAX_V = 100;
const int INF = MAX_S + 1;
int minBrojNovcica(int v[], int n, int S) {
int dp[MAX_S + 1];
// iznos 0 se naplaćuje sa 0 novčića
dp[0] = 0;
// analiziramo sve pozitivne iznose do S
for (int s = 1; s <= S; s++) {
// analiziramo uključivanje jedne po jedne vrsta novčića
dp[s] = INF;
for (int i = 0; i < n; i++)
if (v[i] <= s)
dp[s] = min(dp[s], dp[s-v[i]] + 1);
}
return dp[S];
}
int main() {
// učitavamo iznos i niz novčića
int S;
cin >> S;
int n;
cin >> n;
int v[MAX_V];
for(int i = 0; i < n; i++)
cin >> v[i];
// izračunavamo i ispisujemo minimum
int br = minBrojNovcica(v, n, S);
cout << (br == INF ? -1 : br) << endl;
return 0;
}Programer se seli iz jedne kompanije u drugu i želi da ponese predmete iz svoje stare kancelarije, međutim, na raspolaganju samo ima jedan veliki ranac u koji možda ne mogu da stanu svi predmeti. Ako je poznata masa i vrednost svakog od predmeta i ako je poznata nosivost ranca, napiši program koji određuje maksimalnu vrednost skupa predmeta koje programer može da prenese u rancu.
Sa standardnog ulaza se unosi nosivost ranca (ceo broj između \(1\) i \(150\)), zatim broj predmeta \(n\) (ceo broj između \(1\) i \(30\)), zatim u narednih \(n\) redova mase i cene predmeta (mase su celi brojevi između \(1\) i \(10\), a cene realni brojevi između \(1,0\) i \(100,0\), zaokruženi na dve decimale).
Na standardni izlaz ispisati najveću vrednost predmeta koji se mogu preneti u rancu, zaokruženu na dve decimale.
5 3 1 6.00 2 10.00 3 12.00
22.00
Najveća vrednost se dobije ako se prenesu predmeti mase 2 i mase 3 (vrednost je tada \(10,0 + 12,0 = 22,0\)).
15 5 12 4.00 2 2.00 1 2.00 1 1.00 4 10.00
15.00
Najveća vrednost se dobije ako se prenesu predmeti masa 2, 1, 1 i 4 kilograma (vrednost je tada \(2,0 + 2,0 + 1,0 + 10,0 = 15,0\)).
Iako neke varijante problema ranca dopuštaju određena gramziva rešenja, u ovoj varijanti u kojoj se predmeti ne mogu deliti već se uzimaju u celini (tzv. 0-1 varijanta problema ranca), potrebno je napraviti algoritam zasnovan na nekom obliku (optimizovane) iscrpne pretrage. Nije teško konstruisati primere koji pokazuju da gramzivi algoritam koji bi u ranac prvo stavljao najvredniji predmet ili koji bi prvo stavljao predmet koji je najvredniji po jedinici mase ne dovode uvek do optimalnog rešenja.
Rešenje grubom silom podrazumeva da se ispitaju svi mogući podskupovi predmeta i da se pronađe onaj koji može da stane u ranac a ima najveću vrednost.
Nabrajanje podskupova može da se izvrši rekurzivnom funkcijom, čiji je parametar dužina niza predmeta \(n\).
Ako je niz predmeta prazan (ako je \(n=0\)), tada je maksimalna vrednost koja se može spakovati jednaka nuli.
Ako niz predmeta nije prazan (ako je \(n>0\)), tada analiziramo mogućnost da njegov poslednji element izostavimo ili da ga spakujemo u ranac. U prvom slučaju rekurzivnu funkciju pozivamo za istu vrednost kapaciteta ranca i dužinu niza \(n-1\). Drugi slučaj je moguć samo ako je masa poslednjeg predmeta manja od kapaciteta ranca. U tom slučaju na rezultat rekurzivnog poziva gde je nosivost ranca umanjena za masu tog predmeta i gde je prosleđena dužina niza \(n-1\) dodajemo cenu poslednjeg predmeta. Najveću vrednost dobijamo tako što izračunamo maksimum dva analizirana slučaja (kada poslednji predmet nije i kada jeste stavljen u ranac).
Ako sa \(f(n, W)\) obeležimo maksimalnu vrednost koja se može dobiti tako što se neki od prvih \(n\) predmeta spakuju u ranac nosivosti \(W\), važe sledeće veze:
\[\begin{eqnarray*} f(0, W) &=& 0\\ f(n, W) &=& \max{(f(n-1, W), f(n-1, W-w_{n-1})) + v_{n-1}}, \quad\textrm{za}\ w_{n-1} \leq W\\ f(n, W) &=& f(n-1, W), \quad\textrm{za}\ w_{n-1} > W \end{eqnarray*}\]
Primetimo da se rekurzivnim pozivima traži optimum za skup bez poslednjeg predmeta, što je u redu, jer je za globalni optimum neophodno i da su predmeti iz tog podskupa odabrani optimalno (zadovoljen je uslov optimalne podstrukture).
U naivnoj rekurzivnoj implementaciji dolazi do preklapanja identičnih rekurzivnih poziva, pa je ta implementacija veoma neefikasna (složenost najgoreg slučaja joj je eksponencijalna).
double maxCena(const vector<int>& mase,
const vector<double>& cene,
int nosivost, int n) {
vector<double> dp(nosivost + 1);
dp[0] = 0.0;
for (int N = 1; N <= n; N++)
for (int M = nosivost; M >= 0; M--)
if (mase[N-1] <= M)
dp[M] = max(dp[M], dp[M - mase[N-1]] + cene[N-1]);
return dp[nosivost];
}#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
double maxCena(const vector<int>& mase,
const vector<double>& cene,
int nosivost, int n) {
vector<double> dp(nosivost + 1);
dp[0] = 0.0;
for (int N = 1; N <= n; N++)
for (int M = nosivost; M >= 0; M--)
if (mase[N-1] <= M)
dp[M] = max(dp[M], dp[M - mase[N-1]] + cene[N-1]);
return dp[nosivost];
}
int main() {
int nosivost;
cin >> nosivost;
int n;
cin >> n;
vector<int> mase(n);
vector<double> cene(n);
for (int i = 0; i < n; i++)
cin >> mase[i] >> cene[i];
cout << fixed << showpoint << setprecision(2)
<< maxCena(mase, cene, nosivost, n) << endl;
return 0;
}Rešenje problema ponovljenih rekurzivnih poziva, naravno, dolazi u obliku dinamičkog programiranja (bilo memoizacije, bilo dinamičkog programiranja naviše). Pošto imamo dva promenljiva parametra (broj predmeta \(n\) i nosivost ranca \(W\)), alociramo takvu matricu da svakoj vrsti odgovara jedan prefiks niza predmeta, a svakoj koloni jedna nosivost. Matricu možemo popunjavati vrstu po vrstu.
Primer 8.3.1. Prikažimo rad algoritma na primeru kada je nosivost ranca 15 kilograma i kada imamo 5 predmeta čije su mase i cene redom \((12, 4.00)\), \((2, 2.00)\), \((1, 2.00)\), \((1, 1.00)\) i \((4, 10.00)\).
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ---------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 2 | 0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 3 | 0 2 2 4 4 4 4 4 4 4 4 4 4 6 6 8 4 | 0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 5 | 0 2 3 2 10 12 13 14 15 15 15 15 15 15 15 15
Vrednost 15 u donjem desnom uglu ukazuje na to da ako imamo ranac nosivosti 15 kilograma i svih 5 predmeta na raspolaganju, tada je najveća vrednost koju možemo poneti 15. Dalje, na primer, vrednosti u vrsti 2 ukazuju na maksimalne vrednosti koje možemo poneti ako uzimamo samo neke od prva dva predmeta (to su onaj mase 12 i vrednosti 4,0 i onaj mase 2 i vrednosti 2,0) Ako je nosivost manja od 2, nijedan od ova dva predmeta ne može biti spakovan. Ako je nosivost između 2 i 11 tada može biti spakovan samo predmet vrednosti 2,0. Ako je nosivost 12 ili 13, tada nam se više isplati da spakujemo predmet mase 12 i vrednost 4,0. Kada nosivost pređe 14, tada može zapakovati oba predmeta, pa je ukupna vrednost 6,0.
Ovim smo dobili algoritam čija je i vremenska i memorijska složenost \(O(n\cdot W)\) gde je \(n\) broj predmeta, a \(W\) nosivost ranca.
Primetimo da je veoma važno bila pretpostavka da su nosivost ranca i mase predmeta celobrojne. Takođe, obratimo pažnju na to da iako deluje da smo ovaj problem rešili u polinomskoj vremenskoj složenosti, to zapravo nije slučaj. Naime, složenost u ovom slučaju ne zavisi i nije izražena samo u terminima veličine ulaza, već u terminima vrednosti na ulazu (vrednosti nosivosti ranca). Za ovakve algoritme se kaže da su pseudo-polinomski. Veličina ulaza vezanog za broj \(W\) odgovara broju cifara broja \(W\) (npr. broju binarnih cifara upotrebljenih u zapisu), a vreme izvršavanja algoritma eksponencijalno raste u odnosu na taj broj. Za veće vrednosti \(W\) dobili bismo veoma neefikasan algoritam (i što se tiče utrošene memorije i što se tiče vremena izvršavanja).
double maxCena(const vector<int>& mase,
const vector<double>& cene,
int nosivost, int n) {
vector<vector<double>> dp(nosivost + 1);
for (int M = 0; M <= nosivost; M++) {
dp[M].resize(n+1);
dp[M][0] = 0.0;
}
for (int N = 1; N <= n; N++) {
for (int M = 0; M <= nosivost; M++) {
dp[M][N] = dp[M][N-1];
if (mase[N-1] <= M)
dp[M][N] = max(dp[M][N-1],
dp[M-mase[N-1]][N-1] + cene[N-1]);
}
}
return dp[nosivost][n];
}#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
double maxCena(const vector<int>& mase,
const vector<double>& cene,
int nosivost, int n) {
vector<vector<double>> dp(nosivost + 1);
for (int M = 0; M <= nosivost; M++) {
dp[M].resize(n+1);
dp[M][0] = 0.0;
}
for (int N = 1; N <= n; N++) {
for (int M = 0; M <= nosivost; M++) {
dp[M][N] = dp[M][N-1];
if (mase[N-1] <= M)
dp[M][N] = max(dp[M][N-1],
dp[M-mase[N-1]][N-1] + cene[N-1]);
}
}
return dp[nosivost][n];
}
int main() {
int nosivost;
cin >> nosivost;
int n;
cin >> n;
vector<int> mase(n);
vector<double> cene(n);
for (int i = 0; i < n; i++)
cin >> mase[i] >> cene[i];
cout << fixed << showpoint << setprecision(2)
<< maxCena(mase, cene, nosivost, n) << endl;
return 0;
}Možemo primetiti da elementi svake vrste zavise samo od prethodne, tako da ne moramo čuvati celu matricu, već samo tekuću vrstu. Ažuriranje vrste tada vršimo s njenog desnog kraja.
Ovom optimizacijom se memorijska složenost smanjuje na \(O(W)\), a vremenska složenost ostaje \(O(n\cdot W)\). Primetimo da vremenska, ali i memorijska složenost ostaje eksponencijalna u odnosu na veličinu ulaza (broj bitova potrebnih za zapis vrednosti \(W\)).
double maxCena(const vector<int>& mase,
const vector<double>& cene,
int nosivost, int n) {
if (n == 0)
return 0.0;
double cenaBez = maxCena(mase, cene, nosivost, n-1);
if (mase[n-1] > nosivost)
return cenaBez;
double cenaSa = maxCena(mase, cene, nosivost-mase[n-1], n-1) +
cene[n-1];
return max(cenaBez, cenaSa);
}#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
double maxCena(const vector<int>& mase,
const vector<double>& cene,
int nosivost, int n) {
if (n == 0)
return 0.0;
double cenaBez = maxCena(mase, cene, nosivost, n-1);
if (mase[n-1] > nosivost)
return cenaBez;
double cenaSa = maxCena(mase, cene, nosivost-mase[n-1], n-1) +
cene[n-1];
return max(cenaBez, cenaSa);
}
int main() {
int nosivost;
cin >> nosivost;
int n;
cin >> n;
vector<int> mase(n);
vector<double> cene(n);
for (int i = 0; i < n; i++)
cin >> mase[i] >> cene[i];
cout << fixed << showpoint << setprecision(2)
<< maxCena(mase, cene, nosivost, n) << endl;
return 0;
}Edit-rastojanje između dve niske se definiše u terminima operacija umetanja, brisanja i izmena slova prve reči kojima se može dobiti druga reč. Svaka od ove tri operacije ima svoju cenu. Definisati program koji izračunava najmanju cenu operacija kojima se od prve niske može dobiti druga. Na primer, ako je cena svake operacije jedinična, tada se niska zdravo može pretvoriti u bravo! najefikasnije operacijom izmene slova z u b, brisanja slova d i umetanja karaktera !.
Sa standardnog ulaza se učitavaju dve niske dužine najviše 100 karaktera, a zatim cene operacije umetanja, brisanja i izmene (prirodni brojevi od 1 do 10, svaki u posebnom redu).
Na standardni izlaz ispisati traženu vrednost edit-rastojanja.
zdravo bravo! 1 1 1
3
kitten sitting 1 2 3
7
Izvedimo prvo induktivno-rekurzivnu konstrukciju.
Ako je prva niska prazna, najefikasniji način da se od nje dobije druga niska je da se umetne jedan po jedan karakter druge niske, tako da je minimalna cena jednaka proizvodu cene operacije umetanja i broja karaktera druge niske.
Ako je druga niska prazna, najefikasniji način da se od prve niske dobije prazna je da se jedan po jedan njen karakter izbriše, tako da je minimalna cena jednaka proizvodu cene operacije brisanja i broja karaktera prve niske.
Induktivna hipoteza će biti da umemo da rešimo problem za bilo koja dva prefiksa prve i druge niske.
Ako su poslednja slova prve i druge niske jednaka, onda je potrebno pretvoriti prefiks bez poslednjeg slova prve niske u prefiks bez poslednjeg slova druge niske.
Ako nisu, onda imamo tri mogućnosti.
Na osnovu ovoga lako možemo definisati rekurzivnu funkciju koja izračunava edit-rastojanje. Da nam se niske ne bi menjale tokom rekurzije (što može biti sporo), efikasnije je da niske prosleđujemo u neizmenjenom obliku i da samo prosleđujemo brojeve karaktera njihovih prefiksa koji se trenutno razmatraju.
U direktnoj rekurzivnoj implementaciji dolazi do velikog broja ponovljenih rekurzivnih poziva, što dovodi do veoma loše (eksponencijalne) složenosti.
int editRastojanje(const string& s1, const string& s2,
int n1, int n2) {
if (n1 == 0)
return n2 * cenaUmetanja;
if (n2 == 0)
return n1 * cenaBrisanja;
if (s1[n1-1] == s2[n2-1])
return editRastojanje(s1, s2, n1-1, n2-1);
int r1 = editRastojanje(s1, s2, n1-1, n2) + cenaUmetanja;
int r2 = editRastojanje(s1, s2, n1, n2-1) + cenaBrisanja;
int r3 = editRastojanje(s1, s2, n1-1, n2-1) + cenaIzmene;
return min({r1, r2, r3});
}
int editRastojanje(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
return editRastojanje(s1, s2, n1, n2);
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int cenaUmetanja, cenaBrisanja, cenaIzmene;
int editRastojanje(const string& s1, const string& s2,
int n1, int n2) {
if (n1 == 0)
return n2 * cenaUmetanja;
if (n2 == 0)
return n1 * cenaBrisanja;
if (s1[n1-1] == s2[n2-1])
return editRastojanje(s1, s2, n1-1, n2-1);
int r1 = editRastojanje(s1, s2, n1-1, n2) + cenaUmetanja;
int r2 = editRastojanje(s1, s2, n1, n2-1) + cenaBrisanja;
int r3 = editRastojanje(s1, s2, n1-1, n2-1) + cenaIzmene;
return min({r1, r2, r3});
}
int editRastojanje(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
return editRastojanje(s1, s2, n1, n2);
}
int main() {
string s1, s2;
cin >> s1 >> s2;
cin >> cenaUmetanja >> cenaBrisanja >> cenaIzmene;
cout << editRastojanje(s1, s2) << endl;
return 0;
}Rešenje direktnom rekurzijom je, naravno, izrazito neefikasno zbog preklapajućih rekurzivnih poziva. Algoritam dinamičkog programiranja naviše za ovaj problem poznat je pod imenom Vagner-Fišerov algoritam. Rezultate za prefikse dužine \(i\) i \(j\) pamtićemo u matrici na polju \((i, j)\). Dakle, ako su dužine niski \(n_1\) i \(n_2\), potrebna nam je matrica dimenzije \((n_1 + 1) \times (n_2 + 1)\), a konačan rezultat će se nalaziti na mestu \((n_1, n_2)\). Ako matricu popunjavamo vrstu po vrstu, sleva nadesno, prilikom izračunavanja elementa na poziciji \((i, j)\), biće izračunati svi elementi matrice od kojeg on zavisi (a to su \((i-1, j-1)\), \((i-1, j)\) i \((i, j-1)\)).
Primer 8.3.2. Pod pretpostavkom da su cene jedinične, za niske zdravo i bravo! dobija se sledeća matrica.
b r a v o ! 0 1 2 3 4 5 6 ------------- 0|0 1 2 3 4 5 6 z1|1 1 2 3 4 5 6 d2|2 2 2 3 4 5 6 r3|3 3 2 3 4 5 6 a4|4 4 3 2 3 4 5 v5|5 5 4 3 2 3 4 o6|6 6 5 4 3 2 3
Pošto se tokom rada algoritma popunjava matrica dimenzije \((n_1+1) \times (n_2+1)\), a svako polje matrice se popunjava u vremenu \(O(1)\), ukupna vremenska i memorijska složenost algoritma je \(O(n_1\cdot n_2)\).
int editRastojanje(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<vector<int>> dp(n1+1);
for (int i = 0; i <= n1; i++)
dp[i].resize(n2+1);
dp[0][0] = 0;
for (int i = 0; i <= n1; i++)
dp[i][0] = i * cenaBrisanja;
for (int j = 0; j <= n2; j++)
dp[0][j] = j * cenaUmetanja;
for (int i = 1; i <= n1; i++)
for (int j = 1; j <= n2; j++) {
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1];
else {
int r1 = dp[i-1][j] + cenaUmetanja;
int r2 = dp[i][j-1] + cenaBrisanja;
int r3 = dp[i-1][j-1] + cenaIzmene;
dp[i][j] = min({r1, r2, r3});
}
}
return dp[n1][n2];
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int cenaUmetanja, cenaBrisanja, cenaIzmene;
int editRastojanje(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<vector<int>> dp(n1+1);
for (int i = 0; i <= n1; i++)
dp[i].resize(n2+1);
dp[0][0] = 0;
for (int i = 0; i <= n1; i++)
dp[i][0] = i * cenaBrisanja;
for (int j = 0; j <= n2; j++)
dp[0][j] = j * cenaUmetanja;
for (int i = 1; i <= n1; i++)
for (int j = 1; j <= n2; j++) {
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1];
else {
int r1 = dp[i-1][j] + cenaUmetanja;
int r2 = dp[i][j-1] + cenaBrisanja;
int r3 = dp[i-1][j-1] + cenaIzmene;
dp[i][j] = min({r1, r2, r3});
}
}
return dp[n1][n2];
}
int main() {
string s1, s2;
cin >> s1 >> s2;
cin >> cenaUmetanja >> cenaBrisanja >> cenaIzmene;
cout << editRastojanje(s1, s2, cenaUmetanja, cenaBrisanja, cenaIzmene) << endl;
return 0;
}Na osnovu postavke zadatka, nije potrebno odrediti same izmene, već samo rastojanje (na primer, ako se vrši provera da li su dve niske bliske prilikom pretrage u kojoj se dopušta da je korisnik napravio i nekoliko slovnih grešaka). Pošto elementi tekućeg reda zavise samo od prethodnog, možemo izvršiti memorijsku optimizaciju i istovremeno čuvati samo jedan red. Tokom ažuriranja elementa na poziciji \(j\) njegov deo na pozicijama strogo manjim od \(j\) će čuvati elemente tekućeg reda \(i\), deo od pozicije \(j\) nadalje će čuvati elemente prethodnog reda \(i-1\). Promenljiva prethodni će čuvati vrednost sa polja \((i-1, j-1)\), a promenljiva tekuci će čuvati vrednost sa polja \((i-1, j)\).
Vremenska složenost nakon ove optimizacije je \(O(n_1\cdot n_2)\), dok se memorijska složenost može spustiti na \(O(\min(n_1, n_2))\) (tako što se odabere da li će se popunjavati vrsta po vrsta ili kolona po kolona).
int editRastojanje(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<int> dp(n2 + 1);
dp[0] = 0;
for (int j = 0; j <= n2; j++)
dp[j] = j * cenaUmetanja;
for (int i = 1; i <= n1; i++) {
int prethodni = dp[0];
dp[0] = i * cenaBrisanja;
for (int j = 1; j <= n2; j++) {
int tekuci = dp[j];
if (s1[i-1] == s2[j-1])
dp[j] = prethodni;
else {
int r1 = tekuci + cenaUmetanja;
int r2 = dp[j-1] + cenaBrisanja;
int r3 = prethodni + cenaIzmene;
dp[j] = min({r1, r2, r3});
}
prethodni = tekuci;
}
}
return dp[n2];
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int cenaUmetanja, cenaBrisanja, cenaIzmene;
int editRastojanje(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<int> dp(n2 + 1);
dp[0] = 0;
for (int j = 0; j <= n2; j++)
dp[j] = j * cenaUmetanja;
for (int i = 1; i <= n1; i++) {
int prethodni = dp[0];
dp[0] = i * cenaBrisanja;
for (int j = 1; j <= n2; j++) {
int tekuci = dp[j];
if (s1[i-1] == s2[j-1])
dp[j] = prethodni;
else {
int r1 = tekuci + cenaUmetanja;
int r2 = dp[j-1] + cenaBrisanja;
int r3 = prethodni + cenaIzmene;
dp[j] = min({r1, r2, r3});
}
prethodni = tekuci;
}
}
return dp[n2];
}
int main() {
string s1, s2;
cin >> s1 >> s2;
cin >> cenaUmetanja >> cenaBrisanja >> cenaIzmene;
cout << editRastojanje(s1, s2) << endl;
return 0;
}Na osnovu popunjene matrice lako je rekonstruisati i sam niz koraka koji prvu nisku transformiše u drugu. Krećemo od donjeg desnog ugla matrice i krećemo se unazad. U svakom koraku proveravamo kako smo došli na tekuću poziciju i u skladu sa tim korak ubacujemo u niz (vektor). Na kraju, kada stignemo do gornjeg levog ugla, niz koraka ispisujemo unazad.
Primer 8.3.3. U tekućem primeru na polje (6, 6) smo stigli sa polja (6, 5) što znači da je poslednji korak umetanje karaktera !. Na polje (6, 5) smo stigli sa polja (5, 4) pri čemu nije vršen nikakva izmena. Slično, na polje (5, 4) smo stigli sa (4, 3), na polje (4, 3) smo stigli sa (3, 2), a na polje (3, 2) smo stigli sa (2, 1). Na polje (2, 1) smo mogli stići sa (1, 1) pri čemu je obrisan karaker d, a na polje (1, 1) smo stigli sa (0, 0) tako što je karakter z promenjen u b. Dakle, jedan niz mogućih koraka je
zdravo izmena z u b bdravo brisanje d bravo umetanje ! bravo!
Primetimo da smo na polje (2, 1) mogli stići i sa polja (1, 0) operacijom izmene d u b. Na polje (1, 0) smo stigli sa (0, 0) operacijom brisanja slova z. Na taj način dobijamo sledeći niz koraka.
zdravo brisanje z dravo izmena d u b bravo umetanje ! bravo!
Napiši program koji određuje najduži strogo rastući podniz (ne obavezno uzastopnih elemenata) unutar datog niza.
Sa standardnog ulaza se učitava broj elemenata niza \(n\) (\(1 \leq n \leq 50000\)), a zatim elementi niza (celi brojevi, svaki u posebnom redu).
Na standardni izlaz ispisati dužinu najdužeg rastućeg podniza.
10 3 2 6 9 5 4 3 7 2 8
4
Jedan rastući podniz dužine 4 je 2 6 7 8.
Prikazaćemo dva rešenja zasnovana na dinamičkom programiranju, koja su različite efikasnosti.
U prvoj grupi rešenja razmatraćemo poziciju po poziciju u nizu. Za svaku poziciju odredićemo najduži rastući podniz čiji je to poslednji element. Najduži rastući podniz se onda dobiti kao najduži od svih tih podnizova (jer on se sigurno završava na nekoj poziciji u nizu). Prilikom određivanja dužine najdužeg rastućeg podniza koji se završava na poziciji \(i \geq 0\), pretpostavićemo da za svaku prethodnu poziciju (ako ih ima) umemo da odredimo dužinu najdužeg rastućeg podniza koji se na njoj završava. Niz koji se završava na poziciji \(i\) sigurno sadrži element \(a_i\), a može produžiti sve one nizove koji se završavaju na nekoj poziciji \(j\), takvoj da je \(0 \leq j < i\) i \(a_j < a_i\). Da bi niz koji se završava na poziciji \(i\) bio što duži, njegov prefiks koji se završava na poziciji \(j\) mora biti što duži (a dužinu najdužeg rastućeg niza za svaku poziciju \(j\) možemo odrediti rekurzivno). Zato od svih nizova koji se završavaju na pozicijama \(j\), takvim da je \(a_j < a_i\) određujemo najduži i produžavamo ga elementom \(a_i\) (ako takvih elemenata nema, tada je najduži niz koji se završava na poziciji \(a_i\) jednočlan).
U direktnoj rekurzivnoj implementaciji dolazi od preklapanja rekurzivnih poziva, što dovodi do veoma neefikasnog rešenja, eksponencijalne složenosti.
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
// koji se zavrsava elementom na poziciji i
int najduziRastuciPodniz(const vector<int>& a, int i) {
int maksI = 1;
for (int j = 0; j < i; j++)
if (a[j] < a[i]) {
int maksJ = najduziRastuciPodniz(a, j);
if (maksJ + 1 > maksI)
maksI = maksJ + 1;
}
return maksI;
}
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
int najduziRastuciPodniz(const vector<int>& a) {
int maks = 0;
for (int i = 0; i < a.size(); i++) {
int maksI = najduziRastuciPodniz(a, i);
if (maksI > maks)
maks = maksI;
}
return maks;
}#include <iostream>
#include <vector>
using namespace std;
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
// koji se zavrsava elementom na poziciji i
int najduziRastuciPodniz(const vector<int>& a, int i) {
int maksI = 1;
for (int j = 0; j < i; j++)
if (a[j] < a[i]) {
int maksJ = najduziRastuciPodniz(a, j);
if (maksJ + 1 > maksI)
maksI = maksJ + 1;
}
return maksI;
}
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
int najduziRastuciPodniz(const vector<int>& a) {
int maks = 0;
for (int i = 0; i < a.size(); i++) {
int maksI = najduziRastuciPodniz(a, i);
if (maksI > maks)
maks = maksI;
}
return maks;
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << najduziRastuciPodniz(a) << endl;
return 0;
}Neefikasnost koja nastaje usled ponavljanja identičnih rekurzivnih poziva rešavamo dinamičkim programiranjem. Za memoizaciju dovoljno je da pamtimo niz dužina najdužih rastućih nizova koji se završavaju na svakoj poziciji u nizu. Pošto su sve te dužine veće ili jednake od 1 (svaki element sam za sebe čini rastući niz), niz u koji memorišemo rešenja možemo inicijalizovati nulama (što znači da je tražena dužina još nepoznata).
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
// koji se zavrsava elementom na poziciji i
int najduziRastuciPodniz(const vector<int>& a, int i,
vector<int>& memo) {
if (memo[i] != 0)
return memo[i];
int maksI = 1;
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) {
int maksJ = najduziRastuciPodniz(a, j, memo);
if (maksJ + 1 > maksI)
maksI = maksJ + 1;
}
}
return memo[i] = maksI;
}
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
int najduziRastuciPodniz(const vector<int>& a) {
vector<int> memo(a.size(), 0);
int maks = 0;
for (int i = 0; i < a.size(); i++) {
int maksI = najduziRastuciPodniz(a, i, memo);
if (maksI > maks)
maks = maksI;
}
return maks;
}#include <iostream>
#include <vector>
using namespace std;
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
// koji se zavrsava elementom na poziciji i
int najduziRastuciPodniz(const vector<int>& a, int i,
vector<int>& memo) {
if (memo[i] != 0)
return memo[i];
int maksI = 1;
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) {
int maksJ = najduziRastuciPodniz(a, j, memo);
if (maksJ + 1 > maksI)
maksI = maksJ + 1;
}
}
return memo[i] = maksI;
}
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
int najduziRastuciPodniz(const vector<int>& a) {
vector<int> memo(a.size(), 0);
int maks = 0;
for (int i = 0; i < a.size(); i++) {
int maksI = najduziRastuciPodniz(a, i, memo);
if (maksI > maks)
maks = maksI;
}
return maks;
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << najduziRastuciPodniz(a) << endl;
return 0;
}Jednostavno možemo formulisati i dinamičko programiranje naviše, tako što niz popunjavamo sleva nadesno. Nakon popunjavanja niza određujemo njegov maksimum. Naglasimo da svaki naredni element niza potencijalno zavisi od velikog broja prethodnih tako da nije moguće redukovati memorijsku složenost time što bi se pamtili samo neki elementi niza (moramo uvek znati dužine svih prethodnih elemenata).
Primer 8.3.4. Prikažimo na primeru kako će se taj niz popunjavati.
i 0 1 2 3 4 5 6 7 8 9 ai 3 2 6 9 5 4 3 7 8 2 dp 1 1 2 3 2 2 2 3 4 1
Na primer, kada izračunavamo element na poziciji 5 analiziramo nizove koji se završavaju elementima manjim od vrednosti 4 koja se nalazi na poziciji 5. To su vrednosti 3 na poziciji 0 i 2 na poziciji 1. U oba slučaja maksimalna dužina podniza koji se završava na toj poziciji je 1, pa se bilo koji od tih nizova produžava elementom 4 i dobija se rastući niz dužine 2.
Rešenje koje se dobija na ovaj način je memorijske složenosti \(O(n)\) i vremenske složenosti \(O(n^2)\).
Rešenje vremenske složenosti \(O(n\log{n})\) je prikazano u dodatku.
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
int najduzi_rastuci_podniz(const vector<int>& a) {
int n = a.size();
vector<int> dp(n);
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++)
if (a[j] < a[i] && dp[j] + 1 > dp[i])
dp[i] = dp[j] + 1;
}
int max = dp[0];
for (int i = 0; i < n; i++)
if (dp[i] > max)
max = dp[i];
return max;
}#include <iostream>
#include <vector>
using namespace std;
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
int najduzi_rastuci_podniz(const vector<int>& a) {
int n = a.size();
vector<int> dp(n);
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++)
if (a[j] < a[i] && dp[j] + 1 > dp[i])
dp[i] = dp[j] + 1;
}
int max = dp[0];
for (int i = 0; i < n; i++)
if (dp[i] > max)
max = dp[i];
return max;
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << najduzi_rastuci_podniz(a) << endl;
return 0;
}U nekim tekstovima memoizacija i dinamičko programiranje razmatraju se kao dva oblika jedne iste tehnike (jer se u oba slučaja uvodi pomoćni niz u kojem se pamte rezultati rekurzivnih poziva). Tada se memoizacija naziva dinamičko programiranje naniže, a (klasično) dinamičko programiranje naziva dinamičko programiranje naviše.↩︎