U jednom kabinetu se subotom održava obuka programiranja. Svaki nastavnik je napisao termin u kom želi da drži nastavu (poznat je sat i minut početka i sat i minut završetka časa). Odredi kako je moguće napraviti raspored časova tako da što više nastavnika bude uključeno.
Sa standardnog ulaza se učitava prvo broj \(n\) (ukupan broj nastavnika, \(1 \leq n \leq 50000\)), a zatim u \(n\) narednih redova po četiri broja razdvojena razmacima koji predstavljaju sat i minut početka tj. završetka časa (pretpostaviti da je završetak uvek iza početka).
Na standardni izlaz ispisati najveći broj nastavnika koji mogu da održe svoje časove.
7 8 15 9 20 10 45 11 30 11 20 12 45 9 30 12 40 10 20 11 20 12 00 13 00 11 30 13 30
3
Mogu se održati, na primer, časovi od 8:15 do 9:20, zatim čas od 10:20 do 11:20 i na kraju od 11:30 do 13:30.
Svaki čas možemo predstaviti parom brojeva koji predstavljaju broj minuta od prethodne ponoći do početka i do kraja časa (već prilikom učitavanja sate i minute možemo prevesti samo u minute).
Naivno rešenje se zasniva na ispitivanju svih mogućih podskupova skupa časova koji su takvi da se svi časovi mogu održati (nikoja dva časa iz tog skupa se ne seku). Presek dva intervala postoji ako i samo ako je kasniji početak časa posle ranijeg kraja časa. Generisanje svih podskupova možemo vršiti rekurzivno.
S obzirom na veliki broj podskupova koje treba ispitati ovo rešenje je veoma neefikasno (složenost mu je eksponencijalna \(O(2^n)\), gde je \(n\) ukupan broj časova).
Efikasno rešenje problema se može dobiti gramzivim pristupom. Postoji nekoliko gramzivih strategija koje je logično razmotriti, međutim, neke od njih neće garantovati optimalnost pronađenog rešenja.
Jedan pristup može biti onaj u kome prvo raspoređujemo čas koji prvi počinje. Na slici je prikazan kontra-primer, koji pokazuje da se već sa tri časa na taj način može dobiti raspored koji nije optimalan.
Jedan pristup može biti onaj u kome težimo da rasporedimo časove koji kratko traju, sa idejom da na taj način ostavljamo više prostora da se u slobodnim terminima održe drugi časovi. Na slici je prikazan kontra-primer koji pokazuje da se već sa tri časa na taj način može dobiti raspored koji nije optimalan.
Jedna gramziva strategija koja daje optimalno rešenje je sledeća. Od svih neraspoređenih časova biramo onaj koji se najranije završava i koji se može održati (ne seče se sa do sada održanim časovima, tj. počinje nakon završetka prethodnog časa). Intuitivno, takvim izborom ostavljamo što veću mogućnost za raspoređivanje naknadnih časova. Ovim dobijamo jednu rekurzivnu konstrukciju.
Ako je skup časova prazan, nema časova koji se mogu rasporediti.
U suprotnom biramo čas koji se najranije završava, odbacujemo časove koji se sa njim seku i rekurzivnom pravimo raspored za preostale časove.
Dokažimo da je ova rekurzivna formulacija korektna, tako što ćemo da dokažemo da uvek postoji ispravan, optimalan raspored (raspored sa najviše časova) u kom učestvuje čas \(c_0\) koji se prvi završava. Pretpostavimo da je \(O\) neki ispravan, optimalan raspored. Ako u njemu učestvuje čas \(c_0\), onda je \(O\) je taj traženi raspored. Ako ne učestvuje, onda pretpostavimo da je \(o_0\) čas u \(O\) koji se prvi završava. Svi drugi časovi u \(O\) počinju nakon završetka časa \(o_0\). Zaista, pošto je \(O\) ispravan, nijedan čas u \(o_i\) se ne seče sa \(o_0\), ako bi neki počinjao pre \(o_0\), tada bi morao i da se završi pre \(o_0\), što je nemoguće, jer se od svih časova u \(O\) čas \(o_0\) prvi završava. Čas \(c_0\) se ne završava kasnije nego čas \(o_0\), jer je on čas koji se prvi završava od svih časova. Dakle, čas \(c_0\) se ne seče ni sa jednim časom u \(O\) (osim eventualno sa \(o_0\)). Kada zamenimo \(c_0\) i \(o_0\), dobijamo ispravan, optimalan raspored (broj časova se nije promenio) koji sadrži \(c_0\).
Dakle, jasno je da će nas izbor časa \(c_0\) voditi do nekog optimalnog rešenja. Takođe je jasno da u tom rešenju ne može da učestvuje nijedan čas koji se seče sa \(c_0\). Ostatak časova biramo rekurzivno, pa korektnost algoritma sledi na osnovu induktivnog argumenta (pretpostavljamo da rekurzivni poziv korektno pronalazi optimalni raspored u preostalom skupu časova).
Tehnika koja je upotrebljena u prethodnom dokazu naziva se tehnika zamene tj. razmene, jer se od nekog proizvoljnog optimalnog rasporeda zamenom dobio raspored koji naša gramziva strategija bira.
Algoritam se može formulisati i iterativno. Časove možemo sortirati neopadajuće na osnovu vremena njihovog završetka i obilaziti ih u tom redosledu. Prvi čas sigurno biramo da bude održan. Redom prolazimo kroz naredne časove i ako tekući čas počinje nakon poslednjeg odabranog časa, biramo ga, a u suprotnom ga preskačemo.
Primer 9.A.1. Na slici su prikazani časovi sortirani po vremenu završetka. Gramzivom strategijom se prvo održava čas 1, zatim se čas 2 preskače (jer se preklapa sa 1), pa se zatim čas 3 održava (jer se ne preklapa sa 1, jer je desno od njega), pa se čas 4 preskače (jer se preklapa sa 3), pa se čas 5 održava (jer se ne preklapa sa 3, pa samim tim ni sa 1, jer je desno od njih), pa se časovi 6, 7 i 8 preskaču (jer se preklapaju sa časom 5), pa se čas 9 održava (jer se ne preklapa sa 5, pa samim tim ni sa 3 ni sa 1, jer je desno od njih) i na kraju se preskaču časovi 10 i 11 (jer se preklapaju sa časom 9). Maksimalan broj časova koji se mogu održati bez preklapanja je 4, međutim, časovi 1, 3, 5 i 9 nisu jedino rešenje. Moguće je, na primer, održati časove 1, 3, 6 i 11.
Ispišimo i dokaz korektnosti iterativne varijante algoritma.
Formalno, pretpostavimo da je \(O=[o_1, o_2, \ldots, o_k]\), niz časova koji predstavlja neko ispravno optimalno rešenje i dokažimo da on sadrži isti broj časova kao i raspored koji bi odabrala naša strategija. Pretpostavimo da su časovi \(o_1\) do \(o_k\) sortirani neopadajuće po redosledu njihovog završetka. Pošto se svi ti časovi mogu održati, između njih nema preklapanja i svaki naredni počinje nakon završetka prethodnog.
Neka je \(S=[s_1, s_2, \ldots, s_{k'}]\) niz časova koji bi bio odabran našom gramzivom strategijom. Pošto je \(O\) optimalan, \(S\) ne može da sadrži više časova od njega važi da je \(k \leq k'\).
Dokažimo prvo da postoji optimalan raspored \(O\) takav da za svako \(1 \leq i \leq k'\) važi da je \(o_i = s_i\). Taj raspored možemo dobiti postupnim izmenama početnog rasporeda \(O\). Pretpostavimo da postoji neko \(1 \leq i \leq k'\) tako da je \(o_i \neq s_i\) (u suprotnom je polazni raspored taj traženi). Neka je \(i\) prvi takav indeks tj. neka za svako \(1 \leq j < i\) važi da je \(o_j = s_j\). Pokažimo da se zamenom časa \(o_i\) časom \(s_i\) u nizu \(O\) dobija takođe raspored koji je ispravan (on je svakako optimalan jer se broj časova ne menja). Pokažimo prvo da se \(s_i\) ne završava kasnije nego \(o_i\).
Zaista, ako je \(i=0\), tada naša strategija bira \(s_0\) koji se prvi završava on ne može da se završava kasnije nego \(o_0\).
Ako je \(i>0\), tada znamo da se \(o_i\) mora da počinje posle \(o_{i-1}=s_{i-1}\), međutim, naša strategija za \(s_i\) bira onaj čas koji počinje nakon \(s_{i-1}\) koji se prvi završava, pa se \(s_i\) ni u ovom slučaju ne može završavati kasnije nego \(o_i\).
Ako postoje časovi u \(O\) pre časa \(o_i\), oni ostaju nepromenjeni i čas \(s_i\) se ne preklapa sa njima (jer ga je strategija bira tako da počinje nakon završetka časa \(s_{i-1} = o_{i-1}\)). Pošto se \(s_i\) ne završava kasnije nego \(o_i\) on se sigurno ne preklapa ni sa jednim časom iz \(O\) koji ide posle \(o_i\) (jer svi oni počinju i završavaju se nakon kraja časa \(o_i\)). Dakle, \(s_i\) se ne preklapa ni sa jednim časom iz \(O\) (osim eventualno sa \(o_i\), koji je u sklopu razmene uklonjen) i raspored dobijen zamenom je ispravan.
Nastavkom ovog procesa zamena stići ćemo do željenog optimalnog rasporeda \(O\) takvog da za svako \(1 \leq i \leq k'\) važi \(o_i = s_i\).
Dokažimo sada da nije moguće da važi da je \(k' < k\). Ako bi važilo da je \(k' < k\), tada bi važilo da čas \(o_{k'+1}\) pripada \(O\) a ne pripada \(S\). Pošto je \(O\) ispravan, to bi bio čas koji bi počinjao posle završetka časa \(o_{k'} = s_{k'}\). Međutim, nije moguće da takav čas postoji, jer bi on počinjao i završavao se posle časa \(s_k'\), što znači da bi naša gramziva strategija morala da ga odabere, što je u kontradikciji sa tim da se on ne nalazi u \(S\). Dakle, važi da je \(k' \geq k\).
Pošto je \(k' \geq k\) i \(k' \leq k\), važi da je \(k'=k\), pa naša gramziva strategija bira isti broj časova koji je u nekom (pa i svakom) optimalnom rasporedu. Dakle, strategijom se dobija jedan ispravan, optimalan raspored.
Primer 9.A.2. Ilustrujmo tehniku razmene na kojoj leži prethodni dokaz, tako što ćemo objasniti kako da se od rasporeda \(1, 3, 6, 11\) koji je optimalan, ali nije u skladu sa našom strategijom dobije raspored \(1, 3, 5, 9\) koji jeste u skladu sa našom strategijom.
Prvi čas gde se rasporedi razlikuju je čas \(5\) tj. \(6\). Zamenom časa \(6\), časom \(5\) dobija se raspored \(1, 3, 5, 11\), koji je takođe ispravan. Zaista, čas \(6\) se ne seče ni sa časovima \(1\) i \(3\), ni sa časom \(11\), jer je raspored \(1, 3, 6, 11\) ispravan. Čas \(5\) se ne seče sa časovima \(1\) i \(3\), jer ga u suprotnom gramziva strategija ne bi odabrala. Međutim, čas \(5\) se ne može završavati posle časa \(6\), jer se čas \(6\) ne seče sa časovima \(1\) i \(3\), a od svih časova koji se ne seku sa časovima \(1\) i \(3\), strategija bira onaj koji se najranije završava. Dakle, \(5\) se ne završava kasnije od \(6\), pa pošto se \(6\) ne seče sa \(11\) i pošto je \(11\) potpuno desno u odnosu na \(6\), ni \(5\) se ne seče sa \(11\). Dakle, raspored \(1, 3, 5, 11\) je ispravan.
U narednom koraku se upoređuju rasporedi \(1, 3, 5, 11\) i \(1, 3, 5, 9\) (koji naša strategija preporučuje). Prvi čas gde se rasporedi razlikuju je čas \(9\) tj. \(11\). Zamenom časa \(11\), časom \(9\) dobija se raspored \(1, 3, 5, 9\), koji strategija preporučuje.
Dakle, proizvoljni optimalni raspored smo razmenama transformisali u raspored koji preporučuje naša strategija, što znači da je broj časova koje naša strategija rasporedi za održavanje optimalan.
Recimo da postoji i dualno rešenje u kojem se bira onaj čas koji poslednji počinje i časovi se obilaze unazad, po nerastućem redosledu njihovog početka.
Primer 9.A.3. Na slici su prikazani časovi sortirani po redosledu početka. Prvo se održava čas 11, koji poslednji počinje, zatim se preskače čas 9 koji se sa njim preklapa, zatim se održava čas 6, nakon čega se preksaču časovi 10, 5 i 7 koji se sa njim preklapaju, zatim se održava čas 3, preskaču se časovi 8, 2 i 4 koji se sa njim preklapaju i na kraju se održava čas 1.
// casove predstavljamo uredjenim parovima (pocetak, kraj), u
// minutima
typedef pair<int, int> cas;
inline int pocetakCasa(const cas& c) {
return c.first;
}
inline int krajCasa(const cas& c) {
return c.second;
}
cas napraviCas(int pocSat, int pocMin,
int krajSat, int krajMin) {
return make_pair(pocSat*60 + pocMin, krajSat*60 + krajMin);
}
// ucitava se niz casova
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(pocSat, pocMin, krajSat, krajMin);
}
return casovi;
}
// maksimalni broj casova koji se mogu odrzati tako da nema
// preklapanja medju rasporedjenim casovima
int maksBrojCasova(vector<cas>& casovi) {
// broj casova
int n = casovi.size();
// sortiramo casove na osnovu vremena zavrsetka
sort(begin(casovi), end(casovi),
[](const cas& a, const cas& b) {
return krajCasa(a) < krajCasa(b);
});
// broj odrzanih casova
int brojOdrzanihCasova;
// kraj poslednjeg odrzanog casa
int kraj;
// rasporedjujemo prvi cas
brojOdrzanihCasova = 1;
kraj = krajCasa(casovi[0]);
// analiziramo ostale casove u redosledu zavrsetka
for (int i = 1; i < n; i++)
// ako se tekuci cas ne preklapa sa poslednjim
// rasporedjenim
if (pocetakCasa(casovi[i]) >= kraj) {
// on se odrzava
brojOdrzanihCasova++;
kraj = krajCasa(casovi[i]);
}
return brojOdrzanihCasova;
}#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
// casove predstavljamo uredjenim parovima (pocetak, kraj), u
// minutima
typedef pair<int, int> cas;
inline int pocetakCasa(const cas& c) {
return c.first;
}
inline int krajCasa(const cas& c) {
return c.second;
}
cas napraviCas(int pocSat, int pocMin,
int krajSat, int krajMin) {
return make_pair(pocSat*60 + pocMin, krajSat*60 + krajMin);
}
// ucitava se niz casova
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(pocSat, pocMin, krajSat, krajMin);
}
return casovi;
}
// maksimalni broj casova koji se mogu odrzati tako da nema
// preklapanja medju rasporedjenim casovima
int maksBrojCasova(vector<cas>& casovi) {
// broj casova
int n = casovi.size();
// sortiramo casove na osnovu vremena zavrsetka
sort(begin(casovi), end(casovi),
[](const cas& a, const cas& b) {
return krajCasa(a) < krajCasa(b);
});
// broj odrzanih casova
int brojOdrzanihCasova;
// kraj poslednjeg odrzanog casa
int kraj;
// rasporedjujemo prvi cas
brojOdrzanihCasova = 1;
kraj = krajCasa(casovi[0]);
// analiziramo ostale casove u redosledu zavrsetka
for (int i = 1; i < n; i++)
// ako se tekuci cas ne preklapa sa poslednjim
// rasporedjenim
if (pocetakCasa(casovi[i]) >= kraj) {
// on se odrzava
brojOdrzanihCasova++;
kraj = krajCasa(casovi[i]);
}
return brojOdrzanihCasova;
}
int main() {
auto casovi = ucitajCasove();
cout << maksBrojCasova(casovi) << endl;
return 0;
}U Srbiji se koriste apoeni od 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000 i 5000 dinara. Napisati program koji formira dati iznos dinara od što manjeg broja apoena (novčanica i novčića) i ispisuje upotrebljen broj apoena.
Sa standardnog ulaza se učitava jedan ceo broj između \(0\) i \(100~000\).
Na standardni izlaz napisati najmanji broj apoena potrebnih da se isplati učitani iznos novca.
243
5
\(243 = 200 + 20 + 20 + 2 + 1\).
Jedan direktan način da se problem reši je da se ispitaju sva moguća razlaganja datog iznosa na zbirove sastavljene od ovih brojeva i da se pronađe onaj zbir koji ima najmanji broj novčića (jednostavnosti radi, zanemarimo razliku između novčića i novčanica). Rešenje ovog tipa bi se moglo zasnovati na dinamičkom programiranju kombinovanom sa odsecanjem tokom pretrage.
Dokaz korektnosti nije težak i ovaj pristup je neophodno primeniti kada su novčići proizvoljni. Međutim, u situaciji u kojoj su dati veoma specifični apoeni, ovaj pristup je nepotrebno komplikovan i neefikasan. Naime specifičnosti apoena omogućavaju da se zadatak reši mnogo efikasnije.
// najmanji broj novčića potreban da se naplati iznos S kada
// su nam na raspolaganju n vrednosti novčića datih u nizu v
int minBrojNovcica(const vector<int>& v, int n, int S) {
vector<int> dp(S+1);
// iznos 0 se naplaćuje sa 0 novčića
dp[0] = 0;
// računamo minimalni broj novčića za sve ostale iznose
for (int s = 1; s <= S; s++) {
// minimalni broj novčića da se naplati iznos s
// (pretpostavljamo da iznos nije moguće naplatiti)
dp[s] = INF;
// razmatramo sve mogućnosti za poslednji novčić
for (int i = 0; i < n; i++)
// proveravamo da li je iznos s moguće naplatiti
// novčićem i
if (v[i] <= s)
// ažuriramo minimum ako je to potrebno
dp[s] = min(dp[s], dp[s-v[i]] + 1);
}
// vraćamo rezultat za iznos S
return dp[S];
}#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = numeric_limits<int>::max() - 1;
// najmanji broj novčića potreban da se naplati iznos S kada
// su nam na raspolaganju n vrednosti novčića datih u nizu v
int minBrojNovcica(const vector<int>& v, int n, int S) {
vector<int> dp(S+1);
// iznos 0 se naplaćuje sa 0 novčića
dp[0] = 0;
// računamo minimalni broj novčića za sve ostale iznose
for (int s = 1; s <= S; s++) {
// minimalni broj novčića da se naplati iznos s
// (pretpostavljamo da iznos nije moguće naplatiti)
dp[s] = INF;
// razmatramo sve mogućnosti za poslednji novčić
for (int i = 0; i < n; i++)
// proveravamo da li je iznos s moguće naplatiti
// novčićem i
if (v[i] <= s)
// ažuriramo minimum ako je to potrebno
dp[s] = min(dp[s], dp[s-v[i]] + 1);
}
// vraćamo rezultat za iznos S
return dp[S];
}
int main() {
// učitavamo iznos
int S;
cin >> S;
vector<int> v{5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1};
// izračunavamo i ispisujemo najmanji potreban broj novcica
cout << minBrojNovcica(v, v.size(), S) << endl;
return 0;
}I bez formalnog matematičkog objašnjenja, svaki prodavac u prodavnici i na pijaci zna da se optimalno rešenje dobija tako što se u svakom trenutku vraća najveći apoen koji je manji ili jednak od trenutnog iznosa i nakon toga se isti princip primenjuje na preostali iznos sve dok se ne vrati ceo kusur (u pitanju je, dakle, gramziva induktivno-rekurzivna konstrukcija). Ovo rešenje je veoma efikasno, lako se implementira, međutim, dokaz njegove korektnosti nije nimalo očigledan.
Naime, postojanje novčića od 4 dinara bi pokvarilo situaciju. 8 dinara bi se moglo dobiti od dva novčića od 4 dinara, dok bi gramziva strategija upotrebila tri novčića (od 5, 2 i 1 dinar). Dakle, dokaz korektnosti mora da uključi analizu konkretnih apoena koji su u opticaju i male promene ovih apoena mogu da utiču na to da opisani pristup daje ili ne daje uvek optimalno rešenje.
Dokažimo sada korektnost. Jednostavnosti radi, pretpostavićemo da su u opticaju samo apoeni od \(1\), \(2\), \(5\), \(10\), \(20\) i \(50\) dinara (za veće novčiće dokaz ide po istom principu). Metodom razmene dokazaćemo gornje granice broja novčića od svih apoena u optimalnom rešenju.
Optimalno rešenje ne može da sadrži više od jednog novčića od \(1\) dinar. Kada bi postojala makar dva novčića od \(1\) dinar, oni bi mogli biti zamenjeni jednim novčićem od \(2\) dinara, čime bi se broj upotrebljenih novčića smanjio, što je u kontradikciji sa pretpostavkom da je polazno rešenje optimalno. Potpuno analogno se dokazuje da optimalno rešenje ne može sadržati ni više od jednog novčića od \(10\) dinara.
Dalje, optimalno rešenje ne može sadržati više od dva novčića od \(2\) dinara. Naime, ako bi sadržalo bar tri novčića od \(2\) dinara, oni bi mogli biti zamenjeni jednim novčićem od \(1\) i jednim novčićem od \(5\) dinara, čime bi se dobilo manje rešenje, što je u kontradikciji sa pretpostavkom da je polazno rešenje optimalno. Potpuno analogno, optimalno rešenje ne može da sadrži ni više od dva novčića od \(20\) dinara.
Na kraju, u optimalnom rešenju ne može biti više od jednog novčića od \(5\) dinara. Naime, ako bi postojala bar dva, ona bi mogla biti zamenjena jednim novčićem od \(10\) dinara čime bi se dobilo manje rešenje, što je kontradikcija.
U rešenju nije moguće ni da istovremeno postoje dva novčića od \(2\) dinara i novčić od \(1\) dinara, jer bi se svi oni mogli zameniti sa jednim novčićem od \(5\) dinara, što je opet kontradikcija. Analogno važi i za novčiće od \(10\) i \(20\) dinara.
Uzevši u obzir prethodna ograničenja, razmotrimo maksimalne iznose sa optimalnim brojem novčića, koji se mogu dobiti korišćenjem samo određenih skupova novčića. Ispostaviće se da su maksimalni iznosi uvek za jedan manji od prvog većeg apoena.
Novčići od \(1\) dinar mogu da naprave najviše iznos od 1 dinara (jer se smeju pojaviti samo jednom).
Novčići od \(1\) i \(2\) dinara mogu da naprave najviše iznos od \(4\) dinara (jer može biti najviše dva novčića od \(2\) dinara i u tom slučaju se ne sme koristiti i novčić od \(1\) dinar).
Novčići od 1, 2 i 5 dinara mogu da naprave najviše iznos od 9 dinara (jer ne može biti više od jednog novčića od 5 dinara, dva novčića od 2 i jednog novčića od 1 dinara, a ako ima dva novčića od 2 dinara, ne sme se javiti i novčić od 1 dinara).
Slično, novčići od 1, 2, 5 i 10 dinara mogu da naprave najviše iznos od 19 dinara (jer se 10 dinara može javiti samo jednom, a od 1, 2 i 5 se može napraviti najviše 9).
Novčići od 1, 2, 5, 10 i 20 mogu da naprave najviše iznos od 49 dinara (jer 1, 2 i 5 mogu da naprave najviše 9, kako smo objasnili, a pošto se 10 dinara javlja najviše jednom, a 20 dinara najviše dva puta, ali ne sva tri takva zajedno, od 10 i 20 se može napraviti najviše 40).
Dokažimo sada da se za svaki pozitivan iznos u optimalnom rešenju mora nalaziti najveći novčić koji je manji ili jednak od tog iznosa (sve navedene konstatacije se odnose samo na optimalna rešenja).
Za iznos 1 javlja se samo novčić 1.
Iznosi između 2 i 4 dinara moraju da sadrže novčić 2. Naime, ne može da se javi novčić od 5 dinara, samo od novčića od 1 dinar može da se napravi najviše 1 dinara, pa za iznose od 2 do 4 dinara mora da se javi bar jedan novčić od 2 dinara.
Iznosi između 5 i 9 dinara moraju da sadrže novčić od 5 dinara. Naime, ne mogu da sadrže novčić od 10 dinara, a pošto se od novčića od samo 1 i 2 dinara može napraviti najviše 4 dinara, za iznose od 5 do 9 dinara mora da se upotrebni novčić od 5 dinara.
Iznosi između 10 i 19 dinara moraju da sadrže novčić 10. Naime, 20 dinara ne može da se javi, a pomoću novčića od 1, 2 i 5 dinara najviše se može napraviti 9 dinara.
Iznosi između 20 i 49 dinara moraju da sadrže bar jedan novčić od 20 dinara. Naime, ne mogu da sadrže 50, a samo sa 1, 2, 5 i 10 se može dobiti najviše 19.
Iznosi preko 50 dinara moraju da sadrže novčić od 50 dinara. Naime, samo sa novčićima od 1, 2, 5, 10 i 20 je moguće napraviti samo 49 dinara.
Dakle, uspeli smo da za svaki iznos pronađemo novčić koji optimalno rešenje mora da sadrži, čime onda uspevamo da smanjimo dimenziju problema i da do rešenja dođemo direktno, bez bilo kakve pretrage i isprobavanja raznih mogućnosti.
int minBrojApoena(int iznos) {
int brojApoena = 0;
vector<int> apoeni
{5000, 2000, 1000,
500, 200, 100,
50, 20, 10,
5, 2, 1};
while (iznos > 0) {
for (int apoen : apoeni)
if (iznos >= apoen) {
iznos -= apoen;
brojApoena++;
break;
}
}
return brojApoena;
}#include <iostream>
#include <vector>
using namespace std;
int minBrojApoena(int iznos) {
int brojApoena = 0;
vector<int> apoeni
{5000, 2000, 1000,
500, 200, 100,
50, 20, 10,
5, 2, 1};
while (iznos > 0) {
for (int apoen : apoeni)
if (iznos >= apoen) {
iznos -= apoen;
brojApoena++;
break;
}
}
return brojApoena;
}
int main() {
int iznos;
cin >> iznos;
cout << minBrojApoena(iznos) << endl;
return 0;
}