Hiểu bài toán

Bài toán Balo 1 (Knapsack 0/1): Có N viên bi, mỗi viên có khối lượng wi và giá trị vi. Cần chọn một tập hợp con các viên bi sao cho tổng khối lượng không vượt quá W và tổng giá trị là lớn nhất. Đây là bài toán tối ưu hóa经典, có thể giải bằng quy hoạch động. Với N ≤ 100 và W ≤ 10^5, ta cần một giải pháp hiệu quả về mặt thời gian và bộ nhớ.

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

Cách Quy hoạch động 2 chiều (DP 2D)

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, s;
    cin >> n >> s;
    vector<int> w(n + 1), v(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];

    // dp[i][j]: tổng giá trị lớn nhất khi xét i viên bi đầu tiên và sức chứa j
    vector<vector<long long>> dp(n + 1, vector<long long>(s + 1, 0));

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= s; j++) {
            // Không chọn viên thứ i
            dp[i][j] = dp[i-1][j];
            // Chọn viên thứ i (nếu khối lượng cho phép)
            if(j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
            }
        }
    }

    cout << dp[n][s];
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất. Ta xây dựng bảng quy hoạch động dp[i][j] thể hiện giá trị lớn nhất khi xét i items đầu tiên với giới hạn trọng lượng j. Công thức chuyển trạng thái: dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]). Cách này dễ hiểu nhưng tốn bộ nhớ (khoảng 100 * 10^5 * 8 bytes ≈ 80MB), có thể gây tràn bộ nhớ hoặc chậm nếu không tối ưu kiểu dữ liệu.

Cách Quy hoạch động 1 chiều (Optimized DP)

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

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

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

    for(int i = 1; i <= n; i++) {
        int w;
        long long v;
        cin >> w >> v;

        // Duyệt NGƯỢC để đảm bảo balo 0/1 (không dùng lại item nhiều lần)
        for(int j = W; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }

    cout << dp[W];
    return 0;
}

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

Cải tiến từ phương pháp 2D. Nhận thấy rằng dp[i][j] chỉ phụ thuộc vào hàng i-1. Do đó, ta có thể dùng mảng 1 chiều dp[j]. Để tránh lặp lại item (vì đây là bài toán 0/1), ta phải duyệt trọng lượng j từ W xuống w (duyệt ngược). Nếu duyệt xuôi, ta sẽ vô tình sử dụng item nhiều lần (bài toán Knapsack số nguyên).

Cách Quy hoạch động theo giá trị (Value DP)

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

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

    // dp[i] là khối lượng nhỏ nhất để đạt được giá trị i
    const long long INF = 1e18;
    vector<long long> dp(sum_v + 1, INF);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (long long j = sum_v; j >= v[i]; j--) {
            if (dp[j - v[i]] != INF) {
                dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
            }
        }
    }

    long long ans = 0;
    for (long long i = 0; i <= sum_v; i++) {
        if (dp[i] <= W) ans = i;
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(N * Sum(v))
• Space Complexity: O(Sum(v))

Khi W quá lớn (ví dụ 10^9) mà N nhỏ và v_i nhỏ, phương pháp DP theo trọng lượng sẽ chậm. Thay vào đó, ta định nghĩa dp[i] là khối lượng tối thiểu cần để đạt được giá trị i. Dải giá trị tổng cộng là Sum(v). Nếu Sum(v) nhỏ, phương pháp này hiệu quả hơn. Tuy nhiên, với ràng buộc của bài này (W=10^5, v=10^9), phương pháp theo trọng lượng là tối ưu.

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

Bài học kinh nghiệm

• Bài toán này là quy hoạch động kinh điển 0/1 Knapsack.
• Việc duyệt ngược trong mảng 1 chiều là chìa khóa để đảm bảo mỗi item chỉ được dùng 1 lần.
• Chọn phương pháp DP theo trọng lượng (Weight DP) hoặc theo giá trị (Value DP) phụ thuộc vào giới hạn của W và tổng giá trị.

Lỗi thường gặp

• Quên duyệt ngược (duyệt xuôi) trong giải pháp 1 chiều, dẫn đến kết quả sai (giải được bài toán Knapsack số nguyên thay vì 0/1).
• Sử dụng kiểu dữ liệu int cho tổng giá trị, trong khi v_i có thể lên tới 10^9 và tổng có thể vượt quá 2^31 - 1, cần dùng long long.
• Tràn mảng do khai báo kích thước không đủ (ví dụ dp[100000] nhưng cần dp[100001] cho chỉ số W).