Dinamičko programiranje: Problem ranca (Knapsack problem)

Problem ranca je jedan od najpoznatijih i najvažnijih problema u oblasti dinamičkog programiranja. Učenici ga često sreću na takmičenjima iz informatike jer zahteva jasno razumevanje definicije stanja, prelaza i odnosa podproblema.

Šta je 0/1 Knapsack problem?

Zamislimo da imamo ranac maksimalne nosivosti W i N predmeta. Za svaki predmet poznate su dve vrednosti:

težina w[i]
vrednost v[i]

Predmet se može:

uzeti u potpunosti
ili ne uzeti uopšte

Zato se ova verzija naziva 0/1 knapsack (0 = ne uzimamo predmet, 1 = uzimamo ga).

Ovaj problem se često pojavljuje u optimizaciji, kombinatorici, algoritmima i informatičkim takmičenjima. U suštini, pokušavamo da pronađemo najbolju kombinaciju predmeta tako da:

ukupna težina ne prelazi kapacitet ranca W
ukupna vrednost izabranih predmeta bude što veća

Vrednost predmeta (v[i]) može predstavljati različite stvari u praksi:

profit ili cenu koju predmet donosi,
korisnost ili važnost predmeta,
broj poena, ili bilo koju merljivu kvantitativnu korist koju predmet daje,
u igricama ili simulacijama – snagu, iskustvo, resurse itd.

Iako jednostavno zvuči, ovaj problem je vrlo poznat jer predstavlja jedan od najklasičnijih primera primene dinamičkog programiranja.

Slika 1: 0/1 Problem ranca u dinamičkom programiranju

Opis zadatka

Data su N predmeta, pri čemu svaki predmet ima:

težinu – ceo broj w[i]
vrednost – ceo broj v[i]

Takođe je dat i ranac maksimalne nosivosti W. Potrebno je odabrati podskup predmeta tako da:

ukupna težina izabranih predmeta ne prelazi W,
a zbir njihovih vrednosti bude maksimalan.

Svaki predmet se može izabrati najviše jednom. Predmeti se ne mogu seći, deliti ili uzimati više puta – uzimamo ih samo potpuno ili ih uopšte ne uzimamo.

Zadatak:
Izračunati maksimalnu ukupnu vrednost predmeta koje je moguće staviti u ranac kapaciteta W.

Primer sa konkretnim brojevima

Ulaz:

Broj predmeta: N = 3
Težine predmeta: w = {1, 3, 4}
Vrednosti predmeta: v = {15, 20, 30}
Maksimalna težina ranca: W = 4

Objašnjenje:

Predmet 1: težina = 1, vrednost = 15
Predmet 2: težina = 3, vrednost = 20
Predmet 3: težina = 4, vrednost = 30

Optimalno rešenje je da izaberemo predmete 1 i 2: ukupna težina = 1 + 3 = 4 (≤ W), ukupna vrednost = 15 + 20 = 35, što je maksimalno moguće.

Izlaz:

Maksimalna ukupna vrednost: 35
Izabrani predmeti: {1, 2} (ili njihove težine/vrednosti: {(1,15),(3,20)})

Rešenje se može dobiti korišćenjem dinamičkog programiranja, bilo top-down (memoizacija) ili bottom-up (tabulacija).

Naivno rešenje i motivacija za dinamičko programiranje

Pre nego što pređemo na efikasno DP rešenje, važno je razumeti kako izgleda naivni pristup. U najjednostavnijoj verziji, probamo sve moguće podskupove predmeta (svaki predmet uzeti ili ne uzeti).

Međutim, broj kombinacija je 2^N. Za N = 30, to je već preko milijardu mogućnosti. Zbog toga je brut-force pristup previše spor i ne može se koristiti na takmičenjima.

Zato uvodimo dinamičko programiranje: umesto da stalno ponavljamo iste proračune, DP pamti rezultate podproblema i koristi ih da bi rešio problem u razumnom vremenu.

Za takmičenja: važne napomene

Obrati pažnju na granice: N i W uvek proveriti u tekstu zadatka.
Tipovi promenljivih – težine i vrednosti često mogu biti veliki. Koristi long long u C++.
Rubni ulazi:
- W = 0
- N = 0
- svi predmeti teži od W
- postoji jedan predmet koji tačno staje u W
Uvek proveriti da li se traži i rekonstrukcija rešenja (koji su predmeti uzeti).

Vremenska složenost, ograničenja i kada DP ne radi

Standardno DP rešenje radi u složenosti O(N · W). Ovo je mnogo bolje od 2^N, ali ima jednu važnu osobinu: to vreme zavisi direktno od vrednosti W.

Zato kažemo da je DP za 0/1 Knapsack pseudo-polynomial algoritam – nije polinom u broju bitova ulaza, već u samoj vrednosti W.

Kada DP rešenje ne radi?

kada je W veoma veliki broj (npr. 10⁷, 10⁸ ili više)
kada memorija ne može da drži DP tabelu

U takvim slučajevima koriste se alternativne metode:

rešenje po vrednostima umesto po težinama (drugi DP pristup)
meet-in-the-middle (za N do oko 40)
branch & bound ili backtracking sa heuristikama
aproksimacije i FPTAS algoritmi

Definicija DP stanja

Definišemo:

dp[i][j] = maksimalna vrednost koju možemo postići koristeći
           prvih i predmeta, ako je preostala nosivost ranca j.

Početni slučajevi

dp[0][j] = 0 → Bez predmeta vrednost je 0
dp[i][0] = 0 → Ako je nosivost 0, vrednost je 0

Prelaz

Ako je predmet pretežak:

ako w[i] > j:
    dp[i][j] = dp[i-1][j]

Ako može da stane, biramo bolju opciju:

dp[i][j] = max(
    dp[i-1][j],                 // ne uzimamo predmet
    dp[i-1][j - w[i]] + v[i]    // uzimamo predmet
)

