Editorial for dicay: Nghé đi cày

Hiểu bài toán

Bài toán này là một bài toán quy hoạch động dạng túi đồ (Knapsack Problem). Cho n thửa ruộng, mỗi thửa có thời gian ti để cày và điểm số di nhận được. Nghé có tổng thời gian tối đa 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ố thu được là lớn nhất. Với n ≤ 25 và S ≤ 30000, ta cần một giải pháp hiệu quả để xử lý trong giới hạn thời gian cho phép.

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

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

#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
int main(){
    int n,S;
    scanf("%d%d",&n,&S);
    int t[n+1];
    int d[n+1];
    t[0]=0;
    d[0]=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&t[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&d[i]);
    }
    int dp[n+1][S+1];
    for(int i=0;i<=S;i++){
        dp[0][i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=S;j++){
            if(j<t[i]) dp[i][j]=dp[i-1][j];
            if(j>=t[i]){
                dp[i][j]=(dp[i-1][j]>dp[i-1][j-t[i]]+d[i])?dp[i-1][j]:dp[i-1][j-t[i]]+d[i];
            }
        }
    }
    printf("%d",dp[n][S]);
}

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

Đây là cách tiếp cận trực tiếp nhất của quy hoạch động túi đồ. Ta xây dựng bảng dp[i][j] thể hiện điểm số lớn nhất có thể đạt được khi xem xét i thửa ruộng đầu tiên với thời gian tối đa j.

• Với mỗi thửa ruộng i và mỗi thời gian j:
  • Nếu không chọn thửa ruộng i: Điểm là dp[i-1][j].
  • Nếu chọn thửa ruộng i (chỉ khi j >= t[i]): Điểm là dp[i-1][j - t[i]] + d[i].
  • dp[i][j] là giá trị lớn hơn của hai trường hợp trên.
• Không gian bảng là O(n * S), có thể tối ưu bộ nhớ.

Cách Quy hoạch động tối ưu bộ nhớ (Mảng 1 chiều)

#include <stdio.h>
#include <math.h>
int main(){
    int m, n;
    scanf("%d%d", &m, &n);
    int a[m+1];
    for(int i=1; i<=m; i++){
        scanf("%d", &a[i]);
    }
    int b[m+1];
    for(int i=1; i<=m; i++){
        scanf("%d", &b[i]);
    }
    int c[m+1][n+1];
    for(int i=0; i<=m; i++){
        for(int j=0; j<n+1; j++){
            if(i==0 || j==0)
            c[i][j] = 0;
            else{
                c[i][j] = c[i-1][j];
                if(j>=a[i])
                c[i][j] = fmax(c[i][j], c[i-1][j-a[i]] + b[i]);
            }
        }
    }
    printf("%d", c[m][n]);
}

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

Cách tiếp cận này tối ưu không gian bộ nhớ bằng cách nhận thấy rằng để tính giá trị của hàng i, ta chỉ cần thông tin từ hàng i-1.

• Ta sử dụng một mảng 1 chiều dp[j].
• Khi duyệt qua từng thửa ruộng, ta duyệt ngược thời gian j từ S về 0. Việc duyệt ngược đảm bảo rằng khi ta cập nhật dp[j] bằng dp[j - t[i]] + d[i], giá trị dp[j - t[i]] vẫn là giá trị của hàng i-1 (chưa bị cập nhật trong vòng lặp hiện tại).
• Độ phức tạp thời gian giữ nguyên là O(n * S) nhưng không gian chỉ còn O(S).

Cách Quy hoạch động truy vấn tối ưu (Tối ưu dòng lặp)

#include <stdio.h>
#include <math.h>
#include <string.h>

int timmax(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    int n, S;
    scanf("%d%d", &n, &S);
    int a[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int b[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }
    int c[n + 1][S + 1];
    memset(c, 0, sizeof(c));

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= S; j++) {
            c[i][j] = c[i - 1][j];
            if(j >= a[i - 1]) {
                c[i][j] = timmax(c[i][j], c[i - 1][j - a[i - 1]] + b[i - 1]);
            }
        }
    }
    printf("%d", c[n][S]);
}

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

Đây là biến thể của giải pháp quy hoạch động cơ bản, chỉ khác biệt nhỏ về cú pháp truy cập mảng (dùng chỉ số 0-based cho input nhưng bảng tính 1-based để tiện xử lý biên). Logic hoàn toàn tương tự Approach 1. Tuy nhiên, có thể tối ưu hơn nữa bằng cách kiểm tra if (t[i] > S) continue; trước khi vào vòng lặp j để giảm thời gian chạy thực tế.

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

Bài học kinh nghiệm

• Bài toán thuộc dạng 'Knapsack' (Túi đồ) cơ bản, mục tiêu tối đa hóa giá trị với ràng buộc về trọng lượng (thời gian).
• Quyết định cho mỗi thửa ruộng là 'Có chọn' hoặc 'Không chọn'. State của bài toán phụ thuộc vào chỉ số item hiện tại và dung lượng còn lại.
• Với ràng buộc về bộ nhớ, việc chuyển từ mảng 2 chiều sang mảng 1 chiều và lặp ngược là kỹ thuật chuẩn để đảm bảo tính đúng đắn của thuật toán.

Lỗi thường gặp

• Lỗi chỉ số mảng: Khi chuyển từ mảng 2 chiều sang 1 chiều hoặc thay đổi cách đánh chỉ số (0-based vs 1-based),很容易 bị sai logic truy cập mảng.
• Lỗi vòng lặp: Khi dùng mảng 1 chiều, nếu lặp xuôi từ 0 đến S, ta sẽ dùng chính kết quả vừa cập nhật của item hiện tại để tính toán (lỗi hoàn toàn sai logic 'phép chọn'). Phải lặp ngược từ S về 0.
• Xử lý số lượng lớn: Với S lên tới 30000 và n=25, độ phức tạp O(nS) ~ 7.510^5 phép tính, hoàn toàn chấp nhận được. Tuy nhiên, nếu S lớn hơn nhiều (ví dụ 10^9), cần phải dùng giải pháp kết hợp (Meet-in-the-middle) do O(n*S) quá lớn.