Choose your language!

---

|

Coin Change problem (dinamičko programiranje)

Coin Change je jedan od najpoznatijih problema dinamičkog programiranja. Zadatak je da, za datu sumu i skup kovanica, odredimo:

• minimalan broj kovanica potreban da se formira suma ili
• broj različitih načina da se suma formira pomoću kovanica.

U ovoj lekciji fokusiraćemo se na problem minimalnog broja kovanica.

---

Definicija problema

Dat je niz kovanica coins[] i ciljna suma S. Svaku kovanicu možemo koristiti neograničen broj puta. Potrebno je pronaći najmanji broj kovanica pomoću kojih se može dobiti suma S.

Primer:

• Kovanice: {1, 3, 4}
• Suma: 6

Rešenje: 2 (3 + 3 ili 4 + 1 + 1 → ali 2 je minimum)

---

Zašto dinamičko programiranje?

Problem ima:

• preklapajuće podprobleme – ista suma se računa više puta
• optimalnu podstrukturu – optimalno rešenje za sumu S zavisi od optimalnih rešenja manjih suma

Zbog toga je idealan kandidat za dinamičko programiranje.

---

DP ideja i stanje

Definišemo niz:

dp[x] = minimalan broj kovanica potreban da se dobije suma x

Početno stanje:

• dp[0] = 0 (za sumu 0 ne treba nijedna kovanica)
• sve ostale vrednosti inicijalno postavljamo na „beskonačno“

Prelaz:

dp[x] = min(dp[x], dp[x - coin] + 1)

za svaku kovanicu coin i svaku sumu x ≥ coin.

---

Bottom-up implementacija (C++)

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {

    // n - broj kovanica
    // S - ciljana suma
    int n, S;
    cin >> n >> S;

    // Učitavanje vrednosti kovanica
    vector<int> coins(n);
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }

    // dp[x] = minimalan broj kovanica za sumu x
    // Inicijalno sve postavljamo na INT_MAX (simbolično "beskonačno")
    vector<int> dp(S + 1, INT_MAX);

    // Osnovni slučaj: za sumu 0 ne treba nijedna kovanica
    dp[0] = 0;

    // Računamo dp vrednosti za sve sume od 1 do S
    for (int x = 1; x <= S; x++) {

        // Probamo svaku kovanicu
        for (int coin : coins) {

            // Ako kovanica može da se iskoristi
            // i prethodno stanje nije "beskonačno"
            if (x - coin >= 0 && dp[x - coin] != INT_MAX) {

                // Biramo manju vrednost:
                // - postojeću dp[x]
                // - ili dp[x - coin] + 1 (koristimo jednu kovanicu više)
                dp[x] = min(dp[x], dp[x - coin] + 1);
            }
        }
    }

    // Ako dp[S] ostane INT_MAX, suma se ne može formirati
    if (dp[S] == INT_MAX) {
        cout << "Nije moguce formirati sumu";
    } else {
        cout << "Minimalan broj kovanica: " << dp[S];
    }

    return 0;
}

---

Vremenska i prostorna složenost

• Vremenska složenost: O(n · S)
• Prostorna složenost: O(S)

gde je n broj kovanica, a S ciljana suma.

Vizuelizacija Coin Change problema (minimalan broj kovanica)

Prikazujemo kako se DP niz puni korak po korak za minimalan broj kovanica. Kovanice: {1, 3, 4}, Suma: 6.

Sledeći korak

Varijacije Coin Change problema

Coin Change ima više čestih varijacija:

• broj načina da se formira suma
• ograničen broj kovanica
• različit redosled kovanica se računa / ne računa

Sve ove varijante se rešavaju dinamičkim programiranjem uz male izmene stanja i prelaza.

Pored osnovnog problema minimalnog broja kovanica, Coin Change ima nekoliko čestih varijacija. Razumevanje ovih varijanti pomaže pri rešavanju složenijih zadataka iz dinamičkog programiranja.

1️⃣ Broj načina da se formira suma (redosled se ne računa)

Cilj: odrediti koliko različitih kombinacija kovanica može formirati sumu S. Svaka kovanica se može koristiti neograničeno, ali redosled kovanica nije bitan.