Implementacija u C++ (sa objašnjenjima)

U ovom programu koristimo dinamičko programiranje da rešimo klasični 0/1 Knapsack problem. Formiramo DP tabelu dimenzija (N+1) × (W+1), gde:

i predstavlja prvih i predmeta koje razmatramo,
j predstavlja kapacitet ranca od 0 do W,
dp[i][j] predstavlja maksimalnu vrednost koju možemo postići koristeći prvih i predmeta i kapacitet j.

Svaki red u tabeli odgovara tome da uključujemo sve više predmeta (1, 2, 3, ..., N). Svaka kolona odgovara mogućem kapacitetu ranca (od 0 do W).

Na osnovu toga određujemo dva izbora:

Ne uzeti predmet i — vrednost ostaje ista kao u dp[i-1][j]
Uzeti predmet i (ako njegova težina ≤ j) — tada gledamo dp[i-1][j−w[i]] + v[i]

Glavni cilj je da pronađemo dp[N][W] — najbolji mogući rezultat koristeći sve predmete i maksimalni kapacitet ranca.


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

int main() {
    int N, W;
    cin >> N >> W;  
    // N = broj predmeta
    // W = maksimalni kapacitet ranca

    vector<int> w(N+1), v(N+1);
    for (int i = 1; i <= N; i++)
        cin >> w[i] >> v[i];  
        // w[i] = težina i-tog predmeta
        // v[i] = vrednost i-tog predmeta

    // Kreiramo DP tabelu veličine (N+1) x (W+1)
    // dp[i][j] = najbolja moguća vrednost koristeći prvih i predmeta i kapacitet j
    vector<vector<<int>> dp(N+1, vector<int>(W+1, 0));

    // Popunjavanje DP tabele
    for (int i = 1; i <= N; i++) {        // razmatramo i-ti predmet
        for (int j = 1; j <= W; j++) {    // kapacitet ranca od 1 do W

            // Opcija 1: NE uzimamo i-ti predmet
            dp[i][j] = dp[i-1][j];

            // Opcija 2: Uzeti predmet (ako staje u preostali kapacitet)
            if (w[i] <= j) {
                dp[i][j] = max(
                    dp[i][j],                   // ne uzimamo predmet
                    dp[i-1][j - w[i]] + v[i]    // uzimamo predmet
                );
            }
        }
    }

    // Konačan odgovor: najbolja moguća vrednost sa svim predmetima i punim kapacitetom
    cout << dp[N][W];
}

Primer — vizualizacija DP tabele

Kako se formira tabela u ovom primeru?

Za N = 4 predmeta i kapacitet ranca W = 7 formira se DP tabela sa brojem redova = 5 (od 0 do 4) i brojem kolona = 8 (od 0 do 7).

Red i znači: razmatramo prvih i predmeta.
Kolona j znači: maksimalni kapacitet ranca je j.

Svaka ćelija dp[i][j] govori: koja je najveća vrednost koju mogu postići koristeći predmete 1..i i kapacitet j.

Pretpostavimo da imamo ranac kapaciteta W = 7 i 4 predmeta:

Predmet	Težina	Vrednost
1	1	1
2	3	4
3	4	5
4	5	7

DP tabela sa redovima koji odgovaraju predmetima:

i\j	1	2	3	4	5	6	7
0 (nema predmeta)	0	0	0	0	0	0	0
1 (predmet 1: w=1, v=1)	1	1	1	1	1	1	1
2 (predmet 2: w=3, v=4)	1	1	4	5	5	5	5
3 (predmet 3: w=4, v=5)	1	1	4	5	6	6	9
4 (predmet 4: w=5, v=7)	1	1	4	5	7	8	9

Važna napomena:
U poslednjem polju dp[4][7] ne možemo staviti vrednost 11 jer bi to zahtevalo uzimanje predmeta 2 i 4: 3 + 5 = 8 > 7 — prelazi kapacitet ranca, pa kombinacija nije dozvoljena.

Optimalno rešenje je uzimanje predmeta 2 i 3 → ukupna vrednost = 4 + 5 = 9.

Zaključak

Problem ranca je klasičan zadatak na takmičenjima jer zahteva razumevanje:

strukture podproblema
formiranja DP stanja
optimalnih prelaza
analize vremena i memorije

Učenici koji savladaju ovaj zadatak kasnije lako prelaze na:

Unbounded Knapsack
Subset Sum
Coin Change
Partition problem

Dodatni materijali — još primera i vizuelno objašnjenje

Da bi se lakše razumela tecnika dinamičkog programiranja kod problema ranca, ispod se nalazi vizuelni prikaz DP tabele, dodatni zadatak za vežbu, i naprednija implementacija koja optimizuje memoriju na O(W).

1. Vizuelna DP tabela (primer)

Posmatrajmo sledeće podatke:

Težine: {1, 3, 4}
Vrednosti: {15, 20, 30}
Maksimalna težina ranca: W = 4

DP tabela (red = broj prvih razmatranih predmeta, kolona = težina ranca):

i \ w	1	2	3	4
0 predmeta	0	0	0	0
1. predmet (1,15)	15	15	15	15
2. predmet (3,20)	15	15	20	35
3. predmet (4,30)	15	15	20	35

Optimalno rešenje je 35, dobijeno kombinovanjem predmeta težine 1 i 3.

Rekonstrukcija izbora predmeta

Nakon što popunimo DP tabelu i izračunamo maksimalnu vrednost ranca, sledeći važan korak je da rekonstruišemo koji su tačno predmeti izabrani. Za to se krećemo unazad kroz DP matricu dp[i][w].

Počinjemo od poslednjeg predmeta: i = n i maksimalne težine w = W.
Ako je dp[i][w] != dp[i-1][w], predmet i je uzet.
Zatim smanjujemo težinu: w -= weight[i].
Nastavljamo sa predmetom i-1.

Ovo je tipičan C++ kod za rekonstrukciju:


vector<int> reconstructItems(const vector<int>& weights,
                             const vector<int>& values,
                             const vector<vector<int>>& dp,
                             int W)
{
    int n = weights.size();
    int w = W;
    vector<int> chosen;

    for (int i = n; i > 0; i--) {
        // Ako se vrednost razlikuje, predmet i-1 je uključen
        if (dp[i][w] != dp[i-1][w]) {
            chosen.push_back(i);      // čuvamo indeks predmeta (1-based)
            w -= weights[i-1];        // smanjujemo preostalu težinu
        }
    }

    reverse(chosen.begin(), chosen.end());
    return chosen;
}

Na ovaj način dobijamo tačan skup predmeta koji čine optimalno rešenje ranca. Ovo je veoma važan korak jer DP tabela daje samo maksimalnu vrednost, dok ovaj postupak omogućava da identifikujemo same predmete koji su u rancu.

Memorijska optimizacija — 1D DP tabelа

Standardno rešenje problema ranca koristi DP tabelu dimenzija N × W, što može zauzeti dosta memorije. Ako je maksimalni kapacitet ranca veliki (npr. W = 100 000), memorija postaje problem.

Dobra vest je da se 0/1 knapsack može optimizovati tako da koristi samo jedan niz dp[] dužine W+1. Ovo smanjuje memoriju sa O(N·W) na samo O(W).

Kako funkcioniše?

Ključna ideja je da kada obrađujemo predmet i, DP stanje zavisi samo od prethodnog reda (i-1). Umesto da čuvamo sve redove, koristimo jedan niz i popunjavamo ga unazad:


// dp[j] = maksimalna vrednost za kapacitet j
vector<int> dp(W+1, 0);

for (int i = 1; i <= N; i++) {
    // važno: ide se UNAZAD, kako se ne bi prepisali potrebni podaci
    for (int j = W; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

Zašto se mora ići unazad?

Ako bismo išli unapred (od 0 → W), onda bi nova vrednost dp[j] bila korišćena za sledeći izračun iste iteracije, čime bismo slučajno dobili unbounded knapsack (predmet se koristi više puta).

Dakle, za 0/1 knapsack: uvek iterirati j od W ka w[i].

Kada 1D optimizacija NIJE primenljiva?

kada treba uraditi rekonstrukciju podskupa → morate čuvati celu 2D tabelu (ili koristiti poseban niz predaka).
kada W nije previše velik i 2D DP već staje u memoriju.
kada se koristi neka varijanta ranca u kojoj prelazi zahtevaju pristup “drugom smeru” DP tabele.

Bonus poglavlje — Varijante problema ranca

Postoji više verzija problema ranca, svaka sa drugačijim DP pristupom. Ovo su najvažnije:

1) Unbounded Knapsack (predmet se može koristiti neograničeno puta)

Slično osnovnoj verziji, ali prelazi se računaju tako da predmet može biti odabran više puta. Kod se razlikuje u jednoj ključnoj stvari: dp se popunjava unapred (j od w[i] ka W).


// j ide unapred → predmet se može koristiti više puta
for (int j = w[i]; j <= W; j++) {
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}

2) Multiple (bounded) Knapsack — svaki predmet ima ograničen broj komada

Svaki predmet može biti uzet k puta (npr. imaš 5 istih flaša). Rešenje koristi:

binary splitting tehniku (pretvaranje komada u 1,2,4,... pakete)
ili 3D DP ako su brojevi mali

Ova varijanta je između 0/1 i unbounded verzije.

3) Multidimenzionalni Knapsack

Slično osnovnom problemu, ali umesto jedne “težine” postoje dve ili više restrikcija (npr. težina i zapremina).

DP više nije 2D, već npr. 3D:


// primer: DP[i][w][vol]
dp[i][w][vol] = maksimum vrednosti

Ova varijanta je mnogo zahtevnija i koristi se u realnim sistemima (npr. pakeri, logistika, optimizacija prostora).

Ovo poglavlje pruža širu sliku o problemu ranca i njegovim primenama. Za ozbiljnije takmičarsko programiranje, poznavanje svih varijanti je ključno.

Za takmičenja — na šta posebno obratiti pažnju

U takmičarskim zadacima o rancu (Knapsack) greške najčešće ne nastaju u DP formuli, već u pogrešnim pretpostavkama o granicama i tipovima podataka. Ovo je kratka lista stvari koje obavezno proveriti pre slanja rešenja.

1) Granice N i W

N — broj predmeta (može biti do 1000, 5000 ili više)
W — maksimalni kapacitet ranca

Pre nego što odlučiš metod, pogledaj red veličine:

Ako je W ≤ 2000 → klasičan 2D DP radi bez problema.
Ako je W ≤ 200 000 → možda radi uz 1D optimizaciju (ako nije potrebno rekonstruisati izbor).
Ako je W ≥ 10⁷ → DP je praktično neupotrebljiv (memorija = problem).

2) Tipovi promenljivih

Vrednosti često mogu biti velike → koristi long long.
Suma vrednosti može preći 32-bitni int ako je N veliko.
DP tabela može zahtevati ogroman memorijski prostor → proveri da li staje:


dp[N+1][W+1]   →   broj elemenata = (N+1)*(W+1)
  • svaki int = 4 bajta
  • 1e8 elemenata → 400 MB → previše!

3) Posebni (“granični”) ulazi

N = 0 ili W = 0
predmeti imaju težinu 0 (ponekad namerno dato!)
vrednost = 0 (uticaj na DP strukturu)
svi predmeti teži od W → rezultat = 0

U mnogim zadacima na takmičenjima upravo ovakvi ulazi prave probleme i prave WA (Wrong Answer) iako je glavni kod ispravan.

Kompleksnost i ograničenja algoritma

Pseudo-polinomska složenost

Vremenska kompleksnost klasičnog ranca je:


O(N · W)

Ovo se naziva pseudo-polynomial zato što zavisi ne od broja cifara u W, već od njegove numeričke vrednosti. Ako W naraste za faktor 10, vreme takođe raste ×10.

