Gramzivi algoritmi (Greedy)

Gramzivi algoritmi (eng. greedy algorithms) predstavljaju tehniku koja gradi rešenje korak po korak, uvek birajući najbolju lokalnu odluku u datom trenutku. Glavna filozofija je: uzmi ono što ti se trenutno čini najbolje, bez razmišljanja o tome kako će ta odluka uticati na budućnost, u nadi da će niz takvih izbora dovesti do globalno optimalnog rešenja.

Ideja je jednostavna: jednom doneta odluka se nikada ne preispituje niti se algoritam vraća unazad (nema backtracking-a).

Kako razmišlja gramzivi algoritam?

Gramzivi algoritam u svakom koraku bira ono što trenutno izgleda kao najbolje rešenje.

Ne razmišlja o svim mogućim kombinacijama, već donosi odluku odmah.

• uzima najveći novčić
• bira najkraći sledeći korak
• uzima aktivnost koja se najranije završava

Ideja: "Uzmi najbolje sada — nadaj se da će biti najbolje ukupno"

Primer 1: Postupak i vizuelni primer: Vraćanje kusura

Zamisli da treba da vratiš 62 dinara kusura koristeći što manji broj kovanica (apoeni: 50, 20, 10, 5, 1). Gramzivi algoritam bi sledio ove korake:

• Korak 1: Uzmi najveću moguću kovanicu koja ne prelazi 62. To je 50. (Ostaje: 12)
• Korak 2: Uzmi najveću moguću kovanicu za 12. To je 10. (Ostaje: 2)
• Korak 3: Uzmi najveću moguću kovanicu za 2. To je 1. (Ostaje: 1)
• Korak 4: Uzmi još jednu kovanicu od 1. (Ostaje: 0)

U ovom slučaju, dobili smo optimalno rešenje od ukupno 4 kovanice.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void vratiKusur(int iznos) {
    // Skup dostupnih apoena (sortiran od najvećeg ka najmanjem)
    // Gramzivi algoritam uvek počinje od najveće vrednosti
    vector<int> apoeni = {50, 20, 10, 5, 1};
    vector<int> rezultat;

    int preostalo = iznos;

    // Prolazimo kroz svaki apoen
    for (int i = 0; i < apoeni.size(); i++) {
        
        // Dokle god je trenutni apoen manji ili jednak preostalom iznosu
        // mi ga "gramzivo" uzimamo
        while (preostalo >= apoeni[i]) {
            preostalo -= apoeni[i];     // Smanjujemo dug
            rezultat.push_back(apoeni[i]); // Dodajemo novčić u novčanik
        }
    }

    // Ispis rezultata
    if (preostalo == 0) {
        cout << "Kusur za " << iznos << " dinara je: ";
        for (int novcic : rezultat) {
            cout << novcic << " ";
        }
        cout << endl << "Ukupno kovanica: " << rezultat.size() << endl;
    } else {
        // Ovo se dešava ako gramzivi algoritam ne može da reši problem 
        // (npr. ako nemamo kovanicu od 1 dinar, a ostane nam kusur)
        cout << "Greška: Gramzivi algoritam nije mogao da vrati tačan iznos!" << endl;
    }
}

int main() {
    int kusur = 62;
    vratiKusur(kusur);
    return 0;
}
    

Da li je gramzivi pristup uvek ispravan?

Odgovor je: NE. Gramzivi algoritmi su "kratkovidi". Ponekad trenutno najbolji potez može blokirati put do stvarno najboljeg ukupnog rešenja.

Primer neuspeha: Treba vratiti 40 dinara, a dostupni apoeni su 25, 20 i 1.
• Greedy: Uzima 25, pa mu ostaje 15, što mora vratiti sa petnaest jedinica. Ukupno 16 kovanica.
• Optimalno: Dve kovanice od po 20. Ukupno 2 kovanice.

Zašto greedy nekad radi, a nekad ne?

Kao što smo videli, gramzivi algoritam ne daje uvek najbolje rešenje. Da bismo znali kada možemo da ga koristimo, postoje određena pravila.

Ova tehnika daje pouzdane rezultate samo ako problem zadovoljava dva ključna svojstva:

• Svojstvo gramzivog izbora: Globalno optimalno rešenje se može postići pravljenjem lokalno optimalnih izbora.
• Optimalna podstruktura: Optimalno rešenje celog problema sadrži u sebi optimalna rešenja njegovih podproblema.

