Quy Hoạch Động 2D & Bài Toán Cái Túi

1. Bản chất không gian trạng thái 2D

Trong Chuyên đề 13, trạng thái $dp[i]$ chỉ phụ thuộc vào một tham số đơn lẻ (vị trí trên dãy số hoặc giá trị tổng tiền). Tuy nhiên, trong thực tế thi đấu, bài toán thường yêu cầu thỏa mãn đồng thời hai điều kiện độc lập:

1. Quy hoạch động trên Lưới tọa độ (Grid DP): Trạng thái được định vị bởi cặp tọa độ $(i, j)$ trên ma trận $N \times M$.
2. Quy hoạch động Bài toán Cái túi (Knapsack DP): Trạng thái cần theo dõi đồng thời Chỉ số món đồ đang xét $i$ và Sức chứa còn lại của cái túi $w$.

Bản chất Không gian Trạng thái 2D: Mỗi ô $dp[i][j]$ là một đỉnh trong Đồ thị trạng thái DAG 2 chiều. Thứ tự tính toán phải quét qua toàn bộ các hàng và cột theo chiều tăng dần (hoặc giảm dần có kiểm soát) để đảm bảo tính đúng đắn của mọi quan hệ phụ thuộc.

2. Quy hoạch động trên lưới tọa độ (grid DP)

2.1. Đếm số đường đi trên lưới & xử lý vật cản

• Bối cảnh: Bắt đầu từ ô $(1, 1)$, cần đi đến ô $(N, M)$. Tại mỗi ô $(i, j)$, chỉ được phép di chuyển Sang phải $(i, j+1)$ hoặc Xuống dưới $(i+1, j)$. Trên lưới có một số ô là vật cản không thể đi vào.
• State Definition: $dp[i][j]$ là số đường đi hợp lệ từ $(1, 1)$ đến $(i, j)$.
• Base Case: dp[1][1] = (grid[1][1] == 0 ? 1 : 0).

• State Transition: Nếu ô $(i, j)$ là vật cản $\implies dp[i][j] = 0$. Ngược lại: $$dp[i][j] = (dp[i-1][j] + dp[i][j-1]) \pmod{10^9+7}$$

• Evaluation Order: Duyệt lồng 2 vòng lặp: Hàng $i = 1 \to N$, Cột $j = 1 \to M$.

2.2. Tìm đường đi có tổng giá trị lớn nhất / nhỏ nhất

• Mỗi ô $(i, j)$ chứa một số nguyên $A[i][j]$. Cần tìm đường đi từ $(1, 1)$ đến $(N, M)$ có tổng giá trị lớn nhất: $$dp[i][j] = A[i][j] + \max(dp[i-1][j], dp[i][j-1])$$

3. Bài toán cái túi $0/1$ (0/1 Knapsack problem)

3.1. Bảng phương án 2D chuẩn mực ($DP[i][w]$)

• Bối cảnh: Cho $N$ món đồ, món thứ $i$ có khối lượng $wt_i$ và giá trị $val_i$. Cái túi có sức chứa tối đa $W$. Mỗi món đồ được chọn tối đa 1 lần ($0$ hoặc $1$).
• State Definition: $dp[i][w]$ là tổng giá trị lớn nhất có thể đạt được khi chỉ xét trong $i$ món đồ đầu tiên với tổng khối lượng không vượt quá $w$.
• Base Cases: dp[0][w] = 0 với mọi $0 \le w \le W$ (Không có đồ thì giá trị bằng 0).
• State Transition: Tại món đồ thứ $i$, ta có 2 quyết định:
• Nếu $w < wt_i \implies dp[i][w] = dp[i-1][w]$ (Không đủ sức chứa để chọn món $i$).
• Nếu $w \ge wt_i \implies dp[i][w] = \max(dp[i-1][w], val_i + dp[i-1][w - wt_i])$.
• Độ phức tạp: Thời gian $\mathcal{O}(N \cdot W)$, Bộ nhớ $\mathcal{O}(N \cdot W)$.

3.2. Tuyệt kỹ nén mảng 1D (space optimization & backward traversal)

Nhận xét rằng dòng $dp[i][\dots]$ chỉ phụ thuộc duy nhất vào dòng ngay trước nó là $dp[i-1][\dots]$. Ta có thể nén bảng 2D thành một mảng 1D $dp[w]$ kích thước $W + 1$.

• Tử huyệt bắt buộc: Vòng lặp sức chứa $w$ bắt buộc phải duyệt ngược từ $W$ giảm dần về $wt_i$:

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