Kada DP ne radi dobro?

kada je W veoma veliki (npr. 10⁷ do 10⁹)
kada je zbir težina ogroman
kada je memorija ograničena (online takmičenja limit 256MB)

U ovim situacijama DP pristup postaje neizvodljiv jer:

dp niz ne može da stane u memoriju
vreme izvršavanja postaje presporo

Šta koristiti umesto DP?

Ako W ima ogromne vrednosti, takmičari prelaze na:

meet-in-the-middle (za N ≤ 40)
branch & bound tehnike
heuristike / greedy (ako je problem takvog tipa)
bitset DP (za Subset Sum varijante)
DP po zbiru vrednosti (kada su vrednosti male, a težine velike)

DP po vrednosti (važan trik!)

Ako su vrednosti male (do npr. 10³), a težine ogromne:


// dp[v] = minimalna težina potrebna da se postigne vrednost v

Ovaj pristup menja kompleksnost iz O(NW) u O(N · sum_vrednosti).

Ove napomene su izuzetno korisne za pripremu za takmičenja poput OI, IOI, CEOI i sličnih. Dobro poznavanje ograničenja omogućava da brzo prepoznaš koju verziju algoritma treba primeniti.

Zadaci za vežbu (sa uputstvom, bez rešenja)

Zadatak 1:

Data je grupa predmeta sa težinama i vrednostima. Svaki predmet može biti uzet najviše jednom. Odredi najveću ukupnu vrednost koju je moguće spakovati u ranac maksimalne težine W = 25.

Težine: {4, 7, 9, 12, 13}
Vrednosti: {10, 13, 18, 22, 23}

Uputstvo (kratko):
Napravi DP tabelu dimenzija (n+1) × (W+1) i popunjavaj je standardnim prelazom:


dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

Posebno obrati pažnju na slučaj kada je weight[i] > w — tada se vrednost samo prenosi iz prethodnog reda.

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

Da proceniš koje kombinacije predmeta mogu stati u ranac
Da barem okvirno predvidiš kolika bi mogla biti maksimalna vrednost

Čak i delimičan pokušaj znatno pomaže razumevanju.

⚠ Upozorenje:
Rešenje je namenjeno proveri i učenju. Ako nisi pokušao/la samostalno, preporuka je da se vratiš korak unazad i pokušaš da sam/a popuniš bar deo DP tabele.

Rešenje — DP tabela, rekonstrukcija i kompletno C++ rešenje

1) Popunjena tabela (dp[i][j]) za dati primer

Parametri: n = 5, W = 25
Težine (index 1..5): 4, 7, 9, 12, 13
Vrednosti (index 1..5): 10, 13, 18, 22, 23

Tabela je predstavljena red po red (i = 0..5). Svaki red sadrži vrednosti dp[i][0..25]. Red i znači: koristimo prvih i predmeta.

i \ j	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
0
1	0	0	0	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10
2	0	0	0	10	10	10	13	13	13	13	23	23	23	23	23	23	23	23	23	23	23	23	23	23	23
3	0	0	0	10	10	10	13	13	18	18	23	23	28	28	28	31	31	31	31	41	41	41	41	41	41
4	0	0	0	10	10	10	13	13	18	18	23	23	28	28	28	32	32	32	35	41	41	41	45	45	50
5	0	0	0	10	10	10	13	13	18	18	23	23	28	28	28	32	33	33	35	41	41	41	45	46	50

Kako čitati tabelu: ćelija dp[3][9] = 18 znači da sa prva 3 predmeta i kapacitetom 9 možemo dobiti maksimalnu vrednost 18. Konačno, dp[5][25] = 50 je odgovor zadatka.

2) Rekonstrukcija rešenja

predmet 1 (4, 10)
predmet 3 (9, 18)
predmet 4 (12, 22)

Ukupna težina = 25
Ukupna vrednost = 50

3) C++ rešenje sa komentarima


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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, W;
    cin >> N >> W;

    vector weight(N+1), value(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> weight[i] >> value[i];
    }

    vector> dp(N+1, vector(W+1, 0));

    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= W; ++j) {
            dp[i][j] = dp[i-1][j];
            if (weight[i] <= j) {
                dp[i][j] = max(
                    dp[i][j],
                    dp[i-1][j - weight[i]] + value[i]
                );
            }
        }
    }

    cout << dp[N][W] << '\n';

    int j = W;
    vector chosen;
    for (int i = N; i >= 1; --i) {
        if (dp[i][j] != dp[i-1][j]) {
            chosen.push_back(i);
            j -= weight[i];
        }
    }

    return 0;
}

2. Knapsack optimizovan na O(W) memorije

Tekst zadatka

Dat je klasični 0/1 Knapsack problem. Potrebno je da, za dati kapacitet ranca W i niz predmeta (svaki sa težinom w[i] i vrednošću v[i]), izračunate maksimalnu moguću vrednost koja može stati u ranac.

Vaš zadatak je da napišete optimizovano rešenje koje koristi samo O(W) memorije (jednodimenzioni DP niz).

Najvažnije pravilo: iterirati težine unazad.

Uputstvo

Za svaku iteraciju predmeta i, DP niz se popunjava unazad:


for (int weight = W; weight >= w[i]; weight--) {
    dp[weight] = max(dp[weight], dp[weight - w[i]] + v[i]);
}

Ovim se sprečava višestruko korišćenje istog predmeta i tačno se simulira 2D DP tabela.

□ Savet za učenje:
Pre nego što pogledaš rešenje, pokušaj da sam/a odgovoriš:

Zašto se petlja po težinama mora ići unazad?
Šta bi se desilo kada bi se išlo unapred?

Čak i kratak pokušaj značajno pomaže razumevanju.

⚠ Upozorenje:
Rešenje služi za proveru i razumevanje ideje. Ako nisi pokušao/la samostalno — preporuka je da se vratiš korak unazad i pokušaš bar osnovnu implementaciju.

