Choose jour language!

---

|

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.

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 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> dp(N+1, vector(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	0	1	2	3	4	5	6	7
0 (nema predmeta)	0	0	0	0	0	0	0	0
1 (predmet 1: w=1, v=1)	0	1	1	1	1	1	1	1
2 (predmet 2: w=3, v=4)	0	1	1	4	5	5	5	5
3 (predmet 3: w=4, v=5)	0	1	1	4	5	6	6	9
4 (predmet 4: w=5, v=7)	0	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	0	1	2	3	4
0 predmeta	0	0	0	0	0
1. predmet (1,15)	0	15	15	15	15
2. predmet (3,20)	0	15	15	20	35
3. predmet (4,30)	0	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 reconstructItems(const vector& weights,
                             const vector& values,
                             const vector>& dp,
                             int W)
{
    int n = weights.size();
    int w = W;
    vector 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 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.

Skriveni mini kviz — 0/1 Knapsack problem

Klikni da proveriš svoje znanje o osnovama ranca i DP rešenja!

Otvori kviz

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

1. Koja je DP relacija za 0/1 Knapsack problem?

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

2. Ako je W = 0 ili N = 0, šta će dp[N][W] biti?

0
1
Nema definisano
Prikaži odgovor

3. Koja je glavna ideja rekonstrukcije izbora predmeta?

Krenuti od dp[N][W] i pratiti da li je predmet uzet na osnovu promena vrednosti
Samo sumirati sve vrednosti
Koristiti brute-force za pronalaženje predmeta
Prikaži odgovor

4. Kada je standardno DP rešenje pseudo-polynomialno?

Kada vreme zavisi od broja predmeta N
Kada vreme zavisi direktno od W, a ne broja bitova ulaza
Kada koristi top-down pristup
Prikaži odgovor

5. Koja je dobra praksa kada su vrednosti W i N veliki?

Koristiti 2D DP tabelu
Razmotriti alternativne metode (meet-in-the-middle, vrednosno baziran DP, aproksimacije)
Povećati stack memoriju i računati standardni DP
Prikaži odgovor

□ Resetuj kviz

Zadaci za vežbu (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 postepeno je popunjavaj koristeći standardni prelaz:

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

Posebno obrati pažnju na to kada težina predmeta prelazi trenutnu težinu ranca — tada se vrednost samo prenosi.

Prikaži / sakrij uputstvo Prikaži / sakrij rešenje

Uputstvo — detaljno objašnjenje kako popuniti DP tabelu

Šta predstavlja svaka ćelija dp[i][j]?
dp[i][j] predstavlja maksimalnu ukupnu vrednost koju možemo dobiti koristeći samo prve i predmeta (1..i) i imajući na raspolaganju kapacitet ranca j.

Redovi tabele (i) modeluju rastući skup razmatranih predmeta: red 0 znači — nema predmeta (samo prazni skup), red 1 znači — razmatramo samo prvi predmet, itd.

Kolone tabele (j) predstavljaju trenutni raspoloživi kapacitet ranca (od 0 do W). Na kraju nas zanima vrednost u ćeliji dp[n][W].

Kako se popunjava jedna ćelija dp[i][j]?

1. Ako weight[i] > j (predmet i ne staje) → dp[i][j] = dp[i-1][j] (prenesi vrednost iz prethodnog reda).
2. Inače imamo izbor:
• ne uzeti predmet i → dp[i-1][j]
• uzeti predmet i → dp[i-1][j - weight[i]] + value[i]
3. Uzmemo maksimum od ta dva izbora.

Napomena o granicama i redosledu

• Počevši od reda 1 i kolone 0 popunjavaš tabelu red po red.
• Ćelije u prvom redu (i=0) su sve 0 — bez predmeta ne možemo postići pozitivnu vrednost.
• Ovaj pristup garantuje da kada izračunavamo dp[i][j], vrednosti dp[i-1][... ] su već izračunate.

Kada popuniš tabelu, možeš i rekonstruisati koji su predmeti uzeti: počinješ od dp[n][W] i ideš unazad: ako dp[i][j] != dp[i-1][j] → znači da je predmet i uzet, pa onda smanjiš j -= weight[i] i nastaviš.

Rešenje — popunjena DP tabela, rekonstrukcija i C++ kod sa komentarima

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	0	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	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	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	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	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	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	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 (primer): ćelija dp[3][9] = 18 znači: koristeći prvih 3 predmeta i kapacitet 9, najbolja vrednost je 18 (to odgovara uzimanju trećeg predmeta težine 9 i vrednosti 18). Na kraju, dp[5][25] = 50 — to je odgovor zadatka (maksimalna vrednost).

2) Koji predmeti su uzeti? (rekonstrukcija)

Rekonstruisanjem (počevši od i = 5, j = 25) dobijamo da su uzeti predmeti:

• predmet 1 (težina 4, vrednost 10)
• predmet 3 (težina 9, vrednost 18)
• predmet 4 (težina 12, vrednost 22)

Ukupna težina = 4 + 9 + 12 = 25, ukupna vrednost = 10 + 18 + 22 = 50.

3) C++ rešenje sa komentarima (svaki važan red objašnjen)

Copy

// 0/1 Knapsack -- kompletno rešenje sa komentarima
#include <iostream>
#include <vector>
using namespace std;

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

    int N, W;
    // N = broj predmeta, W = maksimalni kapacitet ranca
    cin >> N >> W;

    // koristimo 1-indexirane vektore radi jednostavnijeg mapiranja na dp[i][...]
    vector weight(N+1), value(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> weight[i] >> value[i];
        // weight[i] = težina i-tog predmeta
        // value[i]  = vrednost i-tog predmeta
    }

    // dp tabela: (N+1) x (W+1) inicijalizovana sa 0
    // dp[i][j] = maksimalna vrednost koristeći prvih i predmeta i kapaciteta j
    vector> dp(N+1, vector(W+1, 0));

    // Popunjavamo tabelu red po red (i ide od 1 do N)
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= W; ++j) {
            // Opcija 1: NE uzimamo i-ti predmet -> vrednost je ista kao kod dp[i-1][j]
            dp[i][j] = dp[i-1][j];

            // Opcija 2: Uzimamo i-ti predmet (ako staje u trenutni kapacitet j)
            if (weight[i] <= j) {
                // Ako uzmemo predmet i, preostali kapacitet je j - weight[i]
                // a najbolja vrednost iz prethodnog reda za taj preostali kapacitet je dp[i-1][j - weight[i]]
                // dodamo vrednost ovog predmeta value[i] i uporedimo sa opcijom ne-uzimanja
                dp[i][j] = max(dp[i][j], dp[i-1][j - weight[i]] + value[i]);
            }
        }
    }

    // dp[N][W] sadrži odgovor: maksimalna vrednost koju možemo dobiti
    cout << dp[N][W] << '\n';

    // (opciono) Rekonstrukcija jednog optimalnog skupa predmeta:
    int j = W;
    vector chosen;
    for (int i = N; i >= 1; --i) {
        // Ako se dp[i][j] razlikuje od dp[i-1][j], to znači da smo uzeli predmet i
        if (dp[i][j] != dp[i-1][j]) {
            chosen.push_back(i);        // beležimo da je i-ti predmet uzet
            j -= weight[i];             // smanjujemo preostali kapacitet
        }
        // inače, predmet i nije uzet i nastavljamo dalje
    }

    // (opciono) ispis izabranih predmeta
    if (!chosen.empty()) {
        cout << "Izabrani predmeti (indexi): ";
        for (int idx = chosen.size()-1; idx >= 0; --idx) {
            cout << chosen[idx] << " ";
        }
        cout << '\n';
    }

    return 0;
}
    