• Tại sao phải duyệt ngược? Khi tính $dp[w]$, ô dp[w - wt[i]] vẫn giữ nguyên giá trị của tầng $i-1$ (chưa bị đồ thứ $i$ ghi đè), đảm bảo mỗi món đồ chỉ được dùng tối đa 1 lần duy nhất!

4. Bài toán cái túi không giới hạn (unbounded Knapsack)

Khi mỗi món đồ được phép chọn vô số lần không giới hạn:

• Hệ thức 2D: $dp[i][w] = \max(dp[i-1][w], val_i + dp[i][w - wt_i])$.
• Kỹ thuật mảng 1D: Vòng lặp $w$ duyệt XUÔI từ $wt_i$ tăng dần lên $W$:

for (int w = wt[i]; w <= W; ++w) {
    dp[w] = max(dp[w], val[i] + dp[w - wt[i]]);
}

• Duyệt xuôi cho phép trạng thái $dp[w]$ kế thừa ngay lập tức kết quả của chính món đồ $i$ vừa được thêm vào ở dp[w - wt[i]].

5. Kỹ thuật đổi trục DP khi sức chứa $W$ quá lớn ($DP[v] = \text{Min Weight}$)

• Bối cảnh: $N \le 100$, nhưng sức chứa $W \le 10^9$ (không thể tạo mảng kích thước $10^9$), trong khi tổng giá trị tối đa $V_{\text{sum}} = \sum val_i \le 10^5$.
• Đổi Trục Trạng Thái (State Redesign):
• Đặt $dp[v]$ là Khối lượng nhỏ nhất để đạt được đúng tổng giá trị $v$.
• Base case: dp[0] = 0, mọi dp[v] = INF ($v \ge 1$).

• Chuyển trạng thái: Duyệt ngược $v$ từ $V_{\text{sum}}$ về $val_i$: $$dp[v] = \min(dp[v], wt_i + dp[v - val_i])$$

• Đáp án: $\max \{v \mid dp[v] \le W\}$.

• Độ phức tạp: $\mathcal{O}(N \cdot V_{\text{sum}})$ — Chạy mượt mà dưới $0.05$ giây!

6. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy duyệt xuôi trong 0/1 Knapsack mảng 1D: * Viết for (int w = wt[i]; w <= W; ++w) cho bài $0/1$ Knapsack sẽ biến thuật toán thành Unbounded Knapsack $\implies$ Món đồ bị lấy nhiều lần, sai hoàn toàn kết quả!
2. Bẫy tràn chỉ số biên âm trên Lưới 2D: * Tại hàng 1 và cột 1, $dp[i-1][j]$ hoặc $dp[i][j-1]$ sẽ truy cập vào chỉ số 0. * Quy tắc an toàn: Khai báo mảng 1-based kích thước $(N+2) \times (M+2)$ và khởi tạo viền bằng 0 (cho bài đếm cách) hoặc $-\infty$ (cho bài tìm Max).
3. Bẫy mảng 2D quá lớn gây tràn bộ nhớ (Memory Limit Exceeded - MLE): * Khai báo long long dp[2000][2000] tốn $2000 \times 2000 \times 8 \text{ bytes} \approx 32\text{ MB}$ (an toàn). Nhưng long long dp[10000][10000] tốn $800\text{ MB} \implies$ Sập bộ nhớ $256\text{MB}$. Bắt buộc phải nén thành mảng 1D.

7. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: Bài toán cái túi $0/1$ nén mảng 1D

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

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

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;

    if (n <= 0 || W < 0) return 0;

    vector<long long> wt(n), val(n);

    for (int i = 0; i < n; ++i) {
        cin >> wt[i] >> val[i];

    }

    vector<long long> dp(W + 1, 0);

    for (int i = 0; i < n; ++i) {
        // Duyệt ngược w giảm dần từ W về wt[i]
        for (long long w = W; w >= wt[i]; --w) {
            dp[w] = max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }

    cout << dp[W] << "\n";
    return 0;
}

Mẫu 2: Đường đi có tổng lớn nhất trên lưới 2D

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

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    if (n <= 0 || m <= 0) return 0;

    vector<vector<long long>> a(n + 1, vector<long long>(m + 1));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];

        }
    }

    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i == 1 && j == 1) {
                dp[i][j] = a[1][1];
            } else if (i == 1) {
                dp[i][j] = dp[1][j - 1] + a[i][j];
            } else if (j == 1) {
                dp[i][j] = dp[i - 1][1] + a[i][j];
            } else {
                dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[n][m] << "\n";
    return 0;
}