Rešenje — detaljno objašnjeno


// Knapsack optimizovan na O(W) memorije
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> w = {1, 3, 4};
    vector<int> v = {15, 20, 30};

    int W = 7;
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < w.size(); i++) {
        for (int weight = W; weight >= w[i]; weight--) {
            dp[weight] = max(dp[weight], dp[weight - w[i]] + v[i]);
        }
    }

    cout << "Maksimalna vrednost: " << dp[W] << endl;
    return 0;
}

Vizuelizacija 1D DP niza

Posmatrajmo kako se menja DP niz za svaki predmet. Indeks predstavlja kapacitet ranca, a vrednost maksimalnu dobit.

Početno stanje:
dp = [0, 0, 0, 0, 0, 0, 0, 0]

Predmet 1: težina = 1, vrednost = 15
dp = [0, 15, 15, 15, 15, 15, 15, 15]

Predmet 2: težina = 3, vrednost = 20
dp = [0, 15, 15, 20, 35, 35, 35, 35]

Predmet 3: težina = 4, vrednost = 30
dp = [0, 15, 15, 20, 35, 45, 45, 50]

Pošto se iterira unazad, vrednosti poput dp[weight - w[i]] još uvek predstavljaju stanje bez trenutnog predmeta, čime se obezbeđuje da se svaki predmet koristi najviše jednom (0/1 Knapsack).

3. Rekonstrukcija izbora predmeta (0/1 Knapsack)

Tekst zadatka

Nakon što se popuni dinamička tabela za klasični 0/1 Knapsack problem i izračuna maksimalna moguća vrednost, često je potrebno znati i koji tačno predmeti čine to optimalno rešenje.

Dat je već popunjen DP niz dp[i][w], gde dp[i][w] predstavlja maksimalnu vrednost koju možemo dobiti koristeći prvih i predmeta i kapacitet ranca w.

Zadatak je da implementiraš algoritam za rekonstrukciju izbora predmeta — tj. da odrediš koji predmeti su uključeni u optimalno rešenje.

Rekonstrukcija se vrši unazad, počevši od stanja i = n i w = W, analizom promena u DP tabeli.

Potrebno je napisati C++ kod koji vraća indekse predmeta (1-based) koji čine optimalan sadržaj ranca.

Primeri ulaza i očekivanog izlaza

Primer 1


Ulaz:
weights = {1, 3, 4}
values  = {15, 20, 30}
W = 7

Popunjena DP tabela (dp):
i\w | 0  1  2  3  4  5  6  7
--------------------------------
0   | 0  0  0  0  0  0  0  0
1   | 0 15 15 15 15 15 15 15
2   | 0 15 15 20 35 35 35 35
3   | 0 15 15 20 35 45 45 50

Očekivan izlaz:
Izabrani predmeti: 1 3

Objašnjenje:
Predmet 1 (težina 1, vrednost 15) i predmet 3 (težina 4, vrednost 30) zajedno daju maksimalnu vrednost od 45 uz kapacitet 7.

Primer 2


Ulaz:
weights = {2, 5, 3, 4}
values  = {6, 10, 7, 12}
W = 7

Očekivan izlaz:
Izabrani predmeti: 1 4

Primer 3


Ulaz:
weights = {4, 2, 3}
values  = {8, 5, 6}
W = 5

Očekivan izlaz:
Izabrani predmeti: 2 3

Uputstvo — kako funkcioniše rekonstrukcija

Rekonstrukcija koristi činjenicu da se u DP tabeli svaka promena vrednosti u odnosu na prethodni red dešava samo ako je trenutni predmet uključen u rešenje.

Kreni od i = n i w = W.
Ako važi dp[i][w] == dp[i-1][w] → predmet nije uzet.
Ako važi dp[i][w] != dp[i-1][w] → predmet i je uzet.
Ako je predmet uzet, smanji kapacitet: w -= weights[i-1].
Nastavi dok i > 0 i w >= 0.

Ključni uslov u kodu:


if (dp[i][w] != dp[i-1][w]) {
    chosen.push_back(i);
    w -= weights[i-1];
}

Pošto se predmeti pronalaze unazad, na kraju je potrebno obrnuti redosled kako bi se dobili indeksi u rastućem poretku.

□ Savet za učenje:
Pre nego što pogledaš rešenje, razmisli:

Zašto poređenje sa dp[i-1][w] radi?
Šta bi značilo da su vrednosti jednake?
Zašto se kapacitet smanjuje samo kada je predmet uzet?

Razumevanje ovih pitanja je ključno za sve DP probleme sa rekonstrukcijom.

⚠ Upozorenje:
Rešenje je dato radi provere i razumevanja. Ako nisi pokušao/la samostalno — preporuka je da pokušaš da napišeš rekonstrukciju bez gledanja koda.

Rešenje — kompletan C++ kod sa komentarima


// Rekonstrukcija izbora predmeta iz DP tabele (0/1 Knapsack)

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

// Funkcija vraća 1-based indekse izabranih predmeta
vector<int> reconstructItems(const vector<int>& weights,
                             const vector<vector<int>>& dp,
                             int W)
{
    int n = weights.size();
    int w = W;
    vector<int> chosen;

    // Krećemo unazad kroz DP tabelu
    for (int i = n; i > 0; --i) {
        // Ako se vrednost razlikuje, predmet i je uzet
        if (dp[i][w] != dp[i-1][w]) {
            chosen.push_back(i);        // 1-based indeks
            w -= weights[i-1];          // smanjenje kapaciteta
        }
    }

    // Obrćemo redosled jer smo išli unazad
    reverse(chosen.begin(), chosen.end());
    return chosen;
}