Primeri gde je greedy uspešan: Odabir aktivnosti, Huffmanovo kodiranje, Dijkstrin algoritam, Kruskalov i Primov algoritam.

Primeri gde greedy obično ne radi: Problem ranca (0/1 Knapsack), Problem trgovačkog putnika (TSP).

Osnovna struktura koda

while (postoji moguća odluka):
    x = izaberi najbolju lokalnu opciju (npr. najveću kovanicu ili najkraći put)
    if (x je izvodljivo):
        dodaj x u rešenje
    ažuriraj preostali deo problema
    

Primer 2: Odabir aktivnosti (Activity Selection)

Cilj je odabrati najveći broj aktivnosti koje se ne preklapaju. Greedy strategija: uvek biraj aktivnost koja se najranije završava.

// Sortiramo po vremenu završetka (a.second)
sort(aktivnosti.begin(), aktivnosti.end(), [](auto &a, auto &b){ return a.second < b.second; });

int poslednji_kraj = -1, broj = 0;
for (auto &a : aktivnosti){
    if (a.first >= poslednji_kraj){
        broj++;
        poslednji_kraj = a.second;
    }
}
    

Logika: Što se ranije jedna aktivnost završi, ostaje nam više prostora za ostale.

Prednosti i mane

Zaključak

Gramzivi algoritmi su elegantni i efikasni, ali zahtevaju oprez. Ako lokalni optimum ne garantuje globalni, potrebno je koristiti složenije tehnike poput dinamičkog programiranja.

Napredni greedy: pokrivanje celog alfabeta

U nekim problemima greedy se ne koristi za izbor minimuma ili maksimuma, već za praćenje kompletiranih skupova elemenata.

Tipičan primer je rad sa niskama gde želimo da pratimo koliko puta smo uspeli da "sakupimo" sva slova alfabeta.

Ideja:

• Prolazimo kroz nisku s leva na desno
• Vodimo evidenciju koja su slova viđena
• Kada sakupimo svih K različitih slova → pravimo "reset"
• Broj takvih kompletiranja direktno utiče na rešenje

set = prazan skup
broj_setova = 0

za svaki karakter c u stringu:
    dodaj c u skup

    ako skup sadrži svih K slova:
        broj_setova++
        očisti skup

Ključna ideja: svaki put kada sakupimo svih K slova, znamo da smo "potrošili" jednu kompletnu kombinaciju.

Ova tehnika se često koristi u zadacima gde se traži:

• minimalna dužina nečega što nedostaje
• broj potrebnih segmenata
• ili analiza pokrivenosti svih mogućih izbora

U sledećem primeru videćemo kako se ova ideja koristi za rešavanje konkretnog takmičarskog problema.

Zašto greedy ovde radi?

Možda deluje da je potrebno isprobati sve moguće podnizove, što bi bilo presporo (eksponencijalno).

Međutim, greedy radi jer važi sledeće svojstvo:

• Ako nismo sakupili svih K slova → postoji string dužine 1 koji nije podniz
• Kada prvi put sakupimo svih K slova → svi stringovi dužine 1 postoje
• Kada sakupimo 2 puta → svi stringovi dužine 2 mogu postojati

Drugim rečima:

broj kompletnih prolaza kroz alfabet određuje minimalnu dužinu nepodniza

Zato greedy odluka:

• „sakupljaj dok ne dobiješ svih K slova“

daje globalno optimalno rešenje.

Primer 3: Najmanji neviđeni podniz (Missing Subsequence)

Imamo dugačku nisku (string) S koja se sastoji od slova alfabeta veličine K. Želimo da pronađemo dužinu najkraćeg mogućeg stringa koji nije podniz (ne mora biti uzastopan) niske S.

Ovo je savršen zadatak za napredni greedy pristup sa kompletiranjem skupova: da bi najkraći nedostajući niz bio što duži, moramo "potrošiti" što više kompletnih kombinacija slova.

Lokalna odluka: svaki put kada kompletiramo skup od K različitih slova, taj segment smatramo jednim "nivoom" koji smo prešli. Naše rešenje je broj kompletiranih nivoa plus jedan.

#include <iostream>
#include <string>
#include <set>

using namespace std;

