Hiểu bài toán

Bài toán yêu cầu tìm tổng khối lượng lớn nhất có thể chở được trong một chuyến xe, sao cho tổng khối lượng không vượt quá tải trọng C. Đây là bài toán cái túi (Knapsack) kinh điển với N bao ngô và tải trọng C. Với mỗi bao ngô, ta có thể chọn hoặc không chọn. Do N nhỏ (≤ 20), ta có thể sử dụng các phương pháp duyệt (quay lui) hoặc động optimization. Tuy nhiên, với C lớn (≤ 50000), các phương pháp DP dựa trên tải trọng sẽ hiệu quả về thời gian chạy.

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

Cách Quay lui (Backtracking)

#include <stdio.h>

int N, C;
int weights[25];
int max_weight = 0;

void Try(int index, int current_sum) {
    if (current_sum > C) return;
    if (index == N) {
        if (current_sum > max_weight) max_weight = current_sum;
        return;
    }
    // Không chọn bao thứ index
    Try(index + 1, current_sum);
    // Chọn bao thứ index
    Try(index + 1, current_sum + weights[index]);
}

int main() {
    scanf("%d %d", &N, &C);
    for (int i = 0; i < N; i++) {
        scanf("%d", &weights[i]);
    }
    Try(0, 0);
    printf("%d", max_weight);
    return 0;
}

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

Phương pháp này duyệt qua tất cả các khả năng chọn hoặc không chọn từng bao ngô. Với mỗi bao, đệ quy hai nhánh (chọn/không chọn). Độ phức tạp thời gian là O(2^N) do có 2^N cách chọn khác nhau. Với N=20, số bước là khoảng 1 triệu, đủ nhanh để chạy trong thời gian giới hạn. Không gian là độ sâu đệ quy O(N).

Cách Động vật lý dựa trên mảng 2 chiều

#include <stdio.h>

int main() {
    int n, c;
    scanf("%d%d", &n, &c);
    int a[n + 1];
    a[0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int dp[n + 1][c + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = 0;
    for (int i = 0; i <= c; i++) dp[0][i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= c; j++) {
            if (a[i] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                int choice1 = dp[i - 1][j];
                int choice2 = dp[i - 1][j - a[i]];
                dp[i][j] = (choice1 < choice2) ? choice1 : choice2;
            }
        }
    }
    int min = dp[0][c];
    for (int i = 1; i <= n; i++) {
        if (dp[i][c] < min) min = dp[i][c];
    }
    printf("%d", c - min);
    return 0;
}

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

Đây là cách tiếp cận DP kinh điển nhưng implement hơi phức tạp. Nó xây dựng bảng dp[i][j] lưu 'số dư' nhỏ nhất có thể khi xét i bao đầu tiên với tải trọng j. Tuy nhiên, code này khá cồng kềnh và dễ sai sót trong việc khởi tạo và truy vấn kết quả. Logic chung là tìm cách chia tải trọng sao cho số dư (C - tổng chọn) là nhỏ nhất.

Cách Động vật lý dựa trên mảng 1 chiều (Bitset Optimization)

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

int main() {
    int N, C;
    scanf("%d %d", &N, &C);
    int w;
    // dp[i] == 1表示 có thể đạt được tổng khối lượng i
    // Kích thước mảng là C + 1
    int dp[50001];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < N; i++) {
        scanf("%d", &w);
        // Duyệt ngược để tránh dùng lại bao ngô nhiều lần
        for (int j = C; j >= w; j--) {
            if (dp[j - w]) dp[j] = 1;
        }
    }
    // Tìm giá trị j lớn nhất mà dp[j] == 1
    for (int i = C; i >= 0; i--) {
        if (dp[i]) {
            printf("%d", i);
            break;
        }
    }
    return 0;
}

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

Đây là phương pháp tối ưu nhất trong các giải pháp mẫu. Ta dùng mảng 1 chiều dp où dp[x] là 1 nếu có thể tạo ra tổng khối lượng x. Sau khi xử lý hết các bao, ta chỉ cần tìm giá trị dp[C] đầu tiên từ C trở xuống là 1. Độ phức tạp là O(N*C) nhưng với C=50000 và N=20, số phép tính là 1 triệu, rất nhanh. Đây là biến thể của bài toán cái túi 0-1 tối ưu hóa không gian.

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

Bài học kinh nghiệm

• Bài toán này là bài toán cái túi (Knapsack) kinh điển 0-1.
• Với N nhỏ (≤20), quay lui là cách nghĩ đơn giản nhất và vẫn chấp nhận được.
• Với C ở mức vừa phải (≤50000), DP 1 chiều là phương pháp chuẩn để giải quyết bài toán này với độ ổn định cao.

Lỗi thường gặp

• Quên kiểm tra điều kiện current_sum > C trong đệ quy gây tràn số đệ quy (stack overflow) hoặc TLE.
• Trong DP 1 chiều, duyệt vòng lặp j từ 0 đến C thay vì từ C về 0 sẽ dẫn đến việc sử dụng cùng một bao ngô nhiều lần (bài toán cái túi đầy đủ thay vì 0-1).
• Sử dụng mảng 2 chiều trong DP với N=20, C=50000 có thể gây tràn bộ nhớ stack nếu khai báo局部变量, hoặc tốn bộ nhớ nếu khai báo global (khoảng 20500004 bytes ~ 4MB, vẫn OK nhưng 1 chiều tốt hơn).