int main() {
    vector<int> weights = {1, 3, 4};
    int W = 7;

    vector<vector<int>> dp = {
        {0,0,0,0,0,0,0,0},
        {0,15,15,15,15,15,15,15},
        {0,15,15,20,35,35,35,35},
        {0,15,15,20,35,45,45,50}
    };

    vector<int> result = reconstructItems(weights, dp, W);

    cout << "Izabrani predmeti: ";
    for (int idx : result) {
        cout << idx << " ";
    }
    cout << endl;

    return 0;
}

Zaključak

Rekonstrukcija je logičan nastavak DP rešenja. Kada jednom razumeš ovaj princip, isti obrazac možeš primeniti i na: LCS, Edit Distance, Subset Sum, i mnoge druge dinamičke probleme.

4. Unbounded Knapsack (neograničeni ranac)

Tekst zadatka

U ovoj varijanti problema ranca, poznatoj kao Unbounded Knapsack, svaki predmet se može koristiti neograničeno mnogo puta.

To znači da, za razliku od klasičnog 0/1 Knapsack problema, ovde ne postoji ograničenje da se predmet može uzeti samo jednom.

Ključna razlika u implementaciji je u načinu popunjavanja dinamičkog programskog niza:

kod 0/1 Knapsack — kapacitet se iterira unazad
kod Unbounded Knapsack — kapacitet se iterira unapred

Zadatak je da napišeš program koji rešava Unbounded Knapsack problem koristeći 1D DP niz.

Zahtevi zadatka

učitati broj predmeta N i kapacitet ranca W
učitati nizove težina w[i] i vrednosti v[i]
koristiti DP niz dužine W + 1
dozvoliti neograničeno korišćenje svakog predmeta
ispisati maksimalnu moguću vrednost za kapacitet W

Najvažnije pravilo implementacije:
kapacitet j se mora iterirati unapred.


// predmet se može koristiti više puta
for (int j = w[i]; j <= W; j++) {
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}

Uputstvo — kako radi Unbounded Knapsack

Suština Unbounded Knapsack problema je u tome da DP stanje dp[j] može koristiti isti predmet više puta.

DP niz ima sledeće značenje:


dp[j] = maksimalna vrednost koju možemo postići
        za ranac kapaciteta j

Razlika u odnosu na 0/1 Knapsack:

0/1 Knapsack
→ predmet se koristi najviše jednom
→ j ide unazad
Unbounded Knapsack
→ predmet se koristi neograničeno puta
→ j ide unapred

Kada se j iterira unapred, izraz dp[j - w[i]] već može sadržati isti predmet — čime se automatski omogućava višestruko korišćenje.

Inicijalizacija DP niza:


dp[0] = 0
dp[j] = 0 za sva j > 0

Krajnji odgovor se uvek nalazi u dp[W].

□ Savet za učenje:
Pre nego što pogledaš rešenje, pokušaj da sam/a odgovoriš:

Zašto kod ovog zadatka smemo da idemo unapred?
Šta bi se desilo kada bismo išli unazad?
Kako DP implicitno dozvoljava ponavljanje predmeta?

Ako razumeš ova pitanja — razumeš ceo Unbounded Knapsack.

⚠ Upozorenje:
Rešenje služi za proveru i razumevanje ideje. Preporuka je da pokušaš samostalno da napišeš barem osnovnu verziju pre gledanja koda.

Rešenje — kompletan C++ kod sa komentarima


// Unbounded Knapsack -- 1D DP rešenje

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