4) Kratko objašnjenje rezultata

• Odgovor za dati primer je 50.
• Optimalan izbor (jedan od mogućih) je predmeti 1, 3 i 4 (težine 4,9,12).
• Ovaj pristup radi u vremenu O(N·W) i koristi memoriju O(N·W) (može se optimizovati na O(W) ako je potrebno).

5) Saveti za rešavanje na takmičenjima

• Uvek proveri rubne slučajeve: W = 0, N = 0, težine veće od W.
• Ako su težine veoma velike (npr. W ~ 10^6), razmisli o alternativama (meet-in-the-middle, aproksimacija) ili optimizaciji memorije.
• Za rekonstrukciju pazi da proveravaš uslov dp[i][j] != dp[i-1][j] jer to signalizira da je predmet i uzet.

3. 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 — tj. umesto dvodimenzionalne DP tabele koristi samo jedan niz dužine W.

Najvažnije pravilo: Iterirati težine unazad kako se ne bi prepisivali podaci koje DP još nije obradio.

Prikaži uputstvo

Uputstvo

Za svaku iteraciju predmeta i, potrebno je prolaziti kroz DP niz unazad:

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

Time se obezbeđuje da se u istoj iteraciji predmeta ne koriste već ažurirane vrednosti, čime se tačno simulira ponašanje 2D DP tabele u značajno manjoj memoriji.