DP stanje: dp[x] predstavlja broj načina da se formira suma x.

// Inicijalizacija
dp[0] = 1;  // postoji 1 način da se formira suma 0: ništa ne uzimamo
for (int coin : coins) {
    for (int x = coin; x <= S; x++) {
        dp[x] += dp[x - coin]; // dodajemo sve načine da formiramo x - coin
    }
}

Primer: kovanice {1,3,4}, suma 6 → broj kombinacija = 4: - {1,1,1,1,1,1} - {1,1,4} - {3,3} - {1,1,1,3}

2️⃣ Broj načina da se formira suma (redosled se računa)

Ako je redosled kovanica bitan, DP petlje menjaju redosled:

// Inicijalizacija
dp[0] = 1;
for (int x = 1; x <= S; x++) {
    for (int coin : coins) {
        if (x - coin >= 0) {
            dp[x] += dp[x - coin]; // dodajemo sve načine iz prethodne sume
        }
    }
}

Primer: kovanice {1,3,4}, suma 6 → sada redosled stvara više načina, npr. {3,3} i {3,3} sa različitim redosledom se računaju zasebno.

Vizuelizacija Coin Change – broj načina da se formira suma

Prikazujemo kako se DP niz puni korak po korak za broj različitih kombinacija kovanica. Kovanice: {1, 3, 4}, Suma: 6. Redosled kovanica nije bitan.

Sledeći korak

Coin Change – broj načina da se formira suma (vizuelno)

Primer:

• Kovanice: {1, 2, 3}
• Ciljna suma: 4

Inicijalizacija DP niza

Definišemo dp[x] = broj načina da se formira suma x.

dp[0] = 1   // postoji 1 način da se formira suma 0: ne uzimamo ništa
dp[1..4] = 0

Početna tabela:

x	0	1	2	3	4
dp[x]	1	0	0	0	0

Korak 1: kovanica = 1

Dodajemo sve kombinacije koje završavaju sa 1:

x	0	1	2	3	4
dp[x]	1	1	1	1	1

Objašnjenje:

• dp[1] += dp[0] → 1
• dp[2] += dp[1] → 1
• dp[3] += dp[2] → 1
• dp[4] += dp[3] → 1

Korak 2: kovanica = 2

Dodajemo sve kombinacije koje završavaju sa 2:

x	0	1	2	3	4
dp[x]	1	1	2	2	3

Objašnjenje:

• dp[2] += dp[0] → 1 + 1 = 2 (kombinacije: 1+1, 2)
• dp[3] += dp[1] → 1 + 1 = 2 (kombinacije: 1+1+1, 1+2)
• dp[4] += dp[2] → 1 + 2 = 3 (kombinacije: 1+1+1+1, 1+1+2, 2+2)

Detaljno objašnjenje reda: dp[4] += dp[2]

U ovom trenutku već imamo:

• dp[4] = 1 → kombinacija: 1+1+1+1
• dp[2] = 2 → kombinacije: 1+1 i 2

Sada se pitamo:

Koliko načina postoji da napravimo 4 ako poslednja kovanica bude 2?

Ako poslednja kovanica mora biti 2, onda pre toga moramo napraviti sumu:

4 - 2 = 2

A broj načina da napravimo 2 je dp[2] = 2.

Svaku od tih kombinacija možemo produžiti dodavanjem još jedne kovanice 2:

• (1 + 1) + 2 → 1 + 1 + 2
• (2) + 2 → 2 + 2

Dakle dobijamo 2 nove kombinacije.

Pošto smo već imali 1 kombinaciju (1+1+1+1), ukupan broj postaje:

1 (stara) + 2 (nove) = 3

Zato radimo:

dp[4] += dp[2]

Intuitivno:

"Uzmi sve načine da napraviš 2 i na svaki dodaj još jednu dvojku."

Vizuelni dijagram grananja kombinacija

Posmatrajmo kako se kombinacije za sumu 4 formiraju kada obrađujemo kovanicu 2.

Znamo da je:

• dp[2] = 2 → (1+1) i (2)