// Funkcija pronalazi minimalnu dužinu podniza koji nedostaje
int duzinaNajkracegNedostajucegPodniza(string text, int K) {
    set<char> vidjenaSlova;
    int kompletiraniSetovi = 0;

    // Greedy: prolazimo kroz tekst s leva na desno
    for (char karakter : text) {
        // Dodajemo karakter u trenutni skup
        vidjenaSlova.insert(karakter);

        // Ključna provera: ako skup sadrži svih K slova alfabeta
        if (vidjenaSlova.size() == K) {
            kompletiraniSetovi++; // Potrošili smo jedan segment
            vidjenaSlova.clear();   // RESET: počinjemo od nule za sledeći sloj
        }
    }

    // Rezultat: broj kompletiranih nivoa + 1.
    // To je najmanja dužina niza za koji ne možemo da garantujemo da postoji.
    return kompletiraniSetovi + 1;
}

int main() {
    // Primer: DNK sekvenca sa K=4 alfabeta (A, G, C, T)
    string text = "AGCTAGGCTACGTCA";
    int K = 4; // A, G, C, T
    
    // Za ovaj tekst:
    // [AGCT] (1), [AGGCTA] (2), [CGT] (nepotpun) -> 2 + 1 = 3
    // Najkraći nedostajući niz je dužine 3 (npr. 'AAA' ili 'GGG')
    cout << duzinaNajkracegNedostajucegPodniza(text, K) << endl; 
    return 0;
}

Analiza: Složenost je $O(N \cdot \log K)$ zbog korišćenja `std::set`, što je izuzetno efikasno. Bez ove greedy logike, problem bi bio eksponencijalan. Slika ispod ilustruje ovaj proces scan-and-reset na dugačkom stringu, pokazujući kako se formiraju kompletirani nivoi.

Objašnjenje algoritma: Najmanji nepodniz

Zadatak traži da za svaki prefiks stringa pronađemo dužinu najkraćeg stringa koji nije njegov podniz.

Podniz je string koji možemo dobiti brisanjem nekih karaktera, ali uz očuvanje redosleda.

Kako algoritam radi?

Kroz string prolazimo sleva nadesno i održavamo skup različitih karaktera koje smo videli.

• Dodajemo svako novo slovo u skup
• Kada skup sadrži svih K slova → kompletirali smo jedan "set"
• Tada povećavamo brojač i resetujemo skup

Veza sa rezultatom

Ako smo uspeli da kompletiramo C setova, to znači:

• svi podnizovi dužine ≤ C postoje
• ali neki podniz dužine C+1 ne postoji

Objašnjenje slike (korak po korak)

Posmatrajmo string: abcbaca i K = 3 (slova a, b, c)

Intuicija (najvažnije)

Zamisli da skupljaš sličice:

• kada sakupiš sva slova → završio si jedan nivo
• svaki nivo garantuje da postoje svi podnizovi određene dužine

Broj završenih nivoa određuje koliko su "kratki" svi postojeći podnizovi.

Zašto je algoritam efikasan?

• prolazimo kroz string samo jednom → O(N)
• koristimo niz veličine K → O(K)

Kako čitati ovu vizualizaciju?

Na slici je prikazan proces pronalaženja najkraćeg nepodniza za string abcabca kada je K = 3 (slova a, b, c).

String se prolazi sleva nadesno i deli na segmente (nivoe) u kojima se pojavljuju sva slova abecede.

Nivo 1

U prvom delu vidimo karaktere a, b, c. Kada sakupimo sva tri slova, kompletiramo prvi set.

• To znači da svi podnizovi dužine 1 postoje

Nivo 2

Zatim ponovo skupljamo slova: b, a, c. Opet imamo sva slova → kompletiran drugi set.

• Sada znamo da postoje svi podnizovi dužine 2

Nivo 3 (nepotpun)

Na kraju ostaje samo a, što nije dovoljno da se kompletira novi set.

Šta znači nepodniz?

Nepodniz je string koji ne možemo dobiti brisanjem karaktera iz originalnog stringa.

U ovom slučaju, neki string dužine 3 ne postoji kao podniz — i to je odgovor.

Rešenje zadatka: Najmanji nepodniz za svaki prefiks

Ovaj problem rešavamo efikasno koristeći ideju "slojeva" (layering).

Prolazimo kroz string i pratimo koje smo karaktere videli. Kada sakupimo svih K različitih slova, kompletirali smo jedan nivo.

Za svaki prefiks odgovor je: broj kompletiranih nivoa + 1

#include 
#include 

using namespace std;

