Hiểu bài toán

Bài toán yêu cầu tìm cách chọn các thỏi vàng sao cho tổng trọng lượng không vượt quá tải trọng M của túi, nhưng tổng giá trị thu được là lớn nhất. Đây là bài toán cái túi kinh điển (Binary Knapsack). Với mỗi thỏi vàng, ta có thể chọn hoặc không chọn. Với N thỏi và M tải trọng, ta cần tìm tổng giá trị lớn nhất.

Các cách tiếp cận

Cách Quy hoạch động cơ bản (Mảng 1 chiều)

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

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

    // dp[j] là giá trị lớn nhất với trọng lượng tối đa j
    vector<int> dp(M + 1, 0);

    for (int i = 0; i < N; i++) {
        // Duyệt ngược để đảm bảo mỗi item chỉ được dùng 1 lần
        for (int j = M; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[M] << endl;
    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(M)

Đây là cách tiếp cận chuẩn cho bài toán cái túi 0-1. Sử dụng mảng 1 chiều dp với kích thước M + 1. dp[j] lưu giá trị lớn nhất có thể đạt được với tổng trọng lượng không quá j. Với mỗi thỏi vàng (w[i], v[i]), ta cập nhật mảng dp từ M trở về w[i]. Việc duyệt ngược đảm bảo ta không dùng cùng một thỏi vàng nhiều lần cho cùng một trạng thái. Ví dụ: để có dp[j], ta cân nhắc việc không lấy thỏi i (giữ nguyên dp[j]) hoặc lấy thỏi i (lấy dp[j - w[i]] cộng thêm v[i]).

Cách Quy hoạch động mảng 2 chiều (Dễ hiểu)

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

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

    // dp[i][j] là giá trị lớn nhất khi xét i thỏi đầu tiên, trọng lượng tối đa j
    vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            // Không lấy thỏi i
            dp[i][j] = dp[i - 1][j];
            // Nếu trọng lượng thỏi i <= j, thử lấy nó
            if (w[i - 1] <= j) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
            }
        }
    }

    cout << dp[N][M] << endl;
    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(N * M)

Cách này sử dụng bảng 2 chiều dp[N+1][M+1]. dp[i][j] thể hiện giá trị lớn nhất khi xét i items đầu tiên và trọng lượng giới hạn là j. Nó dễ hình dung hơn: tại vị trí (i, j), ta có 2 lựa chọn: không lấy item i (giá trị bằng dp[i-1][j]) hoặc lấy item i (nếu w[i] <= j, giá trị bằng dp[i-1][j - w[i]] + v[i]). Tuy nhiên, cách này tốn nhiều bộ nhớ hơn so với cách tối ưu 1 chiều.

Cách Tối ưu không gian (Mảng 1 chiều)

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

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

    vector<int> dp(M + 1, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = M; j >= w[i]; --j) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[M];
    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(M)

Đây thực chất là cách tiếp cận số 1 nhưng viết lại cho gọn (giống các solution mẫu). Đây là lời giải tối ưu về không gian cho bài toán cái túi 0-1. Mảng dp 1 chiều suffices. Vòng lặp j chạy từ M về w[i] là chìa khóa. Nó đảm bảo rằng khi ta tính dp[j], giá trị dp[j - w[i]] mà ta dùng là giá trị của trạng thái trước khi xét item i (tức là dp của item i-1). Nếu duyệt xuôi (j từ w[i] lên M), ta sẽ bị lặp lại item (vì dp[j] mới sẽ dùng lại dp[j-w[i]] vừa được cập nhật trong cùng vòng lặp item i).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có cấu trúc tối ưu con (optimal substructure) và tính lặp lại (overlapping subproblems) nên phù hợp với Quy hoạch động.
• Biến trạng thái thường là tổng trọng lượng hiện tại (capacity).
• Với bài toán 0-1 Knapsack (mỗi item chỉ chọn 1 lần), việc duyệt công suất (capacity) từ cao xuống thấp (reverse loop) khi dùng mảng 1 chiều là bắt buộc để tránh dùng chéo item.

Lỗi thường gặp

• Dùng mảng 1 chiều nhưng duyệt j từ w[i] đến M (tăng dần)会导致 một item có thể được chọn nhiều lần (trường hợp Unbounded Knapsack).
• Quên kiểm tra j >= w[i] dẫn đến truy cập mảng ngoài vùng nhớ.
• Sử dụng int thay vì long long cho mảng dp nếu giá trị hoặc N*M quá lớn, nhưng trong bài này M, w_i, v_i <= 10^4 nên int an toàn (max value ~10^8).