Hiểu bài toán

Bài toán yêu cầu tìm tổng thể tích lớn nhất của các đồ chơi có thể xếp vào hộp sao cho tổng thể tích không vượt quá thể tích V của hộp. Đây là bài toán quy hoạch động dạng túi đồ (Knapsack) kinh điển, trong đó mỗi đồ chơi có thể tích v_i tương ứng với trọng số và giá trị như nhau, và ta cần chọn một tập con các đồ chơi sao cho tổng thể tích ≤ V nhưng tối ưu (lớn nhất).

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

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

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

int main() {
    int n, V;
    cin >> n >> V;
    int v[n];
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    int dp[V+1];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < n; i++){
        for(int j = V; j >= v[i]; j--){
            dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
        }
    }
    cout << dp[V];
}

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

Sử dụng quy hoạch động dạng mảng 1D dp[j] lưu tổng thể tích lớn nhất có thể đạt được với thể tích tối đa j. Vòng lặp j chạy ngược từ V về v[i] để đảm bảo mỗi đồ chơi chỉ được dùng tối đa một lần (tránh lấy trùng). Kết quả là dp[V].

Cách Quy hoạch động Knapsack với mảng 2D

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

int main() {
    int n, V;
    cin >> n >> V;
    int v[n];
    for(int i = 0; i < n; i++) cin >> v[i];

    vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= V; j++){
            if (j >= v[i-1])
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - v[i-1]] + v[i-1]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n][V];
}

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

Dùng mảng 2D dp[i][j] thể hiện tổng thể tích lớn nhất khi xét i đồ chơi đầu tiên và thể tích tối đa j. Cách này dễ hiểu hơn nhưng tốn bộ nhớ hơn. Cuối cùng, dp[n][V] là kết quả.

Cách Quay lui (Backtracking) - Naive

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

long long n, i, x[10001], a[1000001], j, can, m, q, k, y, s, d, b[1000001], maxx;
void Try(int i)
{
    if(i>n) return;
    for(int j=0;j<=1;j++)
        if(s+j*a[i]<=m)
    {
        x[i]=j;
        s=s+x[i]*a[i];
        if(s==m)
        {
            cout<<m;
            exit(0);
        }
        maxx=max(s,maxx);
        Try(i+1);
        s=s-x[i]*a[i];
    }
}
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(i=1;i<=n;i++)
        cin>>a[i];
    Try(1);
    cout<<maxx;
}

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

Thử tất cả các tập hợp đồ chơi có thể (mỗi đồ chơi có thể được chọn hoặc không). Hàm Try(i) gọi đệ quy để thử cả hai trường hợp (chọn hoặc không chọn đồ chơi thứ i). Biến maxx lưu giá trị lớn nhất tìm được. Với n ≤ 30, cách này có thể chạy chậm nhưng vẫn giải quyết được bài toán.

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

Bài học kinh nghiệm

• Bài toán là dạng Knapsack kinh điển, có thể giải bằng DP với độ phức tạp O(n*V).
• Mảng 1D với vòng lặp ngược là cách tối ưu bộ nhớ và tốc độ trong nhiều trường hợp.
• Với n nhỏ (≤ 30), quay lui cũng có thể chấp nhận được, nhưng DP thường nhanh và ổn định hơn.

Lỗi thường gặp

• Lỗi truy cập ngoài mảng khi j < v[i] trong vòng lặp DP.
• Quên khởi tạo mảng dp hoặc gán sai giá trị ban đầu (phải là 0).
• Sử dụng int có thể gây tràn số với V lớn (≤ 10^5) và tổng giá trị lớn (≤ 30*10^4), nhưng trong bài này int là đủ.
• Trong quay lui, nếu không kiểm tra điều kiện đúng có thể gây tràn stack hoặc chạy lâu.