Hiểu bài toán

Bài toán này là bài toán cái túi kinh điển (Knapsack Problem). Cho n món đồ, mỗi món có trọng lượng w[i] và giá trị v[i]. Người dùng có một chiếc túi có sức chứa tối đa m. Nhiệm vụ là chọn một số các món đồ sao cho tổng trọng lượng không vượt quá m và tổng giá trị là lớn nhất.

Đầu vào:

• Dòng đầu: hai số nguyên n, m.
• n dòng tiếp theo: mỗi dòng chứa hai số nguyên w[i] và v[i] là trọng lượng và giá trị của món đồ thứ i.

Đầu ra:

• Dòng đầu: tổng giá trị lớn nhất có thể đạt được.
• (Theo các giải pháp đã cho, bài toán yêu cầu in ra danh sách các物品 đã chọn và tổng trọng lượng tương ứng).

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

Cách Quy hoạch động (Lập bảng)

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

int main() {
    ifstream fin("BAG.INP");
    ofstream fout("BAG.OUT");

    int n, m;
    fin >> n >> m;

    vector<int> w(n + 1), v(n + 1);
    for (int i = 1; i <= n; ++i) {
        fin >> w[i] >> v[i];
    }

    // dp[i][j] = giá trị lớn nhất dùng i món đầu tiên, sức chứa j
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    // Xây dựng bảng quy hoạch động
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (w[i] <= j) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    // In ra giá trị lớn nhất
    fout << dp[n][m] << "\n";

    // Truy vết các vật đã chọn
    vector<int> selected;
    int totalWeight = 0;
    int i = n, j = m;
    while (i > 0) {
        if (dp[i][j] != dp[i-1][j]) {
            selected.push_back(i);
            totalWeight += w[i];
            j -= w[i];
        }
        i--;
    }

    // In tổng trọng lượng
    fout << totalWeight << "\n";
    // In danh sách các món đồ (theo thứ tự giảm dần của chỉ số)
    for (int k = selected.size() - 1; k >= 0; --k) {
        fout << selected[k] << (k == 0 ? "" : " ");
    }
    fout << endl;

    return 0;
}

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)

Đây là cách tiếp cận chuẩn của bài toán cái túi (Knapsack Problem) sử dụng quy hoạch động.

1. Mô hình hóa: Ta cần một bảng 2 chiều dp[i][j] trong đó:

   • i là số lượng món đồ được xem xét (từ 1 đến i).
   • j là sức chứa hiện tại của túi.
   • dp[i][j] lưu giá trị lớn nhất có thể đạt được.

2. Công thức truy hồi:

   • Nếu không chọn món đồ thứ i: Giá trị tương đương với việc xét i-1 món đồ với sức chứa j. dp[i][j] = dp[i-1][j].
   • Nếu chọn món đồ thứ i (chỉ được phép nếu w[i] <= j): Giá trị sẽ là v[i] cộng với giá trị lớn nhất khi xét i-1 món đồ với sức chứa còn lại là j - w[i]. dp[i][j] = dp[i-1][j - w[i]] + v[i].
   • Ta lấy giá trị lớn hơn trong 2 trường hợp trên.

3. Truy vết kết quả: Sau khi điền đầy bảng, dp[n][m] cho biết giá trị lớn nhất. Để biết những món đồ nào đã được chọn, ta đi ngược lại từ dp[n][m]:

   • Nếu dp[i][j] == dp[i-1][j], món đồ i không được chọn.
   • Ngược lại, món đồ i được chọn. Ta trừ trọng lượng w[i] vào j và tiếp tục truy vết ở i-1.

4. Độ phức tạp:

   • Thời gian: O(n * m) để điền bảng và O(n) để truy vết.
   • Không gian: O(n * m) để lưu bảng DP.

Cách Quy hoạch động tối ưu không gian (1 mảng)

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

int main() {
    freopen("BAG.INP", "r", stdin);
    freopen("BAG.OUT", "w", stdout);

    int n, m;
    cin >> n >> m;

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

    // Chỉ cần 1 mảng 1 chiều dp[j]
    vector<int> dp(m + 1, 0);

    // Để truy vết, ta cần lưu lại các bước
    // Tuy nhiên, trong code mẫu này chỉ tập trung vào tính giá trị max
    // Để truy vết với 1 mảng, ta cần lưu thêm mảng 'trace'

    vector<vector<int>> trace(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        // Vòng lặp j chạy ngược để đảm bảo không dùng lại item nhiều lần
        for (int j = m; j >= w[i]; --j) {
            if (dp[j] < dp[j - w[i]] + v[i]) {
                dp[j] = dp[j - w[i]] + v[i];
                trace[i][j] = 1; // Đánh dấu item i được chọn khi sức chứa là j
            }
        }
    }

    cout << dp[m] << endl;

    // Truy vết
    vector<int> selected;
    int current_m = m;
    for (int i = n; i >= 1; --i) {
        if (trace[i][current_m] == 1) {
            selected.push_back(i);
            current_m -= w[i];
        }
    }

    // In kết quả truy vết (Logic tương tự Solution 1)
    cout << m - current_m << "\n"; // In tổng trọng lượng (hoặc tính lại)
    for (int i = selected.size() - 1; i >= 0; --i) cout << selected[i] << " ";

    return 0;
}

• Time Complexity: O(n * m)
• Space Complexity: O(m) (hoặc O(n*m) nếu lưu truy vết)

Tiếp cận này tối ưu hóa không gian bộ nhớ so với giải pháp 2 mảng.

1. Nguyên lý: Khi tính dp[j] cho món đồ thứ i, ta chỉ cần thông tin từ mảng dp của món đồ thứ i-1. Quan trọng hơn, khi duyệt j từ m xuống w[i], ta đảm bảo rằng dp[j - w[i]] vẫn là giá trị của món đồ i-1 (chưa bị cập nhật bởi món đồ i).

2. Cách triển khai:

   • Duyệt các món đồ i từ 1 đến n.
   • Duyệt sức chứa j từ m xuống w[i].
   • Cập nhật: dp[j] = max(dp[j], dp[j - w[i]] + v[i]).

3. Vấn đề truy vết:

   • Với cách tối ưu không gian này, ta không thể quay lại dp[i-1] để so sánh trực tiếp.
   • Do đó, ta cần thêm một mảng trace[i][j] hoặc trace[j] để ghi nhận lại quyết định chọn hay không chọn món đồ i tại sức chứa j. Tuy nhiên, giải pháp này thường chỉ dùng khi không cần truy vết hoặc truy vết bằng cách lưu lại lịch sử (tốn thêm O(n*m) không gian).
   • Lưu ý: Code mẫu ở trên kết hợp cả lưu trace để minh họa cho việc giải quyết vấn đề này.

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

Bài học kinh nghiệm

• Bài toán chia thành các giai đoạn (từng món đồ), mỗi giai đoạn có các trạng thái (sức chứa hiện tại), là đặc điểm của quy hoạch động.
• Công thức quy hoạch động: F(i, j) = max(F(i-1, j), F(i-1, j - w[i]) + v[i]).
• Việc truy vết lộ trình chọn đồ cần lưu lại dấu vết trong quá trình tính toán hoặc suy luận lại dựa trên bảng DP.

Lỗi thường gặp

• Lỗi chỉ số mảng: 0-based vs 1-based index.
• Quên kiểm tra điều kiện w[i] <= j trước khi truy cập dp[i-1][j-w[i]].
• Trong thuật toán tối ưu không gian, duyệt chiều tăng của j dẫn đến sai kết quả (tính nhầm bài toán túi cơ số).