Sada na svaku od tih kombinacija dodajemo još jednu kovanicu 2:

                (pravimo 4 dodavanjem 2)

                       4
                       |
            ------------------------
            |                      |
        (1+1)                  (2)
            |                      |
        (1+1)+2                (2)+2
            |                      |
        1+1+2                  2+2

Ovo su 2 nove kombinacije koje završavaju sa 2.

Zajedno sa starom kombinacijom:

1 + 1 + 1 + 1

dobijamo ukupno 3 kombinacije za sumu 4 u ovom trenutku.

Ključna intuicija

Možemo razmišljati ovako:

• dp[x] = broj svih kombinacija za x
• dp[x - coin] = broj kombinacija koje možemo proširiti dodavanjem te kovanice

Svaka kombinacija za x - coin postaje nova kombinacija za x kada dodamo još jednu kovanicu.

Zato sabiramo:

dp[x] += dp[x - coin]

Ovo je zapravo sistematsko građenje kombinacija, sloj po sloj.

Korak 3: kovanica = 3

Dodajemo sve kombinacije koje završavaju sa 3:

x	0	1	2	3	4
dp[x]	1	1	2	3	4

Objašnjenje:

• dp[3] += dp[0] → 2 + 1 = 3 (kombinacije: 1+1+1, 1+2, 3)
• dp[4] += dp[1] → 3 + 1 = 4 (kombinacije: 1+1+1+1, 1+1+2, 2+2, 1+3)

Konačan rezultat

Broj različitih kombinacija za sumu 4 je: dp[4] = 4

Ovaj pristup garantuje da redosled kovanica ne menja kombinaciju, jer svaku kovanicu obrađujemo spolja i kombinacije gradimo sistematski.

3️⃣ Ograničen broj kovanica

Ako postoji ograničenje koliko puta svaka kovanica može da se koristi, potrebno je pratiti koliko je kovanica iskorišćeno. To se obično radi 2D DP-jem:

// dp[i][x] = minimalan broj kovanica za sumu x koristeći prvih i kovanica
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
    for (int x = 0; x <= S; x++) {
        dp[i][x] = dp[i-1][x]; // ne koristimo i-tu kovanicu
        for (int k = 1; k <= limit[i] && k*coins[i-1] <= x; k++) {
            if (dp[i-1][x - k*coins[i-1]] != INT_MAX)
                dp[i][x] = min(dp[i][x], dp[i-1][x - k*coins[i-1]] + k);
        }
    }
}

Ovo je sličan princip kao kod 0/1 Knapsack problema, ali sa više kopija po kovanici.

Sve ove varijante se rešavaju dinamičkim programiranjem uz male izmene stanja i prelaza. Razumevanje ovih varijanti omogućava lakše rešavanje zadataka koji kombinuju:

• minimalan broj kovanica
• broj kombinacija
• ograničenja u upotrebi kovanica

Vizuelizacija – broj načina (redosled se računa)

Kovanice: {1,3,4} Suma: 6 Sada se različiti redosledi računaju kao različiti načini.

Sledeći korak

Vizuelizacija – ograničen broj kovanica

Kovanice: {1,3,4} Limit: {2,1,1} Suma: 6

Sledeći korak

Greedy algoritmi – kontra primer

Greedy (gramzivi) algoritmi u svakom koraku biraju trenutno najbolje rešenje, bez razmišljanja o budućim posledicama.

Nekada to daje optimalno rešenje (npr. aktivnosti sa najranijim završetkom), ali često vodi do pogrešnog rezultata.

---

Primer gde greedy NE radi

Posmatrajmo Coin Change problem:

• Kovanice: {1, 3, 4}
• Suma: 6

Greedy strategija bi glasila: „Uvek uzmi najveću moguću kovanicu.”

Koraci:

• Uzmi 4 → ostaje 2
• Uzmi 1 → ostaje 1
• Uzmi 1 → ostaje 0

Greedy rešenje koristi 3 kovanice (4 + 1 + 1).

Ali optimalno rešenje je:

• 3 + 3 = 6

što koristi samo 2 kovanice.

---

Zaključak

Greedy algoritam je doneo lokalno najbolje odluke, ali nije pronašao globalno optimalno rešenje.

Zbog toga:

• Ako problem ima optimalnu podstrukturu i preklapajuće podprobleme → verovatno je DP.
• Ako se može dokazati da lokalni optimalni izbor uvek vodi do globalnog optimuma → greedy je ispravan.

Pre nego što primeniš greedy, uvek pokušaj da pronađeš kontra primer. Ako ga pronađeš – greedy nije bezbedan izbor.

Greedy vs Dinamičko programiranje (vizuelno poređenje)

Posmatrajmo isti primer:

• Kovanice: {1, 3, 4}
• Suma: 6

---

Greedy pristup

Strategija: „Uvek uzmi najveću moguću kovanicu.”

Korak	Izabrana kovanica	Preostala suma
1	4	2
2	1	1
3	1	0

Greedy rezultat: 3 kovanice

⚠ Problem: algoritam nikada nije razmotrio kombinaciju 3 + 3.

---

Dinamičko programiranje (DP)

DP računa optimalno rešenje za svaku sumu od 0 do 6.

Definicija:

dp[x] = minimalan broj kovanica za sumu x

Dobijena tabela:

Suma x	0	1	2	3	4	5	6
dp[x]	0	1	2	1	1	2	2

DP rezultat: 2 kovanice

---

Ključna razlika

Greedy	Dinamičko programiranje
Donosi lokalnu odluku	Razmatra sva podrešenja
Ne proverava alternative	Čuva optimalne rezultate za sve manje sume
Brz i jednostavan	Sigurno daje optimalno rešenje
Može pogrešiti	Ne propušta optimalnu kombinaciju

---

Intuicija

Greedy razmišlja: „Šta je sada najbolje?”

DP razmišlja: „Šta je bilo najbolje za sve manje probleme, pa ću to iskoristiti da dobijem najbolje rešenje sada.”

Zato se DP često može posmatrati kao „sigurna verzija” greedy pristupa, koja proverava sve mogućnosti.

Veza sa drugim DP problemima

Coin Change problem je blisko povezan sa nekoliko drugih klasičnih problema dinamičkog programiranja. Razumevanje ovih veza pomaže ti da:

• lakše prepoznaš DP obrasce
• primeniš slične tehnike na različite probleme
• brže rešavaš zadatke na takmičenjima

1. 0/1 Knapsack problem

Ovo je jedan od najpoznatijih DP problema. Cilj je maksimizovati ukupnu vrednost predmeta koji staju u ranac kapaciteta W, pri čemu se svaki predmet može uzeti najviše jednom.

Coin Change problem (minimalan broj kovanica) je u suštini **poseban slučaj „Unbounded Knapsack”** — gde:

• težine predmeta odgovaraju vrednostima kovanica
• svakom „predmetu” možeš pristupiti neograničen broj puta
• cilj je minimizovati broj korišćenih predmeta (kovanica)

Sa druge strane, 0/1 Knapsack ima bitnu razliku: svaki predmet može biti uzet najviše jednom, što dovodi do drugačije DP formule i 2D DP tabele. Detaljno objašnjenje i primere možeš pogledati ovde:

DP: Problem ranca (0/1 Knapsack)

2. Subset Sum problem

Subset Sum je još jedan jednostavan ali veoma važan DP zadatak: Dat je skup brojeva i ciljna suma T. Proveriti da li postoji podskup kojem je zbir **tačno T**.

DP pristup koristi niz dp[x] koji označava da li je suma x moguća. Ovo je veoma blisko Coin Change varijanti gde samo proveravamo mogućnost formiranja sume, a ne broj načina ili minimum kovanica.

Možeš detaljno pogledati lekciju ovde:

DP: Subset Sum problem

3. Knapsack varijante – Unbounded i Bounded

Coin Change je, tehnički, **Unbounded Knapsack** problem: svaku kovanicu možemo koristiti više puta. To je zato što prelaz u DP koristi samo jednu dimenziju i dozvoljava višestruko korišćenje iste „težine”.

Ako želiš da naučiš više o svim Knapsack varijantama — 0/1, *unbounded* i *bounded* — možeš pogledati lekciju:

Priprema za takmičenja – Knapsack i varijante

4. Brojanje puteva i kombinatorni DP

