Algoritmi zasnovani na pretrazi do rešenja dolaze kroz niz koraka gde u svakom koraku analiziraju nekoliko mogućnosti. Algoritmi kod kojih se umesto analize različitih mogućnosti u svakom koraku uzima neko lokalno optimalno rešenje nazivaju se pohlepni ili gramzivi algoritmi (engl. greedy algorithms). Takve algoritme obično ima smisla primenjivati samo kod problema kod kojih postoji garancija da će takvi izbori na kraju dovesti do globalno optimalnog rešenja.
Na slici su prikazana dva drveta pretrage takva da u slučaju prvog drveta pohlepni algoritam koji u svakom koraku bira naslednika sa najvećom mogućom vrednošću dovodi do optimalnog rešenja (maksimalne moguće vrednosti), dok u slučaju drugog drveta pohlepni algoritam dovodi do neoptimalnog rešenja (vrednosti koja nije optimalna).
Pohlepni algoritmi nam, dakle, pružaju jasnu strategiju (biraj što bolju od svih raspoloživih mogućnosti) kako da u svakom koraku izaberemo jednu od više ponuđenih mogućnosti tako da na kraju dođemo do željenog optimalnog rešenja. U nastavku ćemo pojam pohlepnih algoritama malo proširiti i razmatraćemo algoritme koji u svakom koraku biraju samo jednu mogućnost na osnovu neke precizno definisane strategije, tako da ti izbori garantuju da će se na kraju doći do željenog (ispravnog tj. optimalnog) rešenja problema.
Pohlepni algoritmi ne vrše ispitivanje različitih slučajeva niti iscrpnu pretragu i stoga su po pravilu veoma efikasni (u svakom koraku je izvršeno maksimalno moguće odsecanje). Takođe, obično se veoma jednostavno implementiraju. Sa druge strane, kao i kod svih drugih algoritama u kojima se koristi odsecanje, potrebno je unapred dokazati da se pohlepnim algoritmom dobija korektno tj. optimalno rešenje, što u nekim slučajevima može biti veoma izazovno. Samo nalaženje ispravnog pohlepnog algoritma (tj. strategije) može predstavljati ozbiljan izazov i često nije trivijalno odrediti da li za neki problem postoji ili ne postoji pohlepno rešenje.
Kod nekih problema pohlepni algoritmi ne dovode uvek do optimalnog rešenja, ali se može dokazati da će rešenja koja se dobijaju biti kvalitetna i neće se puno razlikovati od optimalnih, što može opravdati upotrebu pohlepnih algoritama (jer oni mogu biti mnogo efikasniji od iscrpnih algoritama koji garantuju optimalnost). U tom slučaju pohlepni algoritmi su heuristike (tehnike koje ne garantuju da će uvek dovesti do optimalnog rešenja, ali koji dovode do dovoljno dobrih rešenja).
Algoritmi zasnovani na pretrazi ili na dinamičkom programiranju obično u svakom koraku razmatraju više mogućnosti (kojima se dobija više potproblema) i nakon razmatranja svih mogućnosti biraju onu najbolju. Dakle, izbor se vrši tek nakon rešavanja potproblema. Za razliku od toga pohlepni algoritmi unapred znaju koja mogućnost će voditi do optimalnog rešenja i izbor vrše odmah, nakon čega rešavaju samo jedan potproblem. U slučaju optmizacionih problema i u slučaju pohlepnih algoritma potrebno je da važi svojstvo optimalne podstrukture tj. da se optimalno rešenje polaznog problema dobija pomoću optimalnog rešenja potproblema.
Da bi se dokazala korektnost pohlepnog algoritma, obično je potrebno dokazati nekoliko stvari. Iako ćemo nekada pohlepnim algoritmima rešavati probleme u kojima se zahteva da se ispita da se proveri da li postoji neko rešenje koje zadovoljava date uslove i da se pronađe bilo koje takvo rešenje, najčešće ćemo razmatrati probleme u kojima se zahteva da se u grupi rešenja koja zadovoljavaju neke date uslove (ispravnih rešenja) pronađe ono optimalno (u slučaju kada postoji više takvih optimalnih rešenja obično je dovoljno da se pronađe bilo koje).
Prvo je potrebno dokazati da pohlepna strategija daje rešenje koje je ispravno tj. rešenje koje zadovoljava sve uslove zadatka.
Nakon toga je potrebno dokazati i da je rešenje dobijeno pohlepnom strategijom optimalno. Ti dokazi su po pravilu teži i postoji nekoliko tehnika kako se oni izvode. Obično se krene od nekog rešenja za koje pretpostavljamo da je optimalno i koje ne mora biti identično onome koje smo dobili pohlepnom strategijom. Ono ne može biti gore od rešenja nađenog na osnovu pohlepne strategije (jer ona vraća jedno korektno rešenje, pa optimum može biti samo eventualno bolji od tog rešenja), a potrebno je dokazati da ne može biti bolje.
Jedna tehnika da se optimalnost dokaže je to da se pokaže da se optimalno rešenje malo po malo, primenom transformacije pojedinačnih koraka može pretvoriti u rešenje dobijeno na osnovu naše strategije. Obično je dovoljno dokazati da se prvi korak optimalnog rešenja može zameniti prvim korakom koji pohlepna strategija sugeriše, tako da se korektnost i kvalitet rešenja time ne narušavaju i korektnost dalje sledi na osnovu induktivnog argumenta. Ovu tehniku nazivaćemo tehnika razmene (engl. exchange).
Jedna tehnika da se optimalnost dokaže je to da se dokaže da je rešenje dobijeno na osnovu pohlepne strategije uvek po nekom kriterijumu ispred pretpostavljenog optimalnog rešenja. Ovu tehniku nazivaćemo pohlepno rešenje je uvek ispred (engl. greedy stays ahead).
Jedna tehnika da se optimalnost dokaže je da se odredi teorijska granica vrednosti optimuma i da se onda dokaže da pohlepni algoritam daje rešenje čija je vrednost upravo jednaka optimumu. Ovu tehniku nazivaćemo tehnika granice (engl. structural bound).
Kamenje je postavljeno duž pozitivnog dela x-ose i za svaki kamen je poznata njegova koordinata \(x\). Žaba kreće da skače sa prvog kamena koji se nalazi u koordinatnom početku i želi da u što manje skokova dođe do poslednjeg kamena. U svakom skoku ona može da preskoči najviše rastojanje \(r\) (a može da skoči i manje, ako je to potrebno). Napisati program koji određuje da li žaba može stići do poslednjeg kamena i ako može u koliko najmanje skokova to može učiniti.
Sa standardnog ulaza se unosi broj \(n\) (\(1 \leq n \leq 50000\)), a zatim u narednom redu \(n\) pozitivnih celih brojeva broj (u pitanju je rastuće sortiran niz brojeva koji predstavlja koordinate kamenja). U poslednjem redu se nalazi pozitivan ceo broj \(r\).
Na standardni izlaz ispisati najmanji broj skokova potreban da žaba stigne do poslednjeg kamena ili -1 ako to nije moguće.
5 0 3 8 14 16 10
2
Jedan način da se zadatak reši je grubom silom, tj. isprobavanjem svih mogućnosti. Iako se na ovaj način dobija algoritam čija je korektnost prilično očigledna (jer su sve mogućnosti eksplicitno ispitane), u ovom zadatku takvo rešenje je nepotrebno neefikasno, jer, kako ćemo videti, postoji veoma jednostavna gramziva strategija koja uvek dovodi do optimalnog rešenja (najmanjeg broja skokova).
Osnovna ideja algoritma grube sile je da se pokuša skok sa početnog kamena na sve kamenove na koje se može doskočiti i da se zatim rekurzivno izračuna minimalni broj skokova sa kamena na koji smo doskočili do krajnjeg kamena. Ako eliminišemo kamenove na koje smo doskočili sa kojih ne postoji put do krajnjeg kamena i od preostalih kamenova pronađemo minimalni broj skokova do krajenjeg kamena, minimalni broj skokova od početnog kamena do krajnjeg je broj koji je za jedan veći od tog broja.
Primer 9.1. Na slici je prikazano drvo iscrpne pretrage za niz kamenova \(0, 3, 8, 9, 14, 16\) i dužinu skoka \(r=10\). Sa kamena \(0\), žaba može da skoči na kamenove \(3\), \(8\) i \(9\), sa kamena \(3\) na kamenove \(8\) i \(9\), sa kamena \(8\) na kamenove \(9\), \(14\) i \(16\), sa kamena \(9\) na kamenove \(14\) i \(16\) i sa kamena \(14\) na kamen \(16\). Uz svaki čvor je obeležen i najmanji broj skokova potrebnih da žaba dođe do završnog kamena \(16\). Označene su i dve najkraće putanje (\(0-8-16\) i \(0-9-16\)).
Pošto jednostavna rekurzivna implementacija dovodi do ponovljenih rekurzivnih poziva (može se očekivati da ćemo tokom pretrage često dolaziti na neki kamen i računati minimalni broj skokova od tog kamena do kraja), program treba optimizovati dinamičkim programiranje.
Jedno rešenje je da se upotrebi memoizacija. Ako bi se sa svakog kamena moglo doskočiti do svakog drugog, ovim bismo dobili rešenje složenosti \(O(n^2)\) (uz korišćenje pomoćnog niza dužine \(n\)).
Umesto memoizacije možemo upotrebiti i dinamičko programiranje naviše. Niz u kome čuvamo minimalni broj skokova do krajnjeg kamena treba popunjavati od krajnjeg kamena nalevo, u opadajućem redosledu koordinata. Složenost ovog rešenja je takođe \(O(n^2)\) (uz korišćenje pomoćnog niza dužine \(n\)).
Iako u svakom koraku žaba može imati izbor između nekoliko kamenova na koje može da skoči, intuitivno nam je sasvim jasno da ona ništa ne gubi time što skoči što dalje. Stoga je jasno da žaba u svakom koraku treba da skoči na što dalji kamen koji je na rastojanju najviše \(r\). Ako nijedan kamen koji je na rastojanju najviše \(r\) ne postoji, tada žaba ne može stići do kraja. Nakon što žaba napravi prvi skok, postupak se ponavlja na isti način, sve dok ne stigne do kraja ili dok se ne dođe do situacije u kojoj žaba ne može da skoči dalje.
U svakom koraku tražimo najdalji kamen na koji žaba može da skoči i to tako što tražimo prvi kamen na koji žaba ne može da doskoči (to možemo uraditi linearnom, ali i binarnom pretragom). Kada nađemo kamen na koji žaba ne može da doskoči žaba skače na kamen ispred njega (ako žaba može da skoči na svaki kamen, tada skače na poslednji, a ako ne može da skoči ni na jedan kamen, tada konstatujemo da do poslednjeg kamena ne može da doskoči).
Primer 9.2. Razmotrimo primer kada je niz kamenja \(0, 3, 8, 9, 14, 16, 23, 25, 32\) i kada je dužina skoka \(r=10\). Sa početnog kamena \(0\) žaba skače na kamen \(9\) (to je najdalji kamen na koji može da doskoči sa kamena \(0\)). Nakon toga skače na kamen \(16\) (to je najdalji kamen na koji može da doskoči sa kamena \(9\)), nakon toga na kamen \(25\) (to je najdalji kamen na koji može da doskoči sa kamena \(16\)) i na kraju na kamen \(32\) (to je najdalji kamen na koji može da doskoči sa kamena \(25\)).
Ovaj algoritam je tipičan pohlepni (gramzivi) algoritam, jer se u svakom koraku uzima što je više moguće i tako da se dolazi i do globalnog optimuma (najmanjeg broja skokova). Ostaje pitanje kako dokazati da je ova strategija korektna.
Prvo dokazujemo da prethodni algoritam uvek daje korektno rešenje tj. rešenje u skladu sa uslovom zadatka (žaba kreće sa prvog kamena, dolazi na poslednji i u svakom koraku skače samo napred, ne više od \(r\) metara). Zaista, implementacija je određena tako da je svaki skok koji žaba pravi u prethodnom algoritmu skok na kamen koji je udaljen najviše \(r\) (to se u algoritmu eksplicitno proverava), pa smo sigurni da je niz skokova, ako se pronađe, ispravan.
Dodatno je potrebno da dokažemo da je i u slučaju kada funkcija vraća \(-1\), taj odgovor korektan tj. da tada zaista nije moguće da žaba dođe do kraja. To se dešava kada postoje dva kamena sa koordinatama \(x_i\) i \(x_{i+1}\) takvi da je \(x_{i+1} > x_i + r\). Ako bi postojalo neko ispravno rešenje, žaba bi morala da skoči sa nekog kamena pre \(i\) (ili sa kamena \(i\)) na neki kamen nakon \(x_{i+1}\) (ili na kamen \(x_{i+1}\)), no to je nemoguće jer je zbog sortiranosti niza rastojanje svakog takvog para kamenova strogo veće od \(r\).
Drugo što je potrebno dokazati je da je rešenje koje se dobija strategijom optimalno. U ovom slučaju to znači da pohlepna strategija daje najmanji mogući broj skokova.
Dokazaćemo da se kamen na kom se žaba nalazi nakon \(i\) koraka primene strategije nikada ne nalazi strogo iza kamena na kom se žaba nalazi nakon \(i\) koraka u optimalnom rešenju (žaba skače po strategiji je u svakom koraku ili ispred ili na istom kamenu u odnosu na sve žabe koje dostižu cilj u najmanjem broju koraka). Ovo je tipičan dokaz tehnikom pohlepno rešenje je uvek ispred.
Primer 9.3. Razmotrimo primer kada je niz kamenja \(0, 3, 8, 9, 14, 16, 23, 25, 32\) i kada je dužina skoka \(r=10\). Rešenje na osnovu strategije je \(0, 9, 16, 25, 32\). Jedno drugačije optimalno rešenje je \(0, 8, 14, 23, 32\). Zaista, ni u jednom koraku rešenje na osnovu strategije ne zaostaje za optimalnim rešenjem (a u mnogim koracima prednjači). Važi \(0=0\), \(9 \geq 8\), \(16 \geq 14\), \(25 \geq 23\) i \(32=32\).
Formalno, neka je optimalna vrednost broja skokova \(k\) i i neka je \(x^*_0, x^*_1, \ldots, x^*_{k-1}\) sortiran niz x-koordinata kamenja na koje žaba staje u jednom takvom optimalnom rešenju. Neka je \(x_0, x_1, \ldots, x_{m-1}\) rešenje dobijeno na osnovu naše strategije. Pošto nijedno rešenje ne može biti bolje od optimalnog, važi da je \(k \leq m\). Indukcijom dokazujemo da za svako \(i < k\) važi \(x_i \geq x^*_i\).
Na osnovu dokazanog važi i da je \(x_{k-1} \geq x^*_{k-1}\), međutim, pošto je \(x^*_{k-1}\) koordinata poslednjeg kamena, to mora biti i \(x_{k-1}\) (pa je \(m = k\)). Dakle, i optimalna strategija stiže do poslednjeg kamena u \(k\) koraka, pa optimalno rešenje nije bolje od pohlepnog.
int brojSkokova(const vector<int>& kamenje, int r) {
// strategija: u svakom koraku skoci sto dalje
int n = kamenje.size();
int broj = 0; // broj skokova
int kamen = 0; // kamen na kom se zaba trenutno nalazi
while (kamen < n - 1) {
// odredjujemo najdalji kamen na koji mozemo stici od
// tekuceg
int noviKamen = kamen;
// dok god mozes da skocis dalje, skoci dalje
while (noviKamen + 1 < n &&
kamenje[noviKamen + 1] - kamenje[kamen] <= r)
noviKamen++;
// zaba ne moze da skoci ni na jedan kamen
if (noviKamen == kamen)
return -1;
// zaba skace na najdalji moguci kamen i uvecavamo broj
// skokova
kamen = noviKamen;
broj++;
}
// vracamo broj skokova dobijen ovom strategijom
return broj;
}#include <iostream>
#include <vector>
using namespace std;
int brojSkokova(const vector<int>& kamenje, int r) {
// strategija: u svakom koraku skoci sto dalje
int n = kamenje.size();
int broj = 0; // broj skokova
int kamen = 0; // kamen na kom se zaba trenutno nalazi
while (kamen < n - 1) {
// odredjujemo najdalji kamen na koji mozemo stici od
// tekuceg
int noviKamen = kamen;
// dok god mozes da skocis dalje, skoci dalje
while (noviKamen + 1 < n &&
kamenje[noviKamen + 1] - kamenje[kamen] <= r)
noviKamen++;
// zaba ne moze da skoci ni na jedan kamen
if (noviKamen == kamen)
return -1;
// zaba skace na najdalji moguci kamen i uvecavamo broj
// skokova
kamen = noviKamen;
broj++;
}
// vracamo broj skokova dobijen ovom strategijom
return broj;
}
int main() {
// ucitavamo koordinate kamenja
int n;
cin >> n;
vector<int> kamenje(n);
for (int i = 0; i < n; i++)
cin >> kamenje[i];
// rastojanje koje zaba moze da preskoci
int r;
cin >> r;
// odredjujemo i ispisujemo optimalni broj skokova
cout << brojSkokova(kamenje, r) << endl;
return 0;
}U implementaciji se koriste dva pokazivača (kamen i novi_kamen), koji se kroz niz kamenova kreću samo unapred, tako da je ukupan broj koraka algoritma sigurno ograničen dvostrukom dužinom niza i složenost ovog rešenja je \(O(n)\).
Šahovska ekipa \(A\) je pozvala na pripreme šahovsku ekipu \(B\). Svaka ekipa ima isti broj igrača i za svakog igrača je poznat rejting. Ekipa domaćina ima mogućnost da odabere parove koji će igrati u prvom kolu (par čini po jedan igrač iz svake ekipe). Ako svaki igrač domaćina pobeđuje gosta koji ima manji ili jednak rejting, a gubi od gosta koji ima strogo veći rejting, napiši program koji određuje koji je najveći broj pobeda koje ekipa domaćina (ekipa \(A\)) može da ostvari u prvom kolu.
Sa standardnog ulaza se unosi broj \(n\) (\(1 \leq n \leq 50000\)), a zatim u naredom redu rejtinzi igrača ekipe domaćina (prirodni brojevi) razdvojeni razmacima, a u naredom redu rejtinzi igrača ekipe gostiju (prirodni brojevi) razdvojeni razmacima.
Na standardni izlaz ispisati samo jedan broj koji predstavlja najveći mogući broj pobeda domaćina.
4 2120 1985 2205 1842 2045 2100 1990 1980
3
Domaćin može da ostvari najviše tri pobede. Na primer, igrač 2205 može da dobije igrača 2100, igrač 2120 može da dobije igrača 2045, a igrač 1985 može da dobije igrača 1980.
Zadatak možemo rešiti pomoću nekoliko različitih gramzivih algoritama. Cilj je da odredimo najveći broj parova domaćih i gostujućih igrača u kojima domaći igrač nema manji rejting od svog para. Zato ćemo prilikom raspoređivanja obraćati pažnju samo na one partije u kojima domaćini pobeđuju, dok ćemo ostale partije zanemariti (potpuno nam je nebitno kako su tačno raspoređeni igrači u partijama u kojima domaćini gube).
Jedna mogućnost je da se parovi formiraju tako što se upari \(k\) najboljih domaćih igrača sa \(k\) najlošijih gostujućih igrača (dok ostale igrače uparimo na proizvoljan način). Ta strategija bi bila korektna, ali njena implementacija nije trivijalna, jer nije jasno koliko maksimalno može da bude \(k\) tako da u svih \(k\) parova domaćini dobijaju.
Slična strategija, koja se jednostavno implementira je sledeća. Ako domaćin može da ostvari bar jednu pobedu, nju može da donese najbolji domaći igrač. Naime, ako bi on izgubio svoj meč, uvek bismo nekog od igrača koji je dobio meč mogli zameniti njime (jer je on bolji od svih igrača domaćina) i dobiti isti broj pobeda. Postavlja se pitanje sa kojim gostujućem igračem on treba da igra. Cilj nam je da nakon formiranja tog para preostanu što lošiji gostujući igrači, da bi slabiji igrači tima domaćina imali šanse da ostvare pobede. Jasno je da u skup parova u kojima domaćini dobijaju ne možemo da uključimo goste koji su bolji od tog najboljeg domaćeg igrača (jer njih niko od igrača domaćina ne može da pobedi). Dobra strategija je da od preostalih gostujućih igrača izaberemo najboljeg. Nakon uparivanja najboljeg domaćeg igrača i gosta sa kojim će on da igra i eliminisanja svih gostiju boljih od njega, problem je sveden na problem istog oblika, ali manje dimenzije (smanjen je broj preostalih domaćih i broj gostujućih igrača koje pokušavamo da uparimo tako da domaćini pobeđuju). Izlaz iz ovog rekurzivnog postupka predstavlja slučaj kada su svi domaći igrači uspešno upareni ili kada među preostalim gostujućim igračima nema lošijih od najboljeg među preostalim domaćinima.
Dokažimo i formalno korektnost ovakve gramzive strategije.
Rešenje koje prethodni algoritam daje je korektno uparivanje i zadovoljava uslove zadatka jer se svaki domaćin uparuje sa gostom koja nije bolji od njega (to se eksplicitno proverava) i nije ni uparen ni sa jednim drugim domaćinom (jer se nakon uparivanja i domaćin i gost eliminišu iz daljeg razmatranja). Dakle, sigurni smo da zaista postoji korektno uparivanje u kome domaćin ostvaruju broj prijavljen broj pobeda.
Pokažimo i da naša strategija pravi optimalni broj pobeda za domaću ekipu. Dokaz će ići tehnikom razmene, tj. time što ćemo se pokazati da se optimalno uparivanje može transformisati u ono dobijeno gramzivom strategijom, održavajući ukupan broj parova u kojima domaćin pobeđuje (za igrače domaćina koji pobeđuju reći ćemo da su dobitno upareni). Posmatrajmo neko optimalno uparivanje. Neka je \(d_i\) najbolji domaćin koji učestvuje u njemu i neka je \(g_i\) gost sa kojim je on uparen.
Ako on nije ukupno najbolji domaćin \(d_s\), tada najbolji domaćin sigurno nije dobitno uparen. Možemo domaćina \(d_i\) izbaciti iz dobitnog uparivanja i njemu pridruženog gosta \(g_i\) pridružiti ukupno najboljem domaćinu \(d_s\) (to je moguće jer je \(d_s \geq d_i \geq g_i\)). Takvo uparivanje je i dalje optimalno (jer se broj dobitnih parova za domaćina nije promenio).
Neka je \(g_s\) gost koja bi bio odabran strategijom (najbolji gost koji nije bolji od \(d_s\), tj. najbolji gost za koga važi \(d_s \geq g_s\)).
Ako on nije deo trenutnog dobitnog uparivanja, onda gosta \(g_i\) koji trenutno igra sa domaćinom \(d_s\) možemo izbaciti i zameniti gostom \(g_s\) (to je moguće jer je \(d_s \geq g_s\)).
Ako jeste raspoređen tako da gubi od nekog domaćina \(d_j\), onda možemo napraviti razmenu tako da \(d_s\) igra sa \(g_s\), a \(d_j\) sa \(g_i\). Dokažimo da je ovo i dalje korektno uparivanje. Važi da je \(d_s \geq g_s\) i \(d_s \geq g_i\). Pošto je \(g_s\) najbolji gost koga \(d_s\) može da pobedi, važi da je \(g_s \geq g_i\). Zato je \(d_j \geq g_s \geq g_i\). Sa ove dve eventualne razmene dobijamo i dalje optimalan raspored koji je u skladu sa našom strategijom što se tiče prvog para.
Nastavljajući razmene po istom principu (tj. na osnovu induktivnog argumenta), uparivanje možemo transformisati u ono formirano našom strategijom, zadržavajući sve vreme optimalnost.
Prilikom implementacije, skupove domaćih i gostujućih igrača možemo čuvati u nizovima uređenim u nerastućem redosledu rejtinga i algoritam možemo realizovati tehnikom dva pokazivača (prodiskutovaćemo kasnije i ostale moguće varijante). Niz domaćina obilazimo redom, element po element, a niz gostiju razdvajamo na one koje su eliminisani (one koji su do sada upareni i one koje nisu upareni, ali su bolji od tekućeg domaćeg igrača) i preostale. Održavamo mesto početka niza gostiju koji još nisu obrađeni i prilikom traženja para za tekućeg domaćeg igrača niz gostiju obilazimo od te pozicije. Svakog gosta ili eliminišemo, jer je bolji od tekućeg domaćeg igrača ili ga uparujemo sa tekućim domaćim igračem i onda ih obojicu eliminišemo. Naglasimo da se u implementaciji ne moramo vraćati na eliminisane goste, jer ako je neki gost bolji od tekućeg domaćina (najboljeg među preostalim), biće bolji i od svih narednih (preostalih) domaćina.
Pošto se oba pokazivača kreću samo u jednom smeru i složenost faze uparivanja je linearna. Ukupnim algoritmom, dakle, dominira složenost sortiranja, pa je ukupna složenost \(O(n\log{n})\).
Moguće je formulisati i gramzivu strategiju koja će biti dualna ovoj upravo opisanoj. U toj gramzivoj strategiji obrađujemo goste u neopadajućem redosledu rejtinga (od lošijih ka boljima) i svakom gostu dodeljujemo najlošijeg domaćina koji može da ga pobedi. Analogno prethodnoj, jednostavno se dokazuje da je i ta gramziva strategija takođe korektna.
int maksBrojPobeda(vector<int>& domaci, vector<int>& gosti) {
// Ako domacini mogu da ostvare nekih k pobeda, onda tih k
// pobeda moze da ostvari njihovih k najjacih igraca. Zato
// domacine obradjujemo u nerastucem redosledu rejtinga i za
// svakog redom odredjujemo gosta kojeg moze da pobedi. Za
// svakog domacina odredjujemo najboljeg gosta kojeg moze da
// pobedi jer time losijim igracima domace ekipe ostavljamo
// prostor da pobede nekoga.
// broj igraca
int n = domaci.size();
// zelimo da i domacine i goste obilazimo u nerastucem
// redosledu rejtinga (od boljih ka losijim)
sort(begin(domaci), end(domaci), greater<int>());
sort(begin(gosti), end(gosti), greater<int>());
// broj pobeda domacih igraca
int brojPobeda = 0;
// tekuci indeks domaceg i gostujuceg igraca
int d = 0, g = 0;
while (true) {
// trazimo najboljeg gosta kojeg moze da pobedi domacin na
// poziciji d goste koji su jaci od trenutno najaceg
// domacina ne moze da pobedi niko od preostalih domacina,
// pa ih eliminisemo iz daljeg razmatranja
while (g < n && domaci[d] < gosti[g])
g++;
// ako najaci nerasporedjeni domacin ne moze da pobedi
// nijednog gosta, ne mozemo povecati broj pobeda
if (g >= n) break;
// u suprotnom smo nasli gosta g kojeg uparujemo sa
// domacinom d
brojPobeda++;
// obojicu eliminisemo iz daljeg uparivanja
g++, d++;
}
return brojPobeda;
}#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int maksBrojPobeda(vector<int>& domaci, vector<int>& gosti) {
// Ako domacini mogu da ostvare nekih k pobeda, onda tih k
// pobeda moze da ostvari njihovih k najjacih igraca. Zato
// domacine obradjujemo u nerastucem redosledu rejtinga i za
// svakog redom odredjujemo gosta kojeg moze da pobedi. Za
// svakog domacina odredjujemo najboljeg gosta kojeg moze da
// pobedi jer time losijim igracima domace ekipe ostavljamo
// prostor da pobede nekoga.
// broj igraca
int n = domaci.size();
// zelimo da i domacine i goste obilazimo u nerastucem
// redosledu rejtinga (od boljih ka losijim)
sort(begin(domaci), end(domaci), greater<int>());
sort(begin(gosti), end(gosti), greater<int>());
// broj pobeda domacih igraca
int brojPobeda = 0;
// tekuci indeks domaceg i gostujuceg igraca
int d = 0, g = 0;
while (true) {
// trazimo najboljeg gosta kojeg moze da pobedi domacin na
// poziciji d goste koji su jaci od trenutno najaceg
// domacina ne moze da pobedi niko od preostalih domacina,
// pa ih eliminisemo iz daljeg razmatranja
while (g < n && domaci[d] < gosti[g])
g++;
// ako najaci nerasporedjeni domacin ne moze da pobedi
// nijednog gosta, ne mozemo povecati broj pobeda
if (g >= n) break;
// u suprotnom smo nasli gosta g kojeg uparujemo sa
// domacinom d
brojPobeda++;
// obojicu eliminisemo iz daljeg uparivanja
g++, d++;
}
return brojPobeda;
}
int main() {
// ucitavamo ulazne podatke
int n;
cin >> n;
vector<int> domaci(n);
for (int i = 0; i < n; i++)
cin >> domaci[i];
vector<int> gosti(n);
for (int i = 0; i < n; i++)
cin >> gosti[i];
// odredjujemo i prijavljujemo maksimalni broj pobeda koje mogu
// ostvariti domaci igraci
cout << maksBrojPobeda(domaci, gosti) << endl;
return 0;
}Skrenimo pažnju i na važnost efikasne implementacije. Razmotrimo rešenje zasnovano na dualnoj strategiji u kojoj uparujemo loše goste. Kao što smo videli, u efikasnoj implementaciji bi prilikom prelaska na svakog novog gosta domaćina trebalo tražiti samo među onima koji u ranijim koracima nisu eliminisani (bilo tako što su upareni ili tako što je ustanovljeno da ne mogu da pobede nekog od slabijih gostiju). Ako pretragu domaćina svaki put počinjemo iz početka (vodeći računa o tome da ranije uparene domaćine ne uparujemo ponovo, tako što u posebnom nizu registrujemo one domaćine koje smo već uparili) dobićemo neefikasan algoritam.
Pošto se za svakog od \(n\) gostiju iznova pretražuje niz od \(n\) domaćina, složenost najgoreg slučaja ove implementacije je \(O(n^2)\). Naglasimo da nije problem u gramzivoj strategiji, već u njenoj lošoj implementaciji.
int maksBrojPobeda(vector<int>& domaci, vector<int>& gosti) {
// broj igraca
int n = domaci.size();
// Ako je moguce pobediti nekih k gostiju, onda tih k
// gostiju mogu biti k najlosijih gostiju. Zato goste
// obradjujemo u rastucem redosledu rejtinga (od losijih ka
// boljima) i za svakog redom odredjujemo domacina koji moze
// da pobedi tog gosta, a nije ranije uparen.
sort(begin(domaci), end(domaci));
sort(begin(gosti), end(gosti));
// broj pobeda domacih igraca
int brojPobeda = 0;
// da li je domacin trenutno uparen
vector<bool> zauzet(n, false);
// obilazimo sve goste
for (int g = 0; g < n; g++)
// trazimo najslabijeg neuparenog domacina koji moze
// pobediti gosta g
for (int d = 0; d < n; d++)
if (!zauzet[d] && domaci[d] >= gosti[g]) {
brojPobeda++;
zauzet[d] = true;
break;
}
return brojPobeda;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maksBrojPobeda(vector<int>& domaci, vector<int>& gosti) {
// broj igraca
int n = domaci.size();
// Ako je moguce pobediti nekih k gostiju, onda tih k
// gostiju mogu biti k najlosijih gostiju. Zato goste
// obradjujemo u rastucem redosledu rejtinga (od losijih ka
// boljima) i za svakog redom odredjujemo domacina koji moze
// da pobedi tog gosta, a nije ranije uparen.
sort(begin(domaci), end(domaci));
sort(begin(gosti), end(gosti));
// broj pobeda domacih igraca
int brojPobeda = 0;
// da li je domacin trenutno uparen
vector<bool> zauzet(n, false);
// obilazimo sve goste
for (int g = 0; g < n; g++)
// trazimo najslabijeg neuparenog domacina koji moze
// pobediti gosta g
for (int d = 0; d < n; d++)
if (!zauzet[d] && domaci[d] >= gosti[g]) {
brojPobeda++;
zauzet[d] = true;
break;
}
return brojPobeda;
}
int main() {
// ucitavamo ulazne podatke
int n;
cin >> n;
vector<int> domaci(n);
for (int i = 0; i < n; i++)
cin >> domaci[i];
vector<int> gosti(n);
for (int i = 0; i < n; i++)
cin >> gosti[i];
// odredjujemo i prijavljujemo maksimalni broj pobeda koje mogu
// ostvariti domaci igraci
cout << maksBrojPobeda(domaci, gosti) << endl;
return 0;
}Za svaki od \(n\) časova poznato je vreme početka i završetka. Kada se u nekoj učionici završi jedan čas, istog trenutka u njoj može da počne neki drugi čas. Napiši program koji određuje minimalan broj učionica potreban da se svi časovi održe.
Sa standardnog ulaza se učitava broj \(n\) (\(1 \leq n \leq 10^5\)), a zatim u \(n\) narednih redova podaci o \(n\) časova (sat i minut početka i sat i minut završetka, pri čemu je vreme početka strogo manje od vremena završetka).
Na standardni izlaz ispisati traženi broj potrebnih učionica.
6 8 0 8 45 10 0 10 45 9 0 9 45 8 30 9 15 10 45 11 30 10 30 11 15
2
Jedan mogući raspored navedenih 6 časova u dve učionice je sledeći:
Učionica 1 Učionica 2 8:00-8:45 Čas 1 8:30-9:15 Čas 4 9:00-9:45 Čas 3 10:30-11:15 Čas 6 10:00-10:45 Čas 2 10:45-11:30 Čas 5
Pošto se zahteva da se svi časovi održe, obilazićemo ih u određenom redosledu i svaki čas ćemo pridruživati nekoj od slobodnih učionica. U trenutku u kom počinje neki čas i u kome nema više slobodnih učionica koje su ranije upotrebljavane, otvaraćemo novu učionicu u koju ćemo raspoređivati taj čas.
Znamo da je najmanji broj učionica sigurno veći ili jednak najvećem broju časova koji se istovremeno održavaju u nekom trenutku. U nastavku ćemo dokazati da je minimalan broj učionica uvek jednak tom broju i da se raspored može napraviti ako se časovi obilaze u rastućem redosledu njihovog početka.
Primer 9.4. Na slici je prikazan jedan mogući raspored časova. Učionice se nalaze jedna iznad druge (svi časovi u istoj učionici su prikazani na istoj visini). Vertikalnim linijama su označeni trenuci u kojima su sve učionice popunjene tj. trenuci u kojima postoji 5 časova koji se preklapaju. Zbog toga je jasno da nije moguće napraviti raspored sa manje od 5 učionica.
Jedan mogući redosled obrade časova je rastući (neopadajući) redosled njihovih početaka.
Dokažimo da je naša strategija optimalna. Strategija je takva da je jedini razlog da se nova učionica otvori to da su sve ranije otvorene učionice već popunjene u trenutku kada počinje tekući čas, tj. da postoji neki čas (recimo \([s_j, f_j)\)) koji se preklapa sa svim časovima koji su raspoređeni i u trenutku njegovog početka se održavaju u trenutnih \(d\) otvorenih učionica. Pošto su časovi sortirani na osnovu vremena početka, svih tih \(d\) časova počinje pre trenutka \(s_j\) i završava se nakon trenutka \(s_j\) (jer traju u trenutku \(s_j\)). To znači da u trenutku \(s_j\) sigurno postoji \(d+1\) časova (tih \(d\) već raspoređenih i čas \([s_j, f_j)\)) koji se u tom trenutku održavaju, pa broj učionica mora biti bar \(d+1\). Dakle, ako se na osnovu strategije rezerviše nova učionica, sigurni smo da je to neophodno. Zbog toga znamo da kada naša strategija napravi raspored sa nekim brojem učionica, sigurni smo da nije bilo moguće napraviti raspored sa manjim brojem učionica, što znači da je napravljeni raspored optimalan.
Primetimo da je u ovom dokazu određena granica kvaliteta rešenja (raspored ne može biti u manje učionica nego što je broj časova u najvećoj grupi časova koji se održavaju u nekom trenutku) i zatim je pokazano da pohlepno rešenje dostiže tu granicu, pa je zbog toga optimalno.
Ako nas zanima samo broj potrebnih učionica, a i konkretan raspored, tada možemo napraviti veoma jednostavnu implementaciju koja održava broj trenutno otvorenih učionica i obilazi sve značajne vremenske trenutke (početke i završetke časova) redom. Na kraju časa smanjuje se broj zauzetih učionica, a na početku časa povećava se broj učionica. Traženi rezultat se dobija kao maksimalna vrednost brojača zauzetih učionica.
Potrebno je još obratiti pažnju na specijalan slučaj kada se neki časovi završavaju u istom trenutku u kom drugi časovi počinju. Elegantno rešenje je da u datom vremenskom trenutku prvo obradimo sve časove koji se završavaju u tom trenutku i oslobodimo učionice, a zatim da obradimo časove koji počinju u tom trenutku (tako nove časove raspoređujemo u upravo oslobođene učionice, što je u skladu sa tim da je vreme trajanja svakog časa poluotvoreni interval \([s, f)\)).
Za \(n\) časova postoji \(2n\) karakterističnih trenutaka. Njihovo sortiranje se vrši u vremenu \(O(n\log{n})\). Obilazak sortiranog niza trenutaka i ažuriranje brojača se zatim vrši u vremenu \(O(n)\). Složenošću, dakle, dominira sortiranje i ukupna složenost je \(O(n \log{n})\).
// karakteristicni trenuci
struct Vreme {
// vreme izrazeno u minutima
int minut;
// da li je u pitanju pocetak ili kraj casa
bool pocetak;
};
// funkcija rasporedjuje casove u ucionice, vraca minimalni
// potrebni broj ucionica i svakom casu dodeljuje broj
// ucionice
int minUcionica(vector<Vreme>& vremena) {
sort(begin(vremena), end(vremena),
[](const Vreme& v1, const Vreme& v2) {
return v1.minut < v2.minut ||
(v1.minut == v2.minut && !v1.pocetak && v2.pocetak);
});
// trenutan broj zauzetih ucionica
int brojUcionica = 0;
// maksimalni broj zauzetih ucionica u nekom trenutku
int maksBroj = 0;
for (const Vreme& v : vremena)
if (v.pocetak)
maksBroj = max(++brojUcionica, maksBroj);
else
brojUcionica--;
return maksBroj;
}#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;
// karakteristicni trenuci
struct Vreme {
// vreme izrazeno u minutima
int minut;
// da li je u pitanju pocetak ili kraj casa
bool pocetak;
};
Vreme napraviVreme(int sat, int min, bool pocetak) {
Vreme v;
v.minut = 60*sat + min;
v.pocetak = pocetak;
return v;
}
// ucitava spisak casova sa standardnog ulaza
vector<Vreme> ucitajCasove() {
int n;
cin >> n;
vector<Vreme> vremena;
vremena.reserve(2*n);
for (int i = 0; i < n; i++) {
int pocSat, pocMin, krajSat, krajMin;
cin >> pocSat >> pocMin >> krajSat >> krajMin;
vremena.push_back(napraviVreme(pocSat, pocMin, true));
vremena.push_back(napraviVreme(krajSat, krajMin, false));
}
return vremena;
}
// funkcija rasporedjuje casove u ucionice, vraca minimalni
// potrebni broj ucionica i svakom casu dodeljuje broj
// ucionice
int minUcionica(vector<Vreme>& vremena) {
sort(begin(vremena), end(vremena),
[](const Vreme& v1, const Vreme& v2) {
return v1.minut < v2.minut ||
(v1.minut == v2.minut && !v1.pocetak && v2.pocetak);
});
// trenutan broj zauzetih ucionica
int brojUcionica = 0;
// maksimalni broj zauzetih ucionica u nekom trenutku
int maksBroj = 0;
for (const Vreme& v : vremena)
if (v.pocetak)
maksBroj = max(++brojUcionica, maksBroj);
else
brojUcionica--;
return maksBroj;
}
int main() {
vector<Vreme> vremena = ucitajCasove();
cout << minUcionica(vremena) << endl;
return 0;
}Ako želimo da napravimo konkretan raspored, implementacija je malo komplikovanija. Prvi korak u implementaciji je veoma jednostavan – učitavamo sve časove u niz i sortiramo ih na osnovu početnog vremena. Ključni korak u drugoj fazi je određivanje učionice u koju može biti smešten tekući čas. Za sve do tada otvorene učionice znamo vremena završetka časova u njima. Možemo pronaći učionicu u kojoj se čas najranije završava i proveriti da li je moguće da u nju rasporedimo tekući čas. Ako jeste, njoj ažuriramo vreme završetka časa, a ako nije, onda znamo da su sve učionice zauzete (jer se čas koji se prvi završava još nije završio), pa moramo otvoriti novu učionicu. Da bismo efikasno mogli da nađemo učionicu u kojoj se čas najranije završava, sve učionice možemo čuvati u redu sa prioritetom sortiranom po vremenu završetka časa u svakoj od učionica. Ako taj red nije prazan i ako je vreme završetka časa u učionici na vrhu reda manje ili jednako vremenu početka tekućeg časa, vreme završetka časa u toj učionici ažuriramo na vreme završetka tekućeg časa (najlakše tako što tu učionicu izbacimo iz reda i ponovo je dodamo sa ažuriranim vremenom). U suprotnom u red dodajemo novu učionicu kojoj je vreme završetka časa postavljeno na vreme završetka tekućeg časa (broj učionice je za jedan veći od dotadašnjeg broja učionica u redu).
Broj otvorenih učionica je uvek jednak broju elemenata reda. Naime, element u red dodajemo samo kada otvaramo novu učionicu jer su sve do tada otvorene učionice u redu zauzete, dok u suprotnom samo menjamo element koji je bio na vrhu reda novim (časovi koji su se završili a nisu zamenjeni novim časovima u istoj učionici ostaju u redu).
Ukupna složenost algoritma je \(O(n\log{n})\) – i u fazi sortiranja i u fazi raspoređivanja (jer se čitanje i izbacivanje minimuma, kao i ubacivanje novog elementa u red sa prioritetom vrši u vremenu \(O(\log{n})\)). Kada bismo umesto reda sa prioritetom koristili običan niz i u njemu stalno tražili minimum, složenost najgoreg slučaja bi porasla na \(O(n^2)\).
struct Cas {
// redni broj casa (njegov jedinstveni identifikator)
int broj;
// minut pocetka i kraja casa
int pocetak, kraj;
// redni broj ucionice u kojoj se cas odrzava
int ucionica;
};
struct Ucionica {
// broj ucionice (njen jedinstveni identifikator)
int broj;
// minut od kog je ucionica slobodna
int slobodnaOd;
};
// funkcija rasporedjuje casove u ucionice, vraca minimalni
// potrebni broj ucionica i svakom casu dodeljuje broj
// ucionice
int minUcionica(vector<Cas>& casovi) {
// sortiramo časove na osnovu vremena njihovog početka
sort(begin(casovi), end(casovi),
[](const Cas& c1, const Cas& c2) {
return c1.pocetak < c2.pocetak;
});
// red sa prioritetom u kom su trenutno zauzete ucionce
// slozene po vremenu zavrsetka casa
struct PorediUcionice {
bool operator()(const Ucionica& u1, const Ucionica& u2) {
return u1.slobodnaOd > u2.slobodnaOd;
}
};
priority_queue<Ucionica, vector<Ucionica>, PorediUcionice>
redUcionica;
for (Cas& c : casovi) {
int brojUcionice;
if (redUcionica.empty() ||
redUcionica.top().slobodnaOd > c.pocetak)
brojUcionice = redUcionica.size() + 1;
else {
brojUcionice = redUcionica.top().broj;
redUcionica.pop();
}
c.ucionica = brojUcionice;
redUcionica.push(napraviUcionicu(c.kraj, brojUcionice));
}
// sortiramo časove na osnovu rednog broja
sort(begin(casovi), end(casovi),
[](const Cas& c1, const Cas& c2) {
return c1.broj < c2.broj;
});
return redUcionica.size();
}#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;
struct Cas {
// redni broj casa (njegov jedinstveni identifikator)
int broj;
// minut pocetka i kraja casa
int pocetak, kraj;
// redni broj ucionice u kojoj se cas odrzava
int ucionica;
};
Cas napraviCas(int broj, int pocSat, int pocMin,
int krajSat, int krajMin) {
Cas c;
c.broj = broj;
c.pocetak = pocSat*60 + pocMin;
c.kraj = krajSat*60 + krajMin;
return c;
}
struct Ucionica {
// broj ucionice (njen jedinstveni identifikator)
int broj;
// minut od kog je ucionica slobodna
int slobodnaOd;
};
Ucionica napraviUcionicu(int slobodnaOd, int broj) {
Ucionica u;
u.broj = broj;
u.slobodnaOd = slobodnaOd;
return u;
}
// ucitava spisak casova sa standardnog ulaza
vector<Cas> ucitajCasove() {
int n;
cin >> n;
vector<Cas> casovi(n);
for (int i = 0; i < n; i++) {
int pocSat, pocMin, krajSat, krajMin;
cin >> pocSat >> pocMin >> krajSat >> krajMin;
casovi[i] = napraviCas(i, pocSat, pocMin, krajSat, krajMin);
}
return casovi;
}
// funkcija rasporedjuje casove u ucionice, vraca minimalni
// potrebni broj ucionica i svakom casu dodeljuje broj
// ucionice
int minUcionica(vector<Cas>& casovi) {
// sortiramo časove na osnovu vremena njihovog početka
sort(begin(casovi), end(casovi),
[](const Cas& c1, const Cas& c2) {
return c1.pocetak < c2.pocetak;
});
// red sa prioritetom u kom su trenutno zauzete ucionce
// slozene po vremenu zavrsetka casa
struct PorediUcionice {
bool operator()(const Ucionica& u1, const Ucionica& u2) {
return u1.slobodnaOd > u2.slobodnaOd;
}
};
priority_queue<Ucionica, vector<Ucionica>, PorediUcionice>
redUcionica;
for (Cas& c : casovi) {
int brojUcionice;
if (redUcionica.empty() ||
redUcionica.top().slobodnaOd > c.pocetak)
brojUcionice = redUcionica.size() + 1;
else {
brojUcionice = redUcionica.top().broj;
redUcionica.pop();
}
c.ucionica = brojUcionice;
redUcionica.push(napraviUcionicu(c.kraj, brojUcionice));
}
// sortiramo časove na osnovu rednog broja
sort(begin(casovi), end(casovi),
[](const Cas& c1, const Cas& c2) {
return c1.broj < c2.broj;
});
return redUcionica.size();
}
int main() {
vector<Cas> casovi = ucitajCasove();
cout << minUcionica(casovi) << endl;
/*
for (const Cas& cas : casovi)
cout << cas.ucionica << " ";
cout << endl;
*/
return 0;
}