Editorial for project: Dự án

Hiểu bài toán

Bài toán yêu cầu chọn một tập hợp các dự án từ danh sách có sẵn sao cho tổng chi phí xây dựng (ci) của các dự án được chọn không vượt quá nguồn vốn S hiện có. Mục tiêu là tối đa hóa tổng lợi nhuận (pi) thu được từ các dự án đã chọn. Đây là bài toán cái túi (Knapsack) kinh điển: mỗi dự án có một 'trọng số' là chi phí ci và một 'giá trị' là lợi nhuận pi, ta cần chọn các dự án sao cho tổng trọng số ≤ S và tổng giá trị là lớn nhất.

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

Cách Quy hoạch động dạng mảng 1 chiều (Phổ biến)

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

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

int main() {
    int n, s;
    scanf("%d %d", &n, &s);
    int c[30], p[30];
    for (int i = 0; i < n; i++) scanf("%d", &c[i]);
    for (int i = 0; i < n; i++) scanf("%d", &p[i]);

    // dp[j] lưu lợi nhuận lớn nhất có thể đạt được với số vốn ban đầu là j
    int dp[30005];
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < n; i++) {
        // Duyệt ngược để đảm bảo mỗi dự án chỉ được dùng 1 lần
        for (int j = s; j >= c[i]; j--) {
            dp[j] = max(dp[j], dp[j - c[i]] + p[i]);
        }
    }

    printf("%d", dp[s]);
    return 0;
}

• Time Complexity: O(n * S) ~ 25 * 30000 = 750.000
• Space Complexity: O(S) ~ 30000

Đây là cách tiếp cận chuẩn cho bài toán Knapsack 0-1. Ta sử dụng một mảng 1 chiều dp where dp[j] là lợi nhuận tối đa với vốn j. Với mỗi dự án, ta duyệt ngược từ S về c[i]. Việc duyệt ngược đảm bảo rằng khi ta cập nhật dp[j] dựa trên dp[j - c[i]], ta đang sử dụng trạng thái của các dự án trước đó (chưa bao gồm dự án hiện tại), từ đó đảm bảo mỗi dự án chỉ được chọn tối đa một lần. Độ phức tạp thời gian là O(n*S) và bộ nhớ là O(S).

Cách Quy hoạch động dạng mảng 2 chiều

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    int n, s;
    scanf("%d %d", &n, &s);
    int *c = (int*)malloc(n * sizeof(int));
    int *p = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &c[i]);
    for (int i = 0; i < n; i++) scanf("%d", &p[i]);

    // dp[i][j] lưu lợi nhuận lớn nhất xét từ i dự án đầu với vốn j
    int **dp = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int*)calloc(s + 1, sizeof(int));
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= s; j++) {
            // Không chọn dự án i
            dp[i][j] = dp[i-1][j];
            // Chọn dự án i (nếu đủ vốn)
            if (j >= c[i-1]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - c[i-1]] + p[i-1]);
            }
        }
    }
    printf("%d", dp[n][s]);

    // Giải phóng bộ nhớ
    for (int i = 0; i <= n; i++) free(dp[i]);
    free(dp);
    free(c);
    free(p);
    return 0;
}

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

Sử dụng mảng 2 chiều dp[i][j] để lưu kết quả xét i dự án đầu tiên với ngân sách j. Ưu điểm của cách này là dễ hiểu và dễ truy xuất nguồn gốc của kết quả (backtracking). Tuy nhiên, nó tốn bộ nhớ hơn (khoảng 25300004 bytes ≈ 3MB, vẫn chấp nhận được nhưng lãng phí so với mảng 1 chiều). Logic: dp[i][j] = max(dp[i-1][j], dp[i-1][j - c[i]] + p[i]) nếu j >= c[i].

Cách Brute Force (Quay lui/Thử tất cả các khả năng)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, s;
vector<int> c, p;
int max_profit = 0;

void solve(int index, int current_cost, int current_profit) {
    if (current_cost > s) return;
    if (index == n) {
        max_profit = max(max_profit, current_profit);
        return;
    }
    // Chọn dự án index
    solve(index + 1, current_cost + c[index], current_profit + p[index]);
    // Không chọn dự án index
    solve(index + 1, current_cost, current_profit);
}

int main() {
    cin >> n >> s;
    c.resize(n); p.resize(n);
    for (int i = 0; i < n; i++) cin >> c[i];
    for (int i = 0; i < n; i++) cin >> p[i];
    solve(0, 0, 0);
    cout << max_profit;
    return 0;
}

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

Vì n nhỏ (≤ 25), ta có thể duyệt qua tất cả các khả năng chọn hoặc không chọn từng dự án bằng đệ quy. Có tổng cộng 2^n cách chọn. Với n=25, 2^25 ≈ 33 triệu, đây là một số lớn nhưng vẫn có thể chạy được trong thời gian giới hạn của một số bài toán nhỏ hơn, tuy nhiên với n=25 thì khá sát sao. Phương pháp này không hiệu quả bằng DP nhưng là một cách tiếp cận trực quan.

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 Knapsack 0-1 kinh điển: chọn các item sao cho tổng trọng số (chi phí) ≤ Capacity (S) và tổng giá trị (lợi nhuận) là lớn nhất.
• Với ràng buộc n ≤ 25 và S ≤ 30000, phương pháp Quy hoạch động dạng mảng 1 chiều (O(n*S)) là tối ưu nhất về cả thời gian và bộ nhớ.
• Kỹ thuật 'duyệt ngược' trong DP mảng 1 chiều là bắt buộc để tránh trường hợp một dự án bị tính nhiều lần trong cùng một tổ hợp.

Lỗi thường gặp

• Lầm tưởng rằng với n=25 thì Brute Force là đủ nhanh. Mặc dù 2^25 (khoảng 33 triệu) có thể chạy trên máy cá nhân, nhưng trong môi trường thi đấu với nhiều test case hoặc yêu cầu độ chính xác cao, Brute Force rủi ro hơn và chậm hơn nhiều so với DP.
• Quên kiểm tra xem chi phí dự án có vượt quá S hay không trong quá trình nhập liệu (mặc dù DP sẽ tự xử lý nếu viết đúng vòng lặp j >= c[i]).
• Sử dụng mảng 2 chiều khi S lớn (30000) có thể gây tốn bộ nhớ không cần thiết, mặc dù với giới hạn đề bài thì vẫn ổn. Nên ưu tiên mảng 1 chiều.