// Niz za praćenje da li smo videli karakter
bool vidjen[26];

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    cin >> N >> K;

    string S;
    cin >> S;

    int broj_setova = 0;        // koliko puta smo videli svih K slova
    int trenutno_razlicitih = 0; // koliko različitih slova trenutno imamo

    for (int i = 0; i < N; i++) {

        int c = S[i] - 'a'; // pretvaramo slovo u indeks (0 do K-1)

        // Ako ovo slovo još nismo videli u trenutnom "setu"
        if (!vidjen[c]) {
            vidjen[c] = true;
            trenutno_razlicitih++;
        }

        // Ako smo sakupili svih K slova
        if (trenutno_razlicitih == K) {

            broj_setova++; // završili smo jedan nivo

            // resetujemo za sledeći nivo
            trenutno_razlicitih = 0;

            for (int j = 0; j < K; j++) {
                vidjen[j] = false;
            }
        }

        // Rezultat za trenutni prefiks:
        // broj kompletiranih nivoa + 1
        cout << broj_setova + 1;

        if (i != N - 1) cout << " ";
    }

    cout << endl;

    return 0;
}

Objašnjenje kako algoritam radi

Posmatrajmo string: abcbaca i K = 3 (slova a, b, c)

Zašto ovo radi?

Kada sakupimo svih K slova, to znači da:

• svi podnizovi dužine 1 postoje
• kombinovanjem više nivoa dobijamo sve dužine do C

Ako imamo C kompletiranih nivoa:

• svi podnizovi dužine ≤ C postoje
• ali neki podniz dužine C+1 ne postoji

Složenost algoritma

• Vremenska složenost: O(N)
• Memorijska složenost: O(K)

Greedy optimizacije sa akumulacijom efekata

U ovoj lekciji obrađujemo posebnu klasu problema u kojima se greedy odluka ne vidi odmah, već se mora otkriti kroz analizu kako se efekti sabiraju tokom vremena.

Ovakvi zadaci često izgledaju kao simulacija ili dinamičko programiranje, ali se u suštini svode na pametan izbor akcije po koraku + akumulaciju efekta kroz ceo proces.

Ključna ideja

Umesto da pratimo celu simulaciju korak po korak, posmatramo:

• kako svaka odluka utiče na buduće korake
• kako se efekti sabiraju kroz vreme
• i kako možemo unapred izračunati ukupni doprinos

Na taj način, problem se često može svesti na jednostavnu optimizaciju po koraku.

Vizuelna intuicija — akumulacija efekta

Zamisli sledeći proces kroz vreme:

Potez:   1     2     3     4     5
         |-----|-----|-----|-----|

Otrov:   +2    +2    +2    +2    +2
         (akumulira se kroz sve naredne poteze)

Direktni napad: utiče samo u trenutnom potezu

□ Ključna ideja:

• otrov ima trajni efekat
• direktni napad ima trenutni efekat
• zato odluka nije lokalna, već vremenski zavisna

Kako izgleda “naivna” simulacija

za svaki potez:
    izračunaj trenutnu štetu
    dodaj nove efekte
    ponovo prolazi kroz sve prethodne otrove

❌ Ovo je presporo jer stalno ponavljamo iste sabirke.

Kako razmišljamo efikasno

Umesto simulacije, posmatramo:

• ukupan doprinos svakog poteza unapred
• koliko svaki izbor “vredi” na globalnom nivou

To vodi do sledeće transformacije:

• problem iz vremenske simulacije → problem sabiranja doprinosa

Veza sa dinamičkim programiranjem

Iako rešenje izgleda kao greedy, u pozadini postoji DP ideja:

• razmatramo optimalan rezultat za prvih k poteza
• svaki korak zavisi od prethodnih odluka

Međutim, DP tabelu ne moramo eksplicitno da čuvamo jer:

• stanje se može “sažeti” u kumulativne vrednosti
• prelazi se zamenjuju matematičkom formulom

□ Ovo je čest obrazac u takmičarskim zadacima: DP ideja → optimizovana u greedy/matematičko rešenje

Mini intuicija za učenike

Zapamti sledeće pravilo:

• Ako efekat jedne odluke traje kroz više koraka → ne možeš gledati samo trenutni potez
• Ako se efekti sabiraju → probaj da ih “izvučeš ispred petlji”
• Ako vidiš simulaciju → pitaj se da li postoji formula umesto nje

Tipični obrasci ovog tipa problema

• otrov / efekti kroz vreme
• buff/debuff sistemi u igrama
• kumulativni doprinos odluka
• offline izračunavanje rezultata

Zaključak

Greedy algoritmi u naprednim zadacima nisu samo “biraj najbolje sada”, već:

pretvori problem tako da se globalni efekat može izračunati lokalnim odlukama

Upravo u tome leži razlika između osnovnih i takmičarskih greedy problema.