Hiểu bài toán

Bài toán là một bài toán quy hoạch động dạng túi đồ (Knapsack) kinh điển. Input gồm n thửa ruộng, mỗi thửa có thời gian ti để cày và điểm số di nhận được. Tổng thời gian có thể dùng để cày là S. Mục tiêu là chọn một tập hợp các thửa ruộng sao cho tổng thời gian cày không vượt quá S và tổng điểm số là lớn nhất.

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

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

#include <bits/stdc++.h>

using namespace std;

int n, S;
vector<int> t, d;

void input() {
    cin >> n >> S;
    t.resize(n); d.resize(n);
    for (int i = 0; i < n; ++i) cin >> t[i];
    for (int i = 0; i < n; ++i) cin >> d[i];
}

void output() {
    vector<int> dp(S + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = S; j >= t[i]; --j) {
            dp[j] = max(dp[j], dp[j - t[i]] + d[i]);
        }
    }
    cout << dp[S];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    input();
    output();
    return 0;
}

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

Đây là phương pháp chuẩn để giải bài toán túi đồ 0/1. Ta sử dụng mảng 1 chiều dp trong đó dp[j] là điểm số lớn nhất có thể đạt được với thời gian chính xác là j. Để đảm bảo mỗi item chỉ được chọn 1 lần, ta duyệt trọng lượng j từ S giảm về t[i]. Công thức cập nhật: dp[j] = max(dp[j], dp[j - t[i]] + d[i]). Sau khi duyệt qua tất cả các item, dp[S] chứa kết quả tối ưu.

Cách Backtracking (Quay lui) có nhánh cận (Branch and Bound)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n,S;
int time[26];
int point[26];
int max_point = 0;
int max_current = 0;
int time_limit = 0;
int prefix_sum[26] = {0};
void Try(int start_index){
    for (int i = start_index; i <= n; i++)
    {
        max_current = max_current + point[i];
        time_limit = time_limit + time[i];
        if (time_limit <= S)
        {
            if (max_current > max_point)
            {
                max_point = max_current;
            }
            if(max_current + prefix_sum[n] - prefix_sum[i] >= max_point){
                Try(i+1);
            }
        }
        max_current = max_current - point[i];
        time_limit = time_limit - time[i];
    }
    return;
}
int main(){
    scanf("%d%d",&n,&S);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d",&time[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d",&point[i]);
        prefix_sum[i] = prefix_sum[i-1] + point[i];
    }
    Try(1);
    printf("%d",max_point);
    return 0;
}

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

Phương pháp này thử tất cả các cách kết hợp các thửa ruộng (tập con của n items). Hàm Try duyệt qua các item và thử chọn hoặc không chọn. Cải tiến 'Branch and Bound' ở đây sử dụng mảng prefix_sum để đánh giá cận trên: nếu số điểm tối đa có thể đạt được từ các item còn lại cộng với điểm hiện tại không vượt quá max_point hiện tại thì ta bỏ qua nhánh đó (không cần đệ quy tiếp). Tuy nhiên, với n <= 25, số trường hợp vẫn rất lớn (2^25) nên phương pháp này có thể chậm hơn DP.

Cách Knapsack 1D Optimization (Space Optimized)

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

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

    int n, T;
    cin >> n >> T;

    vector<int> t(n), d(n);
    for (int i = 0; i < n; i++) cin >> t[i];
    for (int i = 0; i < n; i++) cin >> d[i];

    vector<int> dp(T + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int time = T; time >= t[i]; time--) {
            dp[time] = max(dp[time], dp[time - t[i]] + d[i]);
        }
    }

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

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

Đây là phiên bản tối ưu không gian của quy hoạch động 2 chiều. Thay vì ma trận dp[n+1][S+1], ta chỉ cần một mảng 1 chiều dp[S+1]. Vòng lặp duyệt ngược từ S về t[i] là chìa khóa để đảm bảo mỗi item chỉ được cập nhật một lần cho mỗi trọng lượng. Logic tương tự như Solution 1.

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

Bài học kinh nghiệm

• Bài toán này là biến thể của bài toán Túi đồ (0/1 Knapsack Problem). Với n nhỏ (<=25) nhưng S lớn (<=30000), phương pháp quy hoạch động O(n*S) là tối ưu nhất, thay vì O(2^n).
• Sử dụng mảng 1 chiều và duyệt ngược (S -> t[i]) để tối ưu bộ nhớ và đảm bảo tính đúng đắn của thuật toán.

Lỗi thường gặp

• Lỗi duyệt xuôi trong vòng lặp thứ cấp của thuật toán Knapsack 1 chiều: Nếu duyệt từ t[i] đến S, một item có thể được sử dụng nhiều lần cho cùng một trạng thái (vượt quá giới hạn 1 lần chọn), dẫn đến kết quả sai.
• Quên kiểm tra điều kiện j >= t[i] trong vòng lặp để tránh truy cập chỉ số âm của mảng.