Prikaži rešenje

×

□ Unesite lozinku za pristup rešenju:

Potvrdi

Pogrešna lozinka.

Rešenje — detaljno objašnjeno

// Knapsack optimizovan na O(W) memorije — detaljno objašnjeno
#include 
#include 
using namespace std;

int main() {
    // Primer podataka:
    // w = težine, v = vrednosti
    vector w = {1, 3, 4};
    vector v = {15, 20, 30};

    int n = w.size();
    int W = 7;

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

    // Iteriramo kroz svaki predmet
    for (int i = 0; i < n; i++) {
        // Iteriramo UNAZAD po težinama
        // Važno: time obezbeđujemo da se isti predmet ne koristi više puta
        for (int weight = W; weight >= w[i]; weight--) {

            // Pokušavamo da ubacimo predmet i
            // dp[weight - w[i]] + v[i] je vrednost ako ga ubacimo
            dp[weight] = max(dp[weight], dp[weight - w[i]] + v[i]);
        }
    }

    // Rešenje je dp[W]
    cout << "Maksimalna vrednost: " << dp[W] << endl;
    return 0;
}
    

Rekonstrukcija izbora predmeta

Tekst zadatka

Nakon što se popuni dinamička tabela za 0/1 Knapsack i dobije maksimalna vrednost koju ranac može da sadrži, potrebno je rekonstruisati tačno koje predmete smo odabrali.

Zadatak: Implementirati funkciju koja, na osnovu popunjene DP matrice dp[i][w], rekonstruiše sve predmete koji se nalaze u optimalnom rancu. Kretanje se obavlja unazad: od i = n i w = W.

Potrebno je napisati C++ kod koji pronalazi i vraća indekse svih predmeta uključenih u optimalno rešenje.

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 funkcije:
Izabrani predmeti: 1 3

Objašnjenje:
Predmet 1 (1kg, 15)
Predmet 3 (4kg, 30)
Ukupno = 45, što je optimalno.

Primer 2

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

Optimalna kombinacija koja daje maksimalnu vrednost = 19
→ Predmeti: 1 i 4

Očekivan izlaz:
Izabrani predmeti: 1 4

Primer 3

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

Optimalno rešenje je predmet 2 + predmet 3 (težina 2+3 = 5)
Vrednost = 11

Očekivan izlaz:
Izabrani predmeti: 2 3

---

Prikaži uputstvo

Uputstvo

Rekonstrukcija se svodi na poređenje vrednosti DP tabele:

• Počinjemo sa i = n i w = W.
• Ako je dp[i][w] != dp[i-1][w] → predmet *i* je uzet.
• Tada smanjujemo w: w -= weights[i-1].
• Nastavljamo ka gore dok ne dođemo do i = 0.

// Ako se dp[i][w] razlikuje od dp[i-1][w], predmet i je korišćen.
if (dp[i][w] != dp[i-1][w]) {
    uzeli_smo_predmet_i;
    w -= weights[i];
}
    

Na kraju je potrebno obrnuti listu, jer se predmeti otkrivaju unazad.

Prikaži rešenje

×

□ Unesite lozinku

Potvrdi

Pogrešna lozinka.

✅ Rešenje — detaljno objašnjeno

// Rekonstrukcija izbora predmeta iz DP tabele — detaljno komentarisano

#include 
#include 
#include 
using namespace std;