int main() {
    int N, W;
    cin >> N >> W;

    vector<int> w(N), v(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }

    // dp[j] = maksimalna vrednost za kapacitet j
    vector<int> dp(W + 1, 0);

    // Prolazimo kroz sve predmete
    for (int i = 0; i < N; i++) {

        // Kod Unbounded Knapsack j ide UNAPRED
        for (int j = w[i]; j <= W; j++) {

            // Opcija 1: ne uzimamo predmet
            // Opcija 2: uzimamo predmet (i možemo ga opet uzeti)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    // Maksimalna vrednost za kapacitet W
    cout << dp[W] << endl;
    return 0;
}

Primeri ulaza i izlaza


Ulaz:
3 7
2 4
3 5
4 7

Izlaz:
13


Ulaz:
2 10
6 30
3 14

Izlaz:
42


Ulaz:
1 10
2 5

Izlaz:
25

Zaključak

Unbounded Knapsack je prirodan nastavak 0/1 Knapsack problema. Razumevanje razlike u smeru iteracije kapaciteta otvara vrata mnogim drugim DP problemima (npr. coin change, rod cutting).

5. Multiple (Bounded) Knapsack — ograničeni ranac

Tekst zadatka

U ovom zadatku razmatra se varijanta problema ranca u kojoj svaki predmet postoji u ograničenom broju primeraka. Ovaj problem se naziva Multiple ili Bounded Knapsack.

Za svaki predmet poznato je:

w[i] — težina i-tog predmeta
v[i] — vrednost i-tog predmeta
c[i] — maksimalan dozvoljen broj primeraka

Ranac ima maksimalni kapacitet W. Potrebno je izabrati predmete (ne prelazeći dozvoljene količine) tako da ukupna vrednost bude maksimalna.

Ovaj problem se nalazi između 0/1 Knapsack i Unbounded Knapsack:

nije dozvoljeno uzeti predmet samo jednom (kao u 0/1)
ali nije dozvoljeno ni neograničeno ponavljanje

Zadatak je implementirati Multiple (Bounded) Knapsack koristeći jednu od sledećih tehnika:

binary splitting (preporučena i efikasna)
ili 3D DP (dp[i][w][k] — konceptualno jednostavnije, ali vremenski i memorijski neefikasno)

Uputstvo — ideja rešenja (Binary Splitting)

Pošto svaki predmet može da se koristi najviše c[i] puta, ne možemo direktno primeniti standardni 0/1 ili Unbounded Knapsack algoritam.

Efikasno rešenje je primena tehnike binary splitting (binarna dekompozicija količina).

Ideja je da se količina c[i] razloži na zbir stepena dvojke:


c = 13 → 1 + 2 + 4 + 6

Svaki od ovih delova se tretira kao poseban 0/1 predmet:

težina = k · w[i]
vrednost = k · v[i]

Na ovaj način bounded problem se transformiše u klasični 0/1 Knapsack problem sa približno O(log c[i]) novih predmeta po originalnom predmetu.

Zašto ovo funkcioniše?

svaka količina od 0 do c[i] može se predstaviti kombinacijom binarnih paketa
broj predmeta u DP-u se drastično smanjuje
možemo koristiti standardni 1D DP sa iteracijom težine unazad

Kratak ilustrativni primer

N = 3, W = 10
w = [3, 2, 5]
v = [5, 3, 10]
c = [3, 4, 1]

Nakon binary splitting-a dobijamo sledeće 0/1 predmete:

(3,5), (6,10), (2,3), (4,6), (2,3), (5,10)
(težina, vrednost)

Nad ovim skupom se zatim primenjuje standardni 0/1 Knapsack algoritam.

□ Savet za učenje:
Pre nego što pogledaš rešenje, pokušaj da odgovoriš:

Zašto 3D DP nije praktičan za velike ulaze?
Kako binary splitting čuva ograničenja količina?
Zašto se nakon razlaganja koristi iteracija težine unazad?

Ako razumeš ova pitanja — razumeš ceo Multiple Knapsack.

⚠ Upozorenje:
Rešenje služi za proveru i razumevanje ideje. Preporučuje se da samostalno pokušaš implementaciju binary splitting-a pre gledanja koda.

Rešenje — Binary Splitting + 0/1 Knapsack


// Multiple (Bounded) Knapsack using Binary Splitting

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N = 3;
    int W = 10;

    vector<int> w = {3, 2, 5};
    vector<int> v = {5, 3, 10};
    vector<int> c = {3, 4, 1};

    // Novi 0/1 predmeti nakon razlaganja
    vector<pair<int,int>> items;

    // Binary splitting
    for (int i = 0; i < N; i++) {
        int k = c[i];
        int p = 1;

        while (p <= k) {
            items.push_back({p * w[i], p * v[i]});
            k -= p;
            p *= 2;
        }

        if (k > 0) {
            items.push_back({k * w[i], k * v[i]});
        }
    }

    // Standardni 0/1 Knapsack DP
    vector<int> dp(W + 1, 0);

    for (auto &item : items) {
        for (int j = W; j >= item.first; j--) {
            dp[j] = max(dp[j], dp[j - item.first] + item.second);
        }
    }

    cout << "Maksimalna vrednost = " << dp[W] << endl;
    return 0;
}

Konačan rezultat za dati primer

Za kapacitet W = 10 maksimalna vrednost je:


dp[10] = 18

Jedna optimalna kombinacija predmeta:

1 × (3, 5)
1 × (2, 3)
1 × (5, 10)

Binary splitting + 1D DP daje isti rezultat kao 3D DP, ali uz znatno manju potrošnju memorije i bolju vremensku efikasnost.

Zaključak

Multiple Knapsack predstavlja most između 0/1 i Unbounded varijanti. Binary splitting je standardna tehnika koja se često pojavljuje u takmičarskom programiranju i algoritamskim kursevima.

6. Multidimenzionalni Knapsack (više ograničenja)

Tekst zadatka

U ovoj varijanti problema ranca, svaki predmet ima više ograničenja. Najčešće su to težina i zapremina, ali uopšteno problem može uključivati i više različitih resursa (npr. vreme, energiju, budžet).

Za svaki predmet dato je:

w[i] — težina i-tog predmeta
vol[i] — zapremina i-tog predmeta
v[i] — vrednost i-tog predmeta

Ranac ima dva nezavisna ograničenja:

maksimalnu dozvoljenu težinu W
maksimalnu dozvoljenu zapreminu V

Potrebno je izabrati podskup predmeta tako da:

ukupna težina ≤ W
ukupna zapremina ≤ V
ukupna vrednost bude maksimalna

Svaki predmet može biti uzet najviše jednom (0/1 varijanta).

Uputstvo — Multidimenzionalni Knapsack

Ovo je prirodno proširenje klasičnog 0/1 Knapsack problema. Umesto jednog ograničenja (težina), sada imamo dva nezavisna resursa.

Najdirektniji i najintuitivniji pristup je korišćenje trodimenzionalnog dinamičkog programiranja.

dp[i][w][vol] = maksimalna vrednost koju možemo postići
                koristeći prvih i predmeta,
                sa ukupnom težinom ≤ w
                i zapreminom ≤ vol

Prelazi u DP tabeli

Za svaki predmet i postoje dve mogućnosti:

Ne uzimamo predmet:
dp[i][w][vol] = dp[i-1][w][vol]

Uzimamo predmet (samo ako staje u oba ograničenja):

dp[i][w][vol] =
max(dp[i-1][w][vol],
    dp[i-1][w - w[i]][vol - vol[i]] + v[i])

Važno: predmet mora da zadovolji oba ograničenja istovremeno. Ako ne zadovoljava makar jedno — ne može biti izabran.

Primer

N = 3
W = 5
V = 6

w   = [1, 2, 3]
vol = [3, 2, 4]
v   = [10, 20, 30]

Intuicija primera

Predmet 1: (w=1, vol=3, v=10)
Predmet 2: (w=2, vol=2, v=20)
Predmet 3: (w=3, vol=4, v=30)

Kombinacija predmeta 1 i 3:

Težina: 1 + 3 = 4 ≤ 5
Zapremina: 3 + 4 = 7 ❌ (ne staje)

Ova kombinacija nije dozvoljena. Preostaju sledeće optimalne opcije:

Predmet 1 + predmet 2
Težina = 3, zapremina = 5, vrednost = 30
Samo predmet 3
Težina = 3, zapremina = 4, vrednost = 30

Maksimalna vrednost za dati primer je:

Maksimalna vrednost = 30

□ Savet za učenje:
Pre nego što pogledaš rešenje, razmisli:

Kako bi se problem ponašao sa tri ili više resursa?
Zašto ne možemo nezavisno optimizovati težinu i zapreminu?
Po čemu se ovaj problem razlikuje od običnog 0/1 Knapsack-a?

Ako razumeš ova pitanja, razumeš i suštinu multidimenzionalnog dinamičkog programiranja.

⚠ Upozorenje:
Rešenje je dato radi razumevanja algoritma. Preporučuje se da pokušaš samostalno da napišeš osnovni DP pre gledanja koda.

Rešenje — 3D dinamičko programiranje


// Multidimenzionalni Knapsack (Težina + Zapremina) — 0/1 varijanta

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N = 3;
    int W = 5;
    int V = 6;

    vector<int> w   = {1, 2, 3};
    vector<int> vol = {3, 2, 4};
    vector<int> v   = {10, 20, 30};

    // dp[i][ww][vv] = maksimalna vrednost
    vector<vector<vector<int>>> dp(
        N + 1,
        vector<vector<int>>(W + 1, vector<int>(V + 1, 0))
    );

    for (int i = 1; i <= N; i++) {
        for (int ww = 0; ww <= W; ww++) {
            for (int vv = 0; vv <= V; vv++) {

                // Ne uzimamo predmet
                dp[i][ww][vv] = dp[i-1][ww][vv];

                // Uzimamo predmet ako staje
                if (ww >= w[i-1] && vv >= vol[i-1]) {
                    dp[i][ww][vv] = max(
                        dp[i][ww][vv],
                        dp[i-1][ww - w[i-1]][vv - vol[i-1]] + v[i-1]
                    );
                }
            }
        }
    }

    cout << "Maksimalna vrednost = "
         << dp[N][W][V] << endl;

    return 0;
}

