knapsack_editorial

0/1 Knapsack

De bai

Cho $N$ vat pham, vat thu $i$ co trong luong $w[i]$ va gia tri $v[i]$ . Ban co mot ba lo voi suc chua toi da $W$ . Hay chon mot tap con cac vat pham sao cho tong trong luong khong vuot qua $W$ va tong gia tri la lon nhat.

Rang buoc: moi vat pham chi duoc chon hoac khong chon (0/1), khong duoc chia nho.

Input mau: $N = 4$ , $W = 5$ , trong luong $w = [2, 3, 4, 5]$ , gia tri $v = [3, 4, 5, 6]$ .

Cong thuc truy hoi

Goi $dp[i][j]$ la gia tri lon nhat khi xet $i$ vat pham dau tien voi suc chua $j$ . Ta co cong thuc truy hoi:

dp[i][j] = \max\bigl(dp[i-1][j],\; dp[i-1][j - w[i]] + v[i]\bigr)

Truong hop co so: $dp[0][j] = 0$ voi moi $j$ (khong chon vat nao thi gia tri bang $0$ ).

Dieu kien: chi co the lay vat $i$ khi $j \geq w[i]$ . Neu $j < w[i]$ thi $dp[i][j] = dp[i-1][j]$ .

So do bang DP – trang thai ban dau

Hang $i = 0$ tuong ung voi viec khong chon vat nao. Moi o $dp[0][j] = 0$ . Cac hang tiep theo se duoc dien bang cach ap dung cong thuc truy hoi, xet tung vat pham mot tu trai sang phai.

Giai thich trang thai DP

Moi o $dp[i][j]$ dai dien cho bai toan con: gia tri lon nhat co the dat duoc khi chi xet $i$ vat pham dau va suc chua la $j$ . Tai moi o, ta co hai lua chon:

Bo qua vat $i$ : lay gia tri tu hang tren cung cot, $dp[i-1][j]$ .
Lay vat $i$ : lay gia tri $dp[i-1][j - w[i]] + v[i]$ , chi khi $j \geq w[i]$ .

Gia tri lon hon trong hai lua chon se duoc ghi vao $dp[i][j]$ .

Qua trinh dien bang DP

Step 1 / 13

Co so: $dp[0][j] = 0$ voi moi $j$ . Khong co vat pham nao duoc xet nen gia tri luon bang $0$ .

Step 2 / 13

Vat $1$ ( $w=2, v=3$ ). Voi $j=0$ va $j=1$ : suc chua khong du ( $j < 2$ ), chi co the bo qua. $dp[1][0] = 0$ , $dp[1][1] = 0$ .

Step 3 / 13

$j=2$ : bo qua cho $dp[0][2]=0$ . Lay vat $1$ : $dp[0][2-2]+3 = 0+3 = 3$ . $\max(0, 3) = 3$ . Lay!

Step 4 / 13

$j=3$ : bo qua cho $0$ , lay cho $dp[0][1]+3 = 3$ . $\max(0,3) = 3$ . Lay!

Step 5 / 13

$j=4$ : $\max(0, dp[0][2]+3) = 3$ . $j=5$ : $\max(0, dp[0][3]+3) = 3$ . Hang $i=1$ hoan thanh. Vat $1$ duoc lay khi $j \geq 2$ .

Step 6 / 13

Vat $2$ ( $w=3, v=4$ ). $j=0,1,2$ : suc chua khong du de lay vat $2$ . Bo qua, sao chep tu hang tren: $dp[2][0..2] = [0, 0, 3]$ .

Step 7 / 13

$j=3$ : bo qua cho $3$ . Lay vat $2$ : $dp[1][0]+4 = 0+4 = 4$ . $\max(3, 4) = 4$ . Lay!

Step 8 / 13

$j=4$ : bo qua cho $3$ . Lay vat $2$ : $dp[1][1]+4 = 0+4 = 4$ . $\max(3, 4) = 4$ . Lay!

Step 9 / 13

$j=5$ : bo qua cho $3$ . Lay vat $2$ : $dp[1][2]+4 = 3+4 = 7$ . $\max(3, 7) = 7$ . Lay! Ca hai vat $1$ va $2$ deu duoc chon.

Step 10 / 13

Vat $3$ ( $w=4, v=5$ ). $j=0..3$ : khong du suc chua hoac bo qua tot hon, sao chep tu hang tren. $j=4$ : bo qua cho $4$ , lay cho $dp[2][0]+5=5$ . $\max(4,5) = 5$ . Lay!

Step 11 / 13

$j=5$ : bo qua cho $7$ , lay cho $dp[2][1]+5 = 0+5 = 5$ . $\max(7, 5) = 7$ . Bo qua! Giu nguyen to hop vat $1+2$ tot hon.

Step 12 / 13

Vat $4$ ( $w=5, v=6$ ). $j=0..4$ : sao chep tu hang tren (khong du suc chua hoac bo qua tot hon). $j=5$ : bo qua cho $7$ , lay cho $dp[3][0]+6 = 6$ . $\max(7, 6) = 7$ . Bo qua!

Step 13 / 13

$dp[4][5] = 7$ . Dap an: gia tri lon nhat la $7$ . Truy vet: $dp[4][5] = dp[3][5] = dp[2][5]$ (lay vat $2$ tai day) $\to dp[1][2]$ (lay vat $1$ tai day) $\to dp[0][0]$ . Chon vat $1$ va $2$ , tong trong $2+3=5$ , tong gia tri $3+4=7$ .

Truy vet loi giai

Sau khi dien xong bang DP, dap an nam o $dp[N][W]$ . De biet nhung vat nao duoc chon, ta truy vet tu $dp[N][W]$ nguoc ve $dp[0][0]$ :

Bat dau tai $i = N$ , $j = W$ .
Neu $dp[i][j] \neq dp[i-1][j]$ , thi vat $i$ duoc chon. Giam $j$ di $w[i]$ , giam $i$ di $1$ .
Neu $dp[i][j] = dp[i-1][j]$ , thi vat $i$ khong duoc chon. Chi giam $i$ di $1$ .
Lap lai cho den khi $i = 0$ .

Trong vi du tren: $dp[4][5] = 7 = dp[3][5]$ (khong lay vat $4$ ), $dp[3][5] = 7 = dp[2][5]$ (khong lay vat $3$ ), $dp[2][5] = 7 \neq dp[1][5] = 3$ (lay vat $2$ , $j$ giam tu $5$ ve $2$ ), $dp[1][2] = 3 \neq dp[0][2] = 0$ (lay vat $1$ , $j$ giam tu $2$ ve $0$ ). Vay tap vat duoc chon la $\{1, 2\}$ voi tong gia tri $3 + 4 = 7$ .

Cai dat

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

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];

    // dp[i][j] = max value using items 1..i with capacity j
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i - 1][j]; // skip item i
            if (j >= w[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
        }
    }

    cout << dp[n][W] << "\n";

    // Backtrack to find chosen items
    vector<int> chosen;
    for (int i = n, j = W; i >= 1; i--) {
        if (dp[i][j] != dp[i - 1][j]) {
            chosen.push_back(i);
            j -= w[i];
        }
    }

    reverse(chosen.begin(), chosen.end());
    for (int x : chosen)
        cout << x << " ";
    cout << "\n";

    return 0;
}

Do phuc tap: $O(N \cdot W)$ thoi gian va bo nho. Co the toi uu bo nho xuong $O(W)$ bang cach chi giu mot hang DP va duyet $j$ giam dan.