// Rekonstruiše predmete korišćene u optimalnom rešenju
vector reconstructItems(const vector& weights,
                             const vector& values,
                             const vector>& dp,
                             int W)
{
    int n = weights.size();
    int w = W;
    vector chosen;

    // Krećemo od poslednjeg predmeta i idemo unazad
    for (int i = n; i > 0; i--) {

        // Ako se dp[i][w] razlikuje od dp[i-1][w], predmet je KORIŠĆEN
        if (dp[i][w] != dp[i-1][w]) {

            // Beležimo ga (1-based indeks predmeta)
            chosen.push_back(i);

            // Smanjuje se preostala težina
            w -= weights[i-1];
        }
    }

    // Predmeti su prikupljeni unazad → obrnuti
    reverse(chosen.begin(), chosen.end());

    return chosen;
}

int main() {
    // Primer
    vector weights = {1, 3, 4};
    vector values  = {15, 20, 30};
    int W = 7;

    // Primer DP tabele (popunjena ranije)
    vector> 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 res = reconstructItems(weights, values, dp, W);

    cout << "Izabrani predmeti: ";
    for (int x : res) cout << x << " ";
    cout << endl;
}
    

4. Povezane stranice

• Uvod u DP — osnovna ideja
• DP: Fibonacci sa memoizacijom
• DP: Subset Sum
• Matematički algoritmi — Fibonacci

Zadatak 1 — Unbounded Knapsack

U ovoj varijanti problema ranca svaki predmet se može koristiti neograničeno mnogo puta. DP prelazi se razlikuju od 0/1 ranca time što se tabela popunjava unapred (od manjeg ka većem kapacitetu).

Zadatak

Napiši program koji rešava Unbounded Knapsack tako da:

• učitava N, W
• učitava niz težina w[i] i vrednosti v[i]
• koristi 1D DP niz dužine W+1
• dozvoljava da se predmeti koriste neograničeno puta
• ispiše maksimalnu vrednost koju je moguće postići

Najvažniji deo zadatka: implementirati prelaz sa j 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]);
}
  

Prikaži uputstvo

Uputstvo

Razlika između 0/1 knapsack i unbounded knapsack je u jednoj stvari:

• 0/1 Knapsack → predmeti se koriste najviše jednom → j ide unazad
• Unbounded Knapsack → predmeti se koriste neograničeno puta → j ide unapred

DP[i] predstavlja najveću vrednost za kapacitet i:

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

Pošto se j kreće unapred, dp[j - w[i]] već sadrži vrednost koja podrazumeva da je predmet možda korišćen više puta.

DP inicijalizacija:

dp[0] = 0
dp[j] = 0 za sve j
    

Prikaži rešenje (samo za nastavnike)

Rešenje (sa komentarima)

// Unbounded Knapsack — rešenje sa bogatim komentarima

#include 
#include 
using namespace std;

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

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

    // dp[j] = najveća vrednost za kapacitet j
    vector dp(W + 1, 0);

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

        // Za Unbounded Knapsack j mora ići UNAPRED
        // jer dp[j - w[i]] već može sadržati rešenje gde je isti predmet korišćen više puta.
        for (int j = w[i]; j <= W; j++) {

            // Opcija 1: ne uzimamo predmet i → dp[j] ostaje isti
            // Opcija 2: uzmemo ga bar jednom, pa gledamo dp[j - w[i]] + v[i]
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[W] << endl; // maksimalna vrednost
    return 0;
}
    

Primeri ulaza/izlaza

Ulaz:
3 7
2 4
3 5
4 7

Objašnjenje:
možemo uzeti predmet težine 3 više puta:
3 + 3 + 3 > 7 (ne može)
ali 3 + 2 + 2 = 7 → vrednost = 5 + 4 + 4 = 13

Izlaz:
13
    

Ulaz:
2 10
6 30
3 14

Najbolje je uzeti predmet težine 3 tri puta:
3 + 3 + 3 = 9 (ne možemo do 10)
vrednost = 14 * 3 = 42

Izlaz:
42
    

Ulaz:
1 10
2 5

Možemo uzeti 5 puta isti predmet: 5 * 5 = 25

Izlaz:
25
    

Zadatak 2 — Multiple (Bounded) Knapsack

□ Tekst zadatka

