Hiểu bài toán

Bài toán yêu cầu tìm số cách chọn các đồ dùng học tập (với số lượng không giới hạn) để tổng trọng lượng đúng bằng N. Mỗi đồ dùng có trọng lượng C_i cho trước. Đây là bài toán quy hoạch động kinh điển về bài toán cái túi (Unbounded Knapsack) nhưng với mục tiêu đếm số cách thay vì tìm tổng trọng lượng lớn nhất.

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

Cách Quy hoạch động cơ bản (Unbounded Knapsack)

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> c(m);
    for (int i = 0; i < m; i++) cin >> c[i];

    vector<ll> dp(n + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < m; i++) {
        for (int j = c[i]; j <= n; j++) {
            dp[j] += dp[j - c[i]];
        }
    }

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

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

Đây là cách tiếp cận chuẩn cho bài toán đếm cách kết hợp số lượng không giới hạn. Mảng dp[j] lưu số cách để đạt được tổng trọng lượng j. Với mỗi loại đồ dùng có trọng lượng c[i], ta cập nhật dp[j] bằng cách thêm số cách từ dp[j - c[i]] (tức là thêm một đồ dùng c[i] vào các cách đã có tổng j-c[i]). Vòng lặp j chạy từ c[i] đến N để đảm bảo không bị tràn số âm và tính đúng thứ tự.

Cách Quy hoạch động tối ưu với vector

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> c(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> c[i];
    }

    vector<long long> dp(n + 1, 0);
    dp[0] = 1;

    for (int i = 1; i <= m; i++) {
        for (int x = c[i]; x <= n; x++) {
            dp[x] += dp[x - c[i]];
        }
    }

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

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

Cách tiếp cận này tương tự như cách đầu tiên nhưng sử dụng vector với chỉ số từ 1 để dễ quản lý hơn. Logic tính toán hoàn toàn giống nhau. Việc chỉ số hóa từ 1 giúp code dễ đọc hơn nhưng không thay đổi độ phức tạp.

Cách Xử lý input với biến trung gian

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, z;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    vector<ll> dp(m + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        cin >> z;
        for (int j = z; j <= m; ++j)
            dp[j] += dp[j - z];
    }
    cout << dp[m];
}

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

Cách tiếp cận này có thể gây nhầm lẫn về tên biến. Ở đây m là tổng trọng lượng cần đạt (N) và n là số loại đồ dùng (M). Code sử dụng biến trung gian z để đọc trọng lượng từng loại. Logic DP vẫn giữ nguyên: duyệt qua từng loại đồ dùng và cập nhật mảng dp. Việc tối ưu IO với iosbase::syncwith_stdio(false) và cin.tie(nullptr) giúp tăng tốc độ nhập xuất.

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

Bài học kinh nghiệm

• Quy hoạch động với công thức: dp[j] = dp[j] + dp[j - c[i]], trong đó dp[j] là số cách để đạt tổng j.
• Vòng lặp ngoài duyệt các loại đồ dùng, vòng lặp trong duyệt các tổng trọng lượng để tránh đếm trùng lặp thứ tự.
• dp[0] = 1 là trường hợp cơ sở, nghĩa là có 1 cách để tạo tổng 0 (không chọn gì).

Lỗi thường gặp

• Lỗi thứ tự vòng lặp: Nếu duyệt j từ 0 đến n-c[i] sẽ thành bài toán 0/1 Knapsack (chọn tối đa 1 lần), sai yêu cầu bài toán.
• Tràn số: Với N=250, số cách có thể rất lớn, cần dùng long long (ll) để tránh tràn số.
• Nhầm lẫn tên biến N và M trong input: Cần đọc kỹ đề bài để gán đúng giá trị cho biến.