Probleme de optimizare — rucsacul 0/1

Optimizarea cu DP

Până acum ai construit tablouri dp[] care numărau sau însumau. La problemele de optimizare cauți altceva: o valoare maximă (sau minimă). Diferența esențială apare în tranziție — în loc să aduni orbește, alegi cel mai bun dintre mai multe scenarii cu max (la maximizare) sau min (la minimizare).

Exemplul central al capitolului este rucsacul 0/1 (knapsack): ai n obiecte, fiecare cu o greutate și o valoare, plus un rucsac de capacitate W. Vrei să alegi o submulțime de obiecte cu greutatea totală cel mult W și valoarea totală maximă. „0/1” înseamnă că fiecare obiect se ia o dată întreg sau deloc — nu îl poți tăia în bucăți.

Starea este dp[i][w] = valoarea maximă pe care o obții folosind primele i obiecte într-un rucsac de capacitate w. Pentru fiecare obiect ai două variante:

• nu iei obiectul i → rămâi cu dp[i-1][w];
• iei obiectul i (doar dacă încape, adică greutate[i] <= w) → câștigi valoare[i] plus ce era optim în spațiul rămas: dp[i-1][w - greutate[i]] + valoare[i].

Tranziția alege maximul dintre cele două:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - greutate[i]] + valoare[i])

Inițializarea: la maximizare pornești de la 0 (rucsac gol sau zero obiecte = valoare 0). Și o regulă de aur: nu poți lua obiectul dacă w - greutate[i] < 0 — atunci păstrezi doar prima variantă.

Exemplu pas cu pas

Fie capacitatea W = 5 și trei obiecte:

Completezi tabloul dp[i][w] linie cu linie. Linia 0 (zero obiecte) este toată 0 — cazul de bază. Apoi, pentru fiecare obiect, decizi pe fiecare capacitate w.

Pe linia obiectului 1 (greutate 2, valoare 3): pentru w mai mic decât 2 nu încape, deci 0; de la w = 2 în sus încape și aduce 3.

Pe linia obiectului 2 (greutate 3, valoare 4): la w = 5 compari nu îl iau (dp[1][5] = 3) cu îl iau (dp[1][5-3] + 4 = dp[1][2] + 4 = 3 + 4 = 7). Iei maximul: 7.

Pe linia obiectului 3 (greutate 4, valoare 5): la w = 5 compari nu îl iau (dp[2][5] = 7) cu îl iau (dp[2][5-4] + 5 = dp[2][1] + 5 = 0 + 5 = 5). Maximul rămâne 7.

Răspunsul final este dp[3][5] = 7: iei obiectele 1 și 2 (greutate 2 + 3 = 5, valoare 3 + 4 = 7). Iată ultima linie a tabloului:

Implementare C++

Construiești tabloul de la linia 0 în sus. La fiecare obiect pornești cu varianta „nu îl iau”, apoi verifici dacă încape și, dacă da, încerci varianta „îl iau”.

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

int main() {
    int n = 3;                       // numarul de obiecte
    int W = 5;                       // capacitatea rucsacului
    int greutate[4] = {0, 2, 3, 4};  // greutate[1..n], indexat de la 1
    int valoare[4]  = {0, 3, 4, 5};  // valoare[1..n]

    int dp[4][6];                    // dp[0..n][0..W], deci W+1 coloane

    // init: zero obiecte -> valoare 0 pe orice capacitate
    for (int w = 0; w <= W; w++) {
        dp[0][w] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            // varianta 1: nu iau obiectul i
            dp[i][w] = dp[i - 1][w];

            // varianta 2: il iau, doar daca incape (w - greutate >= 0)
            if (w - greutate[i] >= 0) {
                int cuObiect = dp[i - 1][w - greutate[i]] + valoare[i];
                dp[i][w] = max(dp[i][w], cuObiect);   // pastrez maximul
            }
        }
    }

    cout << dp[n][W] << "\n";        // valoarea maxima = 7
    return 0;
}

Observă verificarea w - greutate[i] >= 0 înainte de a indexa: fără ea ai citi dp[i-1][-1], în afara tabloului. Tabloul are W + 1 coloane fiindcă indexezi capacitățile de la 0 la W inclusiv.

Complexitate

Complexitatea nu depinde de valori, ci de numărul de obiecte și de capacitate. De aici și o capcană: dacă W este uriaș, O(n · W) poate fi prea mult, chiar dacă ai puține obiecte.

Vizualizare

Urmărește cum se umple tabloul dp[i][w] linie cu linie. La fiecare celulă vezi comparația dintre „nu iau” și „iau” și cum se alege maximul dintre ele.

Recapitulare

• La problemele de optimizare tranziția alege cel mai bun scenariu cu max (maximizare) sau min (minimizare), nu doar adună.
• Rucsacul 0/1: dp[i][w] = max(dp[i-1][w], dp[i-1][w-greutate[i]]+valoare[i]), unde a doua variantă există doar dacă obiectul încape (w - greutate[i] >= 0).
• Inițializezi cu 0 (rucsac gol), folosești un tablou cu W + 1 coloane și obții complexitatea O(n · W) — răspunsul citit în dp[n][W].