Data je varijanta problema ranca u kojoj svaki predmet postoji u ograničenom broju primeraka. Za svaki predmet poznato je:

• w[i] — težina predmeta
• v[i] — vrednost predmeta
• c[i] — broj komada tog predmeta

Ranac ima maksimalnu nosivost W. Potrebno je izabrati predmete (ne prelazeći raspoložive količine) tako da je ukupna vrednost maksimalna.

Zadatak korisnika je da implementira Multiple (bounded) Knapsack koristeći binary splitting tehniku ili 3D DP (po izboru).

---

Prikaži / sakrij uputstvo

□ Uputstvo

U ovoj verziji problema ranca, svaki predmet ima ograničenu količinu. Binary splitting funkcioniše tako što se broj komada c[i] rastavlja na pakete veličine 1, 2, 4, 8, ... sve dok ne prekorače c[i]. Svaki paket se zatim tretira kao poseban predmet u 0/1 knapsack pristupu.

Primer ulaza

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

Očekivani izlaz

Maksimalna vrednost = 23

---

Prikaži rešenje (potrebna lozinka)

Unesite lozinku

Potvrdi Otkaži

✅ Rešenje sa komentarima

// 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};

    // 1) Pretvaramo svaki predmet u pakete
    vector<pair<int,int>> items; 
    for (int i = 0; i < N; i++) {
        int k = c[i];
        int base = 1;

        while (base <= k) {
            items.push_back({base * w[i], base * v[i]});
            k -= base;
            base *= 2;
        }
        if (k > 0)  // ostatak
            items.push_back({k * w[i], k * v[i]});
    }

    // 2) Običan 0/1 knapsack nad novim paketima
    vector<int> dp(W + 1, 0);

    for (auto &it : items) {
        int ww = it.first;   // težina paketa
        int vv = it.second;  // vrednost paketa

        for (int j = W; j >= ww; j--) {
            dp[j] = max(dp[j], dp[j - ww] + vv);
        }
    }

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

Zadatak 3 — Multidimenzionalni Knapsack

□ Tekst zadatka

U ovoj varijanti problema ranca, svaki predmet ima više "ograničenja", npr. težinu i zapreminu. Za svaki predmet poznato je:

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

Ranac ima maksimalnu težinu W i maksimalnu zapreminu V. Potrebno je izabrati predmete tako da nijedno ograničenje ne bude prekoračeno, a ukupna vrednost bude maksimalna.

Korisnik treba da implementira **3D DP pristup**: dp[i][w][vol] ili optimizovanu verziju po memoriji.

---

Prikaži / sakrij uputstvo

□ Uputstvo

Ovo je proširenje standardnog ranca na dva ili više resursa. DP stanje definišemo kao:

dp[i][w][vol] = maksimalna vrednost koristeći prvih i predmeta
                 i ograničenja težine <= w i zapremine <= vol

Prelazi

• Ako ne uzmemo predmet i: dp[i][w][vol] = dp[i-1][w][vol]
• Ako uzmemo predmet i (ako w[i] ≤ w i vol[i] ≤ vol): dp[i][w][vol] = max(dp[i-1][w][vol], dp[i-1][w-w[i]][vol-vol[i]] + v[i])

Primer ulaza

N = 3
W = 5
V = 6
w = [1, 2, 3]
vol = [3, 2, 4]
v = [10, 20, 30]

Očekivani izlaz

Maksimalna vrednost = 40

---

Prikaži rešenje (potrebna lozinka)

Unesite lozinku

Potvrdi Otkaži

✅ Rešenje sa komentarima

// 3D Knapsack problem (Weight + Volume constraints)
#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};

    // 3D DP tabela
    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 j = 0; j <= W; j++) {
            for (int k = 0; k <= V; k++) {
                // Ne uzimamo predmet i
                dp[i][j][k] = dp[i-1][j][k];

                // Ako možemo uzeti predmet i
                if (j >= w[i-1] && k >= vol[i-1]) {
                    dp[i][j][k] = max(dp[i][j][k],
                        dp[i-1][j - w[i-1]][k - vol[i-1]] + v[i-1]);
                }
            }
        }
    }

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

---

Prethodno
​|< DP: Fibonacci sa memoizacijom

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

---