Napomena o složenosti

Vremenska složenost: O(N · W · V)
Memorijska složenost: O(N · W · V)

U praksi se često koristi 2D optimizacija (dp[w][vol]), uz iteraciju unazad po oba resursa, čime se memorija smanjuje na O(W · V).

Zaključak

Multidimenzionalni Knapsack pokazuje snagu dinamičkog programiranja u problemima sa više ograničenja. Razumevanje ovog obrasca olakšava rešavanje realnih problema u kojima je potrebno istovremeno optimizovati više ograničenih resursa.

4. Povezane stranice

Prethodno
|< DP: Fibonacci sa memoizacijom

Sledeće
DP: Najduži zajednički podniz (LCS) >|

Dinamičko programiranje: Problem ranca (Knapsack problem)

Šta je 0/1 Knapsack problem?

Opis zadatka

Primer sa konkretnim brojevima

Naivno rešenje i motivacija za dinamičko programiranje

Za takmičenja: važne napomene

Vremenska složenost, ograničenja i kada DP ne radi

Kada DP rešenje ne radi?

Definicija DP stanja

Početni slučajevi

Prelaz

Implementacija u C++ (sa objašnjenjima)

Primer — vizualizacija DP tabele

Zaključak

Dodatni materijali — još primera i vizuelno objašnjenje

1. Vizuelna DP tabela (primer)

Rekonstrukcija izbora predmeta

Memorijska optimizacija — 1D DP tabelа

Kako funkcioniše?

Zašto se mora ići unazad?

Kada 1D optimizacija NIJE primenljiva?

Bonus poglavlje — Varijante problema ranca

1) Unbounded Knapsack (predmet se može koristiti neograničeno puta)

2) Multiple (bounded) Knapsack — svaki predmet ima ograničen broj komada

3) Multidimenzionalni Knapsack

Za takmičenja — na šta posebno obratiti pažnju

1) Granice N i W

2) Tipovi promenljivih

3) Posebni (“granični”) ulazi

Kompleksnost i ograničenja algoritma

Pseudo-polinomska složenost

Kada DP ne radi dobro?

Šta koristiti umesto DP?

DP po vrednosti (važan trik!)

Skriveni mini kviz — 0/1 problem ranca(Knapsack problem engl.)

Mini kviz: Da li razumeš 0/1 Knapsack problem?

Zadaci za vežbu (sa uputstvom, bez rešenja)

Zadatak 1:

Uputstvo — kako razmišljati pri popunjavanju DP tabele

Kako se računa dp[i][j]?

Rešenje — DP tabela, rekonstrukcija i kompletno C++ rešenje

1) Popunjena tabela (dp[i][j]) za dati primer

2) Rekonstrukcija rešenja

3) C++ rešenje sa komentarima

2. Knapsack optimizovan na O(W) memorije

Tekst zadatka

Uputstvo

Rešenje — detaljno objašnjeno

Vizuelizacija 1D DP niza

3. Rekonstrukcija izbora predmeta (0/1 Knapsack)

Tekst zadatka

Primeri ulaza i očekivanog izlaza

Uputstvo — kako funkcioniše rekonstrukcija

Rešenje — kompletan C++ kod sa komentarima

Zaključak

4. Unbounded Knapsack (neograničeni ranac)

Tekst zadatka

Zahtevi zadatka

Uputstvo — kako radi Unbounded Knapsack

Rešenje — kompletan C++ kod sa komentarima

Primeri ulaza i izlaza

Zaključak

5. Multiple (Bounded) Knapsack — ograničeni ranac

Tekst zadatka

Uputstvo — ideja rešenja (Binary Splitting)

Zašto ovo funkcioniše?

Kratak ilustrativni primer

Rešenje — Binary Splitting + 0/1 Knapsack

Konačan rezultat za dati primer

Zaključak

6. Multidimenzionalni Knapsack (više ograničenja)

Tekst zadatka

Uputstvo — Multidimenzionalni Knapsack

Prelazi u DP tabeli

Primer

Intuicija primera

Rešenje — 3D dinamičko programiranje

Napomena o složenosti

Zaključak

4. Povezane stranice