Editorial for charm: Chuỗi hạt ngọc trai

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) kinh điển. Có N hạt ngọc trai, mỗi hạt có khối lượng Wk và giá trị Dk. Bessie cần chọn một số lượng hạt bất kỳ sao cho tổng khối lượng không vượt quá M để tối đa hóa tổng giá trị. Đây là bài toán 0/1 Knapsack vì mỗi hạt chỉ có thể chọn hoặc không chọn (không chọn nhiều lần).

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

Cách Quy hoạch động cơ bản (Mảng 2 chiều)

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

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

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int w[n+1], v[n+1];
    for(int i = 1; i <= n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }

    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));

    // dp[i][j]: giá trị lớn nhất có thể đạt được khi xét i vật đầu tiên với giới hạn khối lượng j
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            // Không chọn vật i
            dp[i][j] = dp[i-1][j];
            // Chọn vật i (nếu khối lượng cho phép)
            if(j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
            }
        }
    }

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

• Time Complexity: O(N * M) ~ 3402 * 12800 ≈ 43.5 triệu thao tác
• Space Complexity: O(N * M) ~ 3402 * 12800 * 4 bytes ≈ 170MB

Sử dụng mảng 2 chiều dp[i][j]. Dòng i đại diện cho việc xét i vật đầu tiên, cột j đại diện cho khối lượng giới hạn là j. Công thức chuyển trạng thái: dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]). Đây là cách tiếp cận trực quan nhất của thuật toán quy hoạch động.

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

#include<stdio.h>

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

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int dp[m+1];

    // Khởi tạo mảng dp với 0
    for(int i = 0; i <= m; i++) dp[i] = 0;

    for(int i = 0; i < n; i++) {
        int w, v;
        scanf("%d %d", &w, &v);
        // Duyệt ngược để đảm bảo mỗi vật chỉ được dùng 1 lần
        for(int j = m; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }

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

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

Tối ưu không gian bằng cách chỉ cần mảng 1 chiều dp[j]. Khi duyệt vật thứ i, ta duyệt ngược khối lượng từ M về w. Việc duyệt ngược đảm bảo rằng khi cập nhật dp[j], giá trị dp[j - w] vẫn là giá trị của vật trước (vật i-1), tránh việc chọn cùng một vật nhiều lần. Giải thuật này hiệu quả hơn đáng kể về mặt bộ nhớ.

Cách Hằng số tối ưu (Vét cạn)

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

// Hàm hoán đổi để sắp xếp
void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    int w[n], v[n];
    for(int i = 0; i < n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }

    // Biến lưu giá trị lớn nhất tìm được (giả sử có thể không chọn gì)
    int max_val = 0;

    // Duyệt qua tất cả các khả năng
    // Với n <= 3402, m <= 12800, 2^n là quá lớn.
    // Tuy nhiên, có thể áp dụng một số kỹ thuật:
    // 1. Nếu tổng w <= m, lấy tổng v.
    // 2. Nếu có item w=1, v lớn, có thể tối ưu.
    // Nhưng thực tế DP là chuẩn nhất.

    // Code dưới đây là code DP 1 chiều tối ưu (Solution 2)
    int dp[m+1];
    memset(dp, 0, sizeof(dp));

    for(int i = 0; i < n; i++) {
        for(int j = m; j >= w[i]; j--) {
            if(dp[j - w[i]] + v[i] > dp[j]) {
                dp[j] = dp[j - w[i]] + v[i];
            }
        }
    }

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

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

Đây thực chất là cách viết khác của giải thuật mảng 1 chiều. Trong bài toán này, các ràng buộc (N=3402, M=12800) đủ nhỏ để thuật toán O(N*M) chạy trong thời gian giới hạn. Nếu M lớn hơn đáng kể (ví dụ > 10^6), ta sẽ cần các kỹ thuật phức tạp hơn như 'Meet-in-the-middle' (vì N nhỏ) hoặc 'Knapsack with large weights'. Tuy nhiên, với ràng buộc hiện tại, DP 1 chiều là đủ.

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

Bài học kinh nghiệm

• Đây là bài toán 0/1 Knapsack kinh điển, sử dụng quy hoạch động.
• Biến trạng thái: dp[j] = giá trị lớn nhất với khối lượng giới hạn j.
• Quy tắc chuyển trạng thái: dp[j] = max(dp[j], dp[j - w[i]] + v[i]).
• Việc duyệt khối lượng ngược (từ M về w[i]) là bắt buộc để tránh chọn trùng vật.

Lỗi thường gặp

• Lưu ý thứ tự tham số trong input: N và M. Solution 1 của hieuochimchim nhầm lẫn giữa N và M khi khai báo mảng, nhưng may mắn thay logic quy hoạch động của code đó (dùng biến m cho số lượng và n cho giới hạn) lại khớp với input nếu ta đọc N vào biến m và M vào biến n. Tuy nhiên, cách đặt tên biến chuẩn nên là 'int n, m; scanf("%d %d", &n, &m);'.
• Sử dụng mảng 2 chiều khi không cần thiết dẫn đến tốn bộ nhớ (có thể gây MLE với các biên lớn hơn).
• Quên khởi tạo mảng dp hoặc sai lệch giá trị ban đầu (nên khởi tạo là 0).
• Duyệt xuôi trong vòng lặp cập nhật dp (vòng lặp j từ w[i] đến m) sẽ dẫn đến sai kết quả do cho phép chọn nhiều lần cùng một vật (Knapsack vô hạn thay vì 0/1 Knapsack).