Coin Change varijanta u kojoj brojimo sve načine da se formira suma je primer kombinatornog dinamičkog programiranja:

• popunjavamo niz dp[x] brojevima kombinacija
• važan je redosled petlji — prvo po kovanicama, pa po sumama

Ovaj princip se često javlja i u drugim problemima – npr. pri brojanju puteva u mreži (Grid DP) ili brojanju kombinacija podskupova. Iako još nemamo zasebnu lekciju samo o tome, ova ideja se koristi i u drugim delovima DP sekcije sajta, posebno kod problema rasporeda i kombinatorike.

5. Ostale povezane DP teme

Coin Change je primer DP problema nad brojevima i sumama – isto kao i brojne druge teme koje obrađuju DP pristup nad nizovima i stringovima:

• DP: Najduži zajednički podniz (LCS) – klasik string DP problema.
• Problemi poput Edit Distance, Grid DP ili Counting Paths takođe koriste slične ideje pojedinačnih stanja i prelaza.

Ukratko: Coin Change se uklapa u širu porodicu DP problema. Ako savladaš veze između njih, moći ćeš da:

• prepoznaš pravi DP obrazac za novi zadatak
• jasno definišeš DP stanje i prelaz
• bez problema koristiš 1D ili 2D DP u različitim situacijama

Zato je dobro da, nakon Coin Change, pogledaš i ove povezane teme — one ti grade **širu DP intuitivnost** i olakšavaju rešavanje kompleksnijih zadataka.

Zadaci za vežbu (Coin Change – DP)

Zadatak 1:

Dat je skup kovanica {1, 2, 5}. Odredi minimalan broj kovanica potreban da se formira suma 11.

Uputstvo (kratko):
Napravi DP niz dimenzije dp[0..11] gde dp[x] predstavlja minimalan broj kovanica za sumu x:

dp[0] = 0
dp[x] = min(dp[x - coin] + 1) za sve coin u {1,2,5} ako x - coin >= 0
  

Posebno obrati pažnju da se ne koristi negativni indeks.

Prikaži / sakrij uputstvo

Uputstvo — kako popuniti DP niz

Značenje ćelije:
dp[x] = minimalan broj kovanica potreban da se formira suma x.

Koraci:

1. Početno stanje: dp[0] = 0 (suma 0 se formira bez kovanica).
2. Za svaku sumu x = 1..11:
• proveri sve kovanice coin
• ako je x - coin >= 0, uzmi dp[x] = min(dp[x], dp[x-coin] + 1)

Nakon popunjavanja niza, dp[11] daje minimalan broj kovanica.

□ Savet:
Pre nego što pogledaš rešenje, pokušaj:

• Da razmisliš koje kombinacije kovanica mogu formirati 11
• Da proceniš minimalan broj kovanica intuitivno

Prikaži rešenje

⚠ Upozorenje:
Rešenje je namenjeno proveri i učenju. Pokušaj prvo sam/a.

Rešenje — minimalan broj kovanica

DP niz za sumu 0..11 (inicijalno = +∞, osim dp[0]=0):
dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

Korak po korak:

• Dodaj kovanicu 1 → dp = [0,1,2,3,4,5,6,7,8,9,10,11]
• Dodaj kovanicu 2 → dp = [0,1,1,2,2,3,3,4,4,5,5,6]
• Dodaj kovanicu 5 → dp = [0,1,1,2,2,1,2,2,3,3,2,3]

Odgovor: dp[11] = 3 (najmanje 3 kovanice: 5+5+1)

C++ implementacija

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector coins = {1,2,5};
    int S = 11;
    vector dp(S+1, 1e9);
    dp[0] = 0;

    for(int x = 1; x <= S; x++) {
        for(int coin : coins) {
            if(x - coin >= 0)
                dp[x] = min(dp[x], dp[x - coin] + 1);
        }
    }

    cout << "Minimalan broj kovanica: " << dp[S] << endl;
    return 0;
}
    

Zadatak 2:

Dat je skup kovanica {1, 2, 5}. Odredi na koliko različitih načina se može formirati suma S = 7. Redosled kovanica nije bitan.

Uputstvo (kratko):

dp[x] = broj načina da se formira suma x
dp[0] = 1
  

Prikaži / sakrij uputstvo

Kovanice se obrađuju spoljašnjom petljom kako bi se izbeglo brojanje istih kombinacija u različitom redosledu.

Za svaku kovanicu proširujemo već poznate kombinacije:

za svaku kovanicu:
  za x = coin .. S:
    dp[x] += dp[x - coin]
    

Prikaži rešenje

⚠ Upozorenje:
Rešenje pogledaj tek nakon pokušaja samostalnog rada.

C++ rešenje (broj načina)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int S = 7;
    vector coins = {1, 2, 5};

    // dp[x] = broj načina da se formira suma x
    vector dp(S + 1, 0);
    dp[0] = 1; // baza: jedna kombinacija za sumu 0

    // Spolja iteriramo po kovanicama
    for (int coin : coins) {
        for (int x = coin; x <= S; x++) {
            dp[x] += dp[x - coin];
        }
    }

    cout << dp[S]; // rezultat za sumu 7
    return 0;
}
    

Konačan rezultat se nalazi u dp[7].

Zadatak 3:

Date su kovanice:

• Vrednosti: {1, 3, 4}
• Maksimalno korišćenje: {2, 1, 1}

Odredi da li je moguće formirati sumu S = 6.

Prikaži / sakrij uputstvo

Ovo je varijacija bounded knapsack problema.

Svaku kovanicu možemo posmatrati kao poseban predmet, ali sa ograničenim brojem korišćenja.

dp[i][j] označava da li se suma j može formirati koristeći prvih i kovanica.

Prikaži rešenje

⚠ Upozorenje:
Rešenje služi za proveru logike DP prelaza.

C++ rešenje (DP sa ograničenjima)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int S = 6;
    vector value = {1, 3, 4};
    vector limit = {2, 1, 1};

    int n = value.size();
    vector> dp(n + 1, vector(S + 1, false));

    dp[0][0] = true; // suma 0 je uvek moguća

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= S; j++) {
            dp[i][j] = dp[i - 1][j]; // ne koristimo kovanicu i

            // pokušavamo da je koristimo k puta
            for (int k = 1; k <= limit[i - 1]; k++) {
                if (j >= k * value[i - 1] &&
                    dp[i - 1][j - k * value[i - 1]]) {
                    dp[i][j] = true;
                }
            }
        }
    }

    cout << (dp[n][S] ? "DA" : "NE");
    return 0;
}
    

Za ovaj primer odgovor je DA (kombinacija 1 + 1 + 4).

Zadatak 4:

Date su kovanice vrednosti {1, 3, 4}. Odredi minimalan broj kovanica potreban da se formira suma S = 6.

Svaka kovanica može biti korišćena neograničen broj puta.

Uputstvo (kratko):

dp[x] = minimalan broj kovanica za sumu x
dp[0] = 0
  

Prikaži / sakrij uputstvo

Za svaku sumu x pokušavamo da dodamo jednu od dostupnih kovanica i biramo najbolju opciju.

dp[x] = min(dp[x - coin] + 1)
    

Ako za neku sumu ne postoji rešenje, vrednost ostaje „beskonačna”.

⚠ Važno:
Pre nego što klikneš na dugme za prikaz rešenja, pokušaj samostalno:

• da izračunaš rešenje „na papiru”
• da proceniš da li greedy pristup uvek daje optimalno rešenje
• da popuniš bar prvih nekoliko vrednosti niza dp

Ovaj korak je ključan za razumevanje dinamičkog programiranja.

Prikaži rešenje

⚠ Upozorenje:
Ako nisi pokušao/la samostalno, preporučuje se da zatvoriš rešenje i pokušaš još jednom.

C++ rešenje (minimalan broj kovanica)

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int S = 6;
    vector coins = {1, 3, 4};

    // dp[x] = minimalan broj kovanica za sumu x
    vector dp(S + 1, INT_MAX);

    dp[0] = 0; // baza: za sumu 0 potrebno je 0 kovanica

    // Računamo dp vrednosti od 1 do S
    for (int x = 1; x <= S; x++) {
        for (int coin : coins) {
            if (x >= coin && dp[x - coin] != INT_MAX) {
                dp[x] = min(dp[x], dp[x - coin] + 1);
            }
        }
    }

    if (dp[S] == INT_MAX) {
        cout << "Nije moguce formirati sumu";
    } else {
        cout << "Minimalan broj kovanica: " << dp[S];
    }

    return 0;
}
    

Za ovaj primer: 6 = 3 + 3 ili 6 = 4 + 1 + 1, pa je minimalan broj kovanica 2.

Ovaj zadatak lepo pokazuje zašto greedy algoritam ne radi uvek, dok DP daje tačno rešenje.

Zadatak 4b: Rekonstrukcija iz DP niza

Nakon što smo izračunali minimalan broj kovanica pomoću DP niza, često želimo da znamo koje tačno kovanice čine optimalno rešenje.

Cilj ovog zadatka je da, pored minimalnog broja kovanica, ispišemo i konkretne vrednosti kovanica koje su korišćene.

Prikaži / sakrij uputstvo

Ideja rekonstrukcije je sledeća:

• počinje se od ciljne sume S
• traži se kovanica coin za koju važi: dp[S] = dp[S - coin] + 1
• ta kovanica je deo optimalnog rešenja
• umanjujemo sumu i nastavljamo dok ne stignemo do 0

dok je S > 0:
  pronađi coin takav da
  dp[S] = dp[S - coin] + 1
  dodaj coin u rešenje
  S = S - coin
    

Ova procedura je moguća jer DP niz čuva optimalne vrednosti za sve manje sume.

⚠ Važno:
Pre nego što pogledaš rešenje:

• pogledaj DP niz za sume od 0 do S
• pokušaj ručno da „vratiš unazad” putanju
• razmisli da li postoji više optimalnih rešenja

Prikaži rešenje

C++ rešenje sa rekonstrukcijom

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int S = 6;
    vector coins = {1, 3, 4};

    // dp[x] = minimalan broj kovanica za sumu x
    vector dp(S + 1, INT_MAX);
    dp[0] = 0;

    // Popunjavanje DP niza
    for (int x = 1; x <= S; x++) {
        for (int coin : coins) {
            if (x >= coin && dp[x - coin] != INT_MAX) {
                dp[x] = min(dp[x], dp[x - coin] + 1);
            }
        }
    }

    // Rekonstrukcija rešenja
    int cur = S;
    vector used;

    while (cur > 0) {
        for (int coin : coins) {
            if (cur >= coin &&
                dp[cur] == dp[cur - coin] + 1) {
                used.push_back(coin);
                cur -= coin;
                break; // uzimamo jednu validnu kovanicu
            }
        }
    }

    cout << "Minimalan broj kovanica: " << dp[S] << "\n";
    cout << "Kovanice koje cine resenje: ";

    for (int c : used)
        cout << c << " ";

    return 0;
}
    

Za ovaj primer, jedan od mogućih izlaza je:

Minimalan broj kovanica: 2
Kovanice koje cine resenje: 3 3
    

Napomena: u nekim slučajevima može postojati više različitih optimalnih rešenja, a DP rekonstrukcija će pronaći jedno od njih.

Zadatak 4c: Rekonstrukcija uz pomoć pomoćnog niza

U prethodnom zadatku rekonstrukcija je rađena direktnim proveravanjem DP niza. Sada ćemo koristiti poseban niz koji pamti koji izbor je doveo do optimalnog rešenja.

Ovaj pristup je vrlo čest u praksi i koristi se i kod:

• 0/1 Knapsack problema
• Edit Distance algoritma
• Najkraćih puteva u grafovima

Prikaži / sakrij uputstvo

Pored DP niza uvodimo niz choice[x]:

• dp[x] – minimalan broj kovanica za sumu x
• choice[x] – vrednost kovanice koja je poslednja dodata da bi se dobilo optimalno dp[x]

Kada god pronađemo bolju opciju:

dp[x] = dp[x - coin] + 1
choice[x] = coin
    

Nakon popunjavanja nizova, rešenje se rekonstruiše jednostavnim „hodanjem unazad”.

⚠ Važno:
Pre prikaza rešenja pokušaj da odgovoriš:

• šta predstavlja choice[x]
• zašto je dovoljno zapamtiti samo jednu kovanicu po sumi
• da li se ovim pristupom gube neka optimalna rešenja

Prikaži rešenje

C++ rešenje sa `choice[]` nizom

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int S = 6;
    vector coins = {1, 3, 4};

    // dp[x] = minimalan broj kovanica za sumu x
    vector dp(S + 1, INT_MAX);

    // choice[x] = kovanica koja je poslednja dodata za optimalno dp[x]
    vector choice(S + 1, -1);

    dp[0] = 0; // baza

    // Popunjavanje DP i choice nizova
    for (int x = 1; x <= S; x++) {
        for (int coin : coins) {
            if (x >= coin && dp[x - coin] != INT_MAX) {
                if (dp[x] > dp[x - coin] + 1) {
                    dp[x] = dp[x - coin] + 1;
                    choice[x] = coin; // pamtimo izbor
                }
            }
        }
    }

    if (dp[S] == INT_MAX) {
        cout << "Nije moguce formirati sumu";
        return 0;
    }

    // Rekonstrukcija
    cout << "Minimalan broj kovanica: " << dp[S] << "\n";
    cout << "Kovanice u resenju: ";

    int cur = S;
    while (cur > 0) {
        cout << choice[cur] << " ";
        cur -= choice[cur];
    }

    return 0;
}
    

Za sumu S = 6, jedan mogući izlaz je:

Minimalan broj kovanica: 2
Kovanice u resenju: 3 3
    

Napomena: Ako postoji više optimalnih rešenja, ovaj pristup će rekonstruisati jedno od njih — ono koje je prvo pronađeno tokom DP popunjavanja.

Zadatak 4d: Kako se popunjava DP niz — vizuelno

U ovom delu ne pišemo novi kod, već vizuelno pratimo kako se popunjavaju nizovi dp i choice za problem minimalnog broja kovanica.

Podsetnik:

• Kovanice: {1, 3, 4}
• Ciljna suma: S = 6

Prikaži / sakrij objašnjenje

Posmatramo niz dp[x] za sve sume od 0 do 6.

Svaka ćelija sadrži:

• dp[x] — minimalan broj kovanica
• choice[x] — kovanica koja je poslednja dodata

Ako u nekom trenutku ne postoji rešenje, dp[x] ostaje ∞.

Korak 0 — početno stanje

Suma (x)	0	1	2	3	4	5	6
dp[x]	0	∞	∞	∞	∞	∞	∞
choice[x]	-	-	-	-	-	-	-

Korak 1 — suma x = 1

Možemo koristiti kovanicu 1:

dp[1] = dp[0] + 1 = 1
choice[1] = 1
  

Korak 2 — suma x = 2

Najbolje je koristiti dve kovanice od 1:

dp[2] = dp[1] + 1 = 2
choice[2] = 1
  

Korak 3 — suma x = 3

Kovanica 3 daje bolje rešenje nego tri jedinice:

dp[3] = dp[0] + 1 = 1
choice[3] = 3
  

Korak 4 — suma x = 4

Najbolja opcija je kovanica 4:

dp[4] = dp[0] + 1 = 1
choice[4] = 4
  

Korak 5 — suma x = 5

Moguće opcije:

• 4 + 1 → 2 kovanice
• 3 + 1 + 1 → 3 kovanice

dp[5] = dp[4] + 1 = 2
choice[5] = 1
  

Korak 6 — suma x = 6

Najbolje rešenje:

• 3 + 3 → 2 kovanice

dp[6] = dp[3] + 1 = 2
choice[6] = 3
  

Konačni DP i choice niz

Suma (x)	0	1	2	3	4	5	6
dp[x]	0	1	2	1	1	2	2
choice[x]	-	1	1	3	4	1	3

Rekonstrukcija:

6 → 6 - 3 = 3
3 → 3 - 3 = 0
  

Rešenje: 3 + 3

Zadatak 4e: Animirani DP — sa isticanjem koraka

Klikom na dugme vidiš kako se DP niz popunjava i koja suma se trenutno obrađuje.

Kovanice: {1, 3, 4}
Ciljna suma: 6

Sledeći korak

---