Hiểu bài toán

Bài toán yêu cầu tìm tổng giá trị lớn nhất có thể đạt được bằng cách chọn một subset các viên bi sao cho tổng khối lượng không vượt quá giới hạn W. Đây là bài toán Knapsack kinh điển. Tuy nhiên, có sự khác biệt quan trọng: N <= 100 nhưng W có thể lên tới $10^9$ (rất lớn), trong khi giá trị $v_i$ chỉ lên tới 1000. Điều này khiến cho cách tiếp cận Knapsack thông thường dựa trên khối lượng (DP theo trọng số) là bất khả thi vì mảng DP cần kích thước quá lớn. Thay vào đó, ta cần chuyển hướng sang giải pháp dựa trên giá trị (DP theo giá trị).

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

Cách Quy hoạch động dựa trên giá trị (DP on Value)

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

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

    int N;
    long long W;
    cin >> N >> W;

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

    // Phân tích ràng buộc:
    // N <= 100, v_i <= 1000
    // Tổng giá trị lớn nhất có thể là 100 * 1000 = 100,000.
    int MAXV = 100000;
    const long long INF = 1e18;

    // dp[j] là khối lượng nhỏ nhất cần có để đạt được giá trị chính xác j.
    vector<long long> dp(MAXV + 1, INF);
    dp[0] = 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 val = MAXV; val >= v[i]; val--) {
            if (dp[val - v[i]] != INF) {
                dp[val] = min(dp[val], dp[val - v[i]] + w[i]);
            }
        }
    }

    int ans = 0;
    // Tìm giá trị lớn nhất j sao cho khối lượng tương ứng <= W
    for(int val = MAXV; val >= 0; val--) {
        if(dp[val] <= W) {
            ans = val;
            break;
        }
    }

    cout << ans;
    return 0;
}

• Time Complexity: O(N * Sum(v_i)) ~ O(10^7)
• Space Complexity: O(Sum(v_i)) ~ O(10^5)

Vì $W$ quá lớn, ta không thể khai báo mảng dp[W]. Thay vào đó, ta khai báo mảng dp theo giá trị. Kích thước mảng dp sẽ là tổng giá trị tối đa có thể đạt được, tức là $100 \times 1000 = 100,000$.

dp[j] lưu trữ khối lượng tối thiểu cần thiết để đạt được tổng giá trị j.

• Khởi tạo: dp[0] = 0 (giá trị 0 cần khối lượng 0), các phần tử khác là INF.
• Công thức chuyển trạng thái: Khi xét item thứ $i$ có khối lượng $wi$, giá trị $vi$, ta cập nhật dp[j] = min(dp[j], dp[j - v_i] + w_i).
• Kết quả: Duyệt từ giá trị lớn nhất trở xuống, giá trị nào đầu tiên có dp[j] <= W chính là đáp án.

Cách Brute Force (Đối với N nhỏ)

// Chỉ mang tính tham khảo, không khả thi với N=100
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
long long W;
vector<long long> w, v;
long long max_val = 0;

void solve(int idx, long long current_w, long long current_v) {
    if (current_w > W) return;
    if (idx == N) {
        max_val = max(max_val, current_v);
        return;
    }
    // Chọn item idx
    solve(idx + 1, current_w + w[idx], current_v + v[idx]);
    // Không chọn item idx
    solve(idx + 1, current_w, current_v);
}

int main() {
    cin >> N >> W;
    w.resize(N); v.resize(N);
    for(int i=0; i<N; i++) cin >> w[i] >> v[i];
    solve(0, 0, 0);
    cout << max_val;
    return 0;
}

• Time Complexity: O(2^N)
• Space Complexity: O(N)

Đây là cách tiếp cận trực tiếp nhất: thử tất cả các khả năng chọn hoặc không chọn từng viên bi. Tuy nhiên, với $N=100$, độ phức tạp $2^{100}$ là lớn hơn rất nhiều so với giới hạn thời gian cho phép (thường là $10^8$ thao tác/giây). Do đó, cách này chỉ hiệu nghiệm khi $N$ rất nhỏ (ví dụ $N \le 20$).

Cách Cải tiến DP trên giá trị (Quản lý mảng động)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;

int main() {
    int n;
    ll w;
    cin >> n >> w;

    // Tính tổng giá trị tối đa để xác định kích thước mảng DP
    ll total_value = 0;
    vector<ll> a(n), b(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i]; // a[i] là weight, b[i] là value
        total_value += b[i];
    }

    // Khởi tạo mảng dp với kích thước theo tổng giá trị
    vector<ll> dp(total_value + 1, INF);
    dp[0] = 0;

    for(int i = 0; i < n; i++) {
        for(int j = total_value; j >= b[i]; j--) {
            if (dp[j - b[i]] != INF) {
                dp[j] = min(dp[j], dp[j - b[i]] + a[i]);
            }
        }
    }

    ll ans = 0;
    for(int i = total_value; i >= 0; i--) {
        if(dp[i] <= w) {
            ans = i;
            break;
        }
    }
    cout << ans;
    return 0;
}

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

Đây là phiên bản linh hoạt hơn của phương pháp DP theo giá trị. Thay vì dùng hằng số MAXV = 100000, ta tính chính xác total_value là tổng giá trị của tất cả các items đầu vào. Điều này giúp tiết kiệm bộ nhớ hơn một chút nếu tổng giá trị thực tế nhỏ hơn 100,000, và đảm bảo không truy cập ngoài mảng nếu tổng giá trị vượt quá 100,000 (dù đề bài đảm bảo $v_i \le 1000$ nên tổng không vượt quá 100,000). Logic xử lý hoàn toàn tương tự.

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

Bài học kinh nghiệm

• Khi trọng lượng (W) lớn nhưng giá trị (v) nhỏ, ta nên chuyển đổi bài toán Knapsack từ 'Maximize value with weight limit' sang 'Minimize weight with value target'.
• Tổng giá trị tối đa trong bài toán này khá nhỏ ($10^5$) so với trọng lượng tối đa ($10^9$), nên DP theo giá trị là phương án tối ưu nhất.

Lỗi thường gặp

• Sử dụng mảng dp có kích thước theo W (ví dụ long long dp[1000000000]) sẽ gây tràn bộ nhớ (Stack overflow hoặc Heap limit exceeded).
• Khi duyệt cập nhật DP, phải duyệt ngược (j) để tránh việc một item bị sử dụng nhiều lần trong cùng một tập hợp (0/1 Knapsack).
• Cần khởi tạo mảng DP bằng một giá trị INF đủ lớn (ví dụ $10^{18}$) để phân biệt các trạng thái chưa thể đạt được.