Khóa học CTDL và GT

Bài 28.4: Tối ưu không gian trong DP Bitmask

Chào mừng các bạn quay trở lại với series bài viết về Cấu trúc dữ liệu và Giải thuật của FullhouseDev!

Trong những bài trước, chúng ta đã làm quen với sức mạnh của Dynamic Programming kết hợp Bitmask (DP Bitmask) để giải quyết các bài toán trên tập nhỏ, thường có kích thước N khoảng dưới 20. Kỹ thuật này sử dụng một bitmask để biểu diễn một tập hợp con của N phần tử, cho phép chúng ta định nghĩa trạng thái DP dựa trên các tập hợp con này.

Trạng thái cơ bản nhất của DP Bitmask thường là dp[mask], biểu diễn kết quả cho tập hợp con được mã hóa bởi mask. Số lượng trạng thái là 2^N. Nếu N=20, 2^N là khoảng một triệu trạng thái, thường là chấp nhận được về mặt thời gian và bộ nhớ.

Tuy nhiên, có nhiều bài toán mà trạng thái DP không chỉ phụ thuộc vào bitmask đơn thuần, mà còn phụ thuộc vào một tham số khác, ví dụ như chỉ số của phần tử đang được xem xét. Một dạng trạng thái phổ biến là dp[i][mask], biểu diễn kết quả sau khi xem xét i phần tử đầu tiên, và mask biểu diễn trạng thái của một tập hợp con nào đó liên quan đến các phần tử này hoặc một tập hợp khác.

Khi đó, tổng số trạng thái sẽ là O(N * 2^M), trong đó M là số bit trong mask (thường M <= N). Nếu cả N và M đều đủ lớn (ví dụ, N=200, M=15), thì N * 2^M có thể lên tới 200 * 32768, là khoảng hơn 6 triệu trạng thái. Mỗi trạng thái lưu trữ một giá trị (int, long long,...), việc này có thể dẫn đến việc sử dụng lượng bộ nhớ vượt quá giới hạn cho phép trong các môi trường lập trình thi đấu (thường là 256MB hoặc 512MB).

Đây chính là lúc chúng ta cần nghĩ đến việc tối ưu không gian cho DP Bitmask.

Tại sao cần tối ưu không gian trong DP Bitmask?

Như đã nói, vấn đề chính là lượng bộ nhớ.

Một mảng dp[N][1 << M] kiểu int sẽ cần N * 2^M * 4 bytes. Ví dụ:

• N=20, M=20: 20 * 2^20 * 4 bytes = 20 * 1048576 * 4 bytes ≈ 80 MB. Chấp nhận được.
• N=200, M=15: 200 * 2^15 * 4 bytes = 200 * 32768 * 4 bytes ≈ 26.2 MB. Chấp nhận được.
• N=200, M=20: 200 * 2^20 * 4 bytes ≈ 800 MB. Vượt quá giới hạn!
• N=1000, M=12: 1000 * 2^12 * 4 bytes = 1000 * 4096 * 4 bytes ≈ 16 MB. Chấp nhận được.

Rõ ràng, khi có thêm một chiều N lớn, ngay cả với M nhỏ, lượng bộ nhớ có thể tăng vọt. Việc tối ưu không gian sẽ giúp chúng ta giảm bộ nhớ từ O(N * 2^M) xuống còn O(2^M), làm cho bài toán khả thi hơn.

Nguyên lý tối ưu không gian

Nguyên lý cơ bản để tối ưu không gian trong DP là quan sát sự phụ thuộc giữa các trạng thái. Nếu trạng thái dp[i][mask] chỉ phụ thuộc vào các trạng thái ở "lớp" trước đó, ví dụ dp[i-1][mask'], mà không phụ thuộc vào dp[i-2] hay xa hơn, thì chúng ta chỉ cần lưu trữ kết quả của hai lớp gần nhất (i và i-1).

Điều này hoàn toàn tương tự với kỹ thuật tối ưu không gian trong DP kinh điển, ví dụ như bài toán Knapsack 0/1 từ O(N*W) xuống O(W). Trạng thái dp[i][w] (giá trị lớn nhất với i vật phẩm và sức chứa w) chỉ phụ thuộc vào dp[i-1][w] (không chọn vật phẩm i) và dp[i-1][w - weight[i-1]] (chọn vật phẩm i). Chúng ta chỉ cần hai hàng để lưu trữ: hàng cho vật phẩm i-1 và hàng cho vật phẩm i.

Trong DP Bitmask với trạng thái dp[i][mask], nếu dp[i][mask] chỉ phụ thuộc vào dp[i-1][mask'] cho mọi mask', chúng ta có thể giảm không gian bằng cách chỉ sử dụng hai mảng O(2^M) hoặc thậm chí một mảng O(2^M).

Kỹ thuật tối ưu: Sử dụng hai mảng (hoặc một mảng)

Xét bài toán mà trạng thái DP có dạng dp[i][mask], và công thức chuyển trạng thái chỉ sử dụng các giá trị từ dp[i-1][...].

Ví dụ: dp[i][mask] = f(dp[i-1][mask'], dp[i-1][mask''], ...)

Chúng ta có thể sử dụng hai mảng 1D có kích thước 2^M:

• prev_dp[mask]: Lưu trữ giá trị dp[i-1][mask]
• curr_dp[mask]: Lưu trữ giá trị dp[i][mask]

Quá trình tính toán sẽ diễn ra như sau:

1. Khởi tạo prev_dp cho trạng thái cơ bản (tương ứng với i=0 hoặc bước khởi đầu).
2. Lặp i từ 1 đến N.
3. Tại mỗi bước i:
   • Khởi tạo curr_dp dựa trên các giá trị từ prev_dp. Thường thì curr_dp sẽ được khởi tạo bằng một bản sao của prev_dp, hoặc bằng giá trị "không làm gì" dựa trên prev_dp.
   • Tính toán các trạng thái curr_dp[new_mask] dựa trên các trạng thái prev_dp[old_mask] theo công thức chuyển trạng thái của bài toán.
   • Sau khi tính xong tất cả các trạng thái cho curr_dp dựa trên prev_dp, gán prev_dp = curr_dp để chuẩn bị cho bước lặp tiếp theo (i+1).
4. Kết quả cuối cùng sẽ nằm trong mảng prev_dp (hoặc curr_dp sau vòng lặp cuối cùng).

Kỹ thuật này giảm bộ nhớ từ O(N * 2^M) xuống O(2 * 2^M) = O(2^M).

Để tối ưu hơn nữa, đôi khi chúng ta có thể chỉ cần một mảng 1D kích thước 2^M. Tuy nhiên, điều này đòi hỏi phải tính toán các trạng thái dp[mask] cho bước i một cách cẩn thận, thường bằng cách lặp qua mask theo một thứ tự đặc biệt (ví dụ, từ lớn đến nhỏ) để đảm bảo rằng khi tính dp[mask] ở bước i, giá trị dp[mask'] mà nó phụ thuộc vào (từ bước i-1) vẫn chưa bị ghi đè bởi giá trị mới của bước i.

Hãy xem xét một ví dụ cụ thể.

Ví dụ Minh Họa: Bài toán Gán việc (phiên bản đơn giản)

Bài toán: Có N người và M công việc. Mỗi người i có thể làm công việc j với giá trị value[i][j]. Mỗi người chỉ làm tối đa một công việc, mỗi công việc chỉ được giao cho tối đa một người. Hãy chọn một tập hợp các cặp (người, công việc) để tối đa hóa tổng giá trị. N có thể lớn (ví dụ 200), M nhỏ (ví dụ 15).

Phân tích: Đây là một dạng bài toán Maximum Weighted Bipartite Matching, có thể giải bằng Min-Cost Max-Flow. Tuy nhiên, với M nhỏ, chúng ta có thể dùng DP Bitmask.

Gọi trạng thái DP là dp[i][mask], với:

• i: Số người đầu tiên đã được xem xét (từ 0 đến N).
• mask: Một bitmask có M bit, bit thứ j = 1 nếu công việc j đã được giao cho một người trong số i người đầu tiên.

dp[i][mask] = giá trị lớn nhất có thể đạt được khi xem xét i người đầu tiên, và tập các công việc đã được giao là mask.

Công thức chuyển trạng thái: Xét người thứ i (chỉ số i-1 trong mảng 0-indexed). Khi xử lý người i, chúng ta có hai lựa chọn:

1. Không giao công việc nào cho người i: Trạng thái mask sau khi xem xét i người vẫn giống như khi xem xét i-1 người. dp[i][mask] = max(dp[i][mask], dp[i-1][mask])
2. Giao công việc j cho người i: Người i làm công việc j. Điều này chỉ có thể thực hiện nếu công việc j chưa được giao (bit thứ j trong mask chưa được set). Nếu công việc j chưa được giao trong trạng thái mask' của i-1 người, thì sau khi người i làm công việc j, trạng thái mới sẽ là mask' | (1 << j), và giá trị tăng thêm value[i-1][j]. dp[i][mask | (1 << j)] = max(dp[i][mask | (1 << j)], dp[i-1][mask] + value[i-1][j]) cho mọi j mà bit j không set trong mask.

Cơ sở DP: dp[0][0] = 0. Tất cả các trạng thái dp[0][mask] khác (với mask > 0) có giá trị âm vô cùng (hoặc một giá trị rất nhỏ) để biểu thị không thể đạt được.

Kích thước trạng thái: O(N * 2^M). Nếu N=200, M=15, đây là 200 * 2^15 trạng thái.

Cài đặt DP O(N * 2^M) (Để so sánh)

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

using namespace std;

const int INF = 1e9; // Sử dụng giá trị âm vô cùng lớn để biểu thị trạng thái không đạt được

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M; // N: số người, M: số công việc
    cin >> N >> M;

    // value[i][j]: giá trị nếu người i làm công việc j
    // Sử dụng 0-indexed cho người và công việc
    vector<vector<int>> value(N, vector<int>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> value[i][j];
        }
    }

    // dp[i][mask]: giá trị lớn nhất khi xem xét i người đầu tiên,
    // tập công việc đã giao là mask
    vector<vector<int>> dp(N + 1, vector<int>(1 << M, -INF));

    // Cơ sở DP: 0 người đã xem xét, 0 công việc đã giao, giá trị 0
    dp[0][0] = 0;

    // Lặp qua số người đã xem xét
    for (int i = 0; i < N; ++i) { // Xem xét người i (0-indexed)
        // Lặp qua tất cả các mask có thể sau khi xem xét i-1 người
        for (int mask = 0; mask < (1 << M); ++mask) {
            // Nếu trạng thái dp[i][mask] không đạt được, bỏ qua
            if (dp[i][mask] == -INF) continue;

            // Lựa chọn 1: Không giao công việc nào cho người i
            // Trạng thái mask vẫn giữ nguyên sau khi xem xét người i
            dp[i + 1][mask] = max(dp[i + 1][mask], dp[i][mask]);

            // Lựa chọn 2: Giao công việc j cho người i
            for (int j = 0; j < M; ++j) { // Thử giao công việc j (0-indexed)
                // Nếu công việc j chưa được giao trong mask
                if (!((mask >> j) & 1)) {
                    int next_mask = mask | (1 << j);
                    dp[i + 1][next_mask] = max(dp[i + 1][next_mask], dp[i][mask] + value[i][j]);
                }
            }
        }
    }

    // Kết quả là giá trị lớn nhất trong tất cả các trạng thái cuối cùng
    // sau khi xem xét N người. Không nhất thiết phải giao hết M công việc.
    int max_value = 0;
    for (int mask = 0; mask < (1 << M); ++mask) {
        max_value = max(max_value, dp[N][mask]);
    }

    cout << "Max value (O(N * 2^M) space): " << max_value << endl;

    return 0;
}

Giải thích code:

• dp[i][mask] lưu trữ giá trị lớn nhất. Khởi tạo bằng -INF (một số âm rất lớn) để dễ dàng lấy max. dp[0][0] được khởi tạo là 0.
• Vòng lặp ngoài cùng for (int i = 0; i < N; ++i): Duyệt qua từng người từ 0 đến N-1. dp[i][mask] sẽ là kết quả sau khi xem xét người 0 đến i-1.
• Vòng lặp giữa for (int mask = 0; mask < (1 << M); ++mask): Duyệt qua tất cả các trạng thái mask có thể có sau khi xem xét người i-1.
• dp[i+1][mask] = max(dp[i+1][mask], dp[i][mask]);: Biểu thị lựa chọn không giao việc cho người i. Trạng thái mask không đổi, giá trị giữ nguyên.
• Vòng lặp trong cùng for (int j = 0; j < M; ++j): Thử giao công việc j cho người i.
• if (!((mask >> j) & 1)): Kiểm tra xem công việc j đã có trong mask (trạng thái trước đó) chưa. Nếu chưa, thì có thể giao.
• int next_mask = mask | (1 << j);: Mask mới sau khi giao công việc j.
• dp[i + 1][next_mask] = max(dp[i + 1][next_mask], dp[i][mask] + value[i][j]);: Cập nhật giá trị lớn nhất cho trạng thái mới.
• Kết quả cuối cùng là giá trị lớn nhất trong hàng dp[N], vì người N là người cuối cùng được xem xét.

Tối ưu không gian O(2^M) với hai mảng

Vì dp[i+1][mask] chỉ phụ thuộc vào dp[i][...], chúng ta có thể giảm chiều i.

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

using namespace std;

const int INF = 1e9; // Sử dụng giá trị âm vô cùng lớn để biểu thị trạng thái không đạt được

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M; // N: số người, M: số công việc
    cin >> N >> M;

    vector<vector<int>> value(N, vector<int>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> value[i][j];
        }
    }

    // prev_dp[mask]: giá trị lớn nhất khi xem xét người i-1, tập công việc là mask
    // curr_dp[mask]: giá trị lớn nhất khi xem xét người i, tập công việc là mask
    vector<int> prev_dp(1 << M, -INF);
    vector<int> curr_dp(1 << M, -INF);

    // Cơ sở DP: 0 người đã xem xét, 0 công việc đã giao, giá trị 0
    prev_dp[0] = 0;

    // Lặp qua số người đã xem xét
    for (int i = 0; i < N; ++i) { // Xem xét người i (0-indexed)
        // Bước 1: Khởi tạo curr_dp. Ban đầu, không giao việc cho người i
        // nên giá trị của curr_dp giống như prev_dp
        curr_dp = prev_dp; // Sử dụng phép gán vector để sao chép

        // Bước 2: Cập nhật curr_dp bằng cách giao công việc cho người i
        // Lặp qua tất cả các mask có thể sau khi xem xét i-1 người
        for (int mask = 0; mask < (1 << M); ++mask) {
             // Nếu trạng thái prev_dp[mask] không đạt được, bỏ qua
            if (prev_dp[mask] == -INF) continue;

            // Thử giao công việc j cho người i
            for (int j = 0; j < M; ++j) { // Thử giao công việc j (0-indexed)
                // Nếu công việc j chưa được giao trong mask
                if (!((mask >> j) & 1)) {
                    int next_mask = mask | (1 << j);
                    curr_dp[next_mask] = max(curr_dp[next_mask], prev_dp[mask] + value[i][j]);
                }
            }
        }

        // Chuẩn bị cho bước lặp tiếp theo: curr_dp trở thành prev_dp
        prev_dp = curr_dp; // Hoặc swap(prev_dp, curr_dp) để hiệu quả hơn
    }

    // Kết quả là giá trị lớn nhất trong prev_dp sau khi xem xét N người
    int max_value = 0;
    for (int mask = 0; mask < (1 << M); ++mask) {
        max_value = max(max_value, prev_dp[mask]);
    }

    cout << "Max value (O(2^M) space with two arrays): " << max_value << endl;

    return 0;
}

Giải thích code:

• Chúng ta chỉ cần hai mảng prev_dp và curr_dp, mỗi mảng kích thước 2^M.
• prev_dp lưu kết quả cho người i-1, curr_dp tính toán kết quả cho người i.
• Trước khi xử lý người i, curr_dp được khởi tạo bằng cách sao chép prev_dp. Điều này tương ứng với lựa chọn không giao việc cho người i.
• Sau đó, chúng ta lặp qua các mask trong prev_dp và thử giao công việc j cho người i. Kết quả được cập nhật vào curr_dp.
• Sau khi xử lý xong người i (tức là tính toán xong curr_dp cho tất cả các mask), prev_dp được gán bằng curr_dp để chuẩn bị cho bước lặp tiếp theo.
• Bộ nhớ sử dụng giảm đáng kể xuống O(2^M).

Tối ưu không gian O(2^M) với một mảng

Chúng ta có thể tối ưu hơn nữa bằng cách chỉ sử dụng một mảng dp[mask]. Khi tính toán cho người i, mảng dp đang lưu trữ kết quả sau khi xem xét người i-1. Chúng ta sẽ cập nhật nó để lưu trữ kết quả sau khi xem xét người i.

Vấn đề là nếu chúng ta cập nhật dp[mask | (1 << j)] dựa trên dp[mask], và sau đó lại sử dụng giá trị dp[mask | (1 << j)] đã cập nhật này để tính toán một trạng thái khác trong cùng vòng lặp xử lý người i, thì sẽ sai.

Công thức chuyển trạng thái là dp[i][new_mask] = max(..., dp[i-1][old_mask] + value). Nếu chúng ta chỉ dùng một mảng dp, thì dp[new_mask] = max(..., dp[old_mask] + value). Để đảm bảo dp[old_mask] luôn là giá trị từ bước i-1, chúng ta cần duyệt mask theo một thứ tự sao cho old_mask luôn được xử lý sau new_mask trong vòng lặp hiện tại.

Trong ví dụ này, new_mask là mask | (1 << j), và old_mask là mask. Rõ ràng new_mask có nhiều bit 1 hơn hoặc bằng old_mask. Nếu chúng ta duyệt mask từ giá trị lớn đến nhỏ, khi cập nhật dp[mask | (1 << j)] sử dụng dp[mask], giá trị dp[mask] hiện tại vẫn là giá trị từ bước i-1 (vì các mask lớn hơn nó đã được xử lý rồi).

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

using namespace std;

const int INF = 1e9; // Sử dụng giá trị âm vô cùng lớn để biểu thị trạng thái không đạt được

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M; // N: số người, M: số công việc
    cin >> N >> M;

    vector<vector<int>> value(N, vector<int>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> value[i][j];
        }
    }

    // dp[mask]: giá trị lớn nhất khi xem xét người i, tập công việc là mask
    // Mảng này sẽ được cập nhật tại chỗ
    vector<int> dp(1 << M, -INF);

    // Cơ sở DP: 0 người đã xem xét, 0 công việc đã giao, giá trị 0
    dp[0] = 0;

    // Lặp qua số người đã xem xét
    for (int i = 0; i < N; ++i) { // Xem xét người i (0-indexed)
        // Lặp qua tất cả các mask. DUYỆT TỪ LỚN ĐẾN NHỎ
        // Điều này đảm bảo khi ta dùng dp[mask] (từ bước i-1) để cập nhật
        // dp[mask | (1 << j)] (cho bước i), thì dp[mask] chưa bị cập nhật
        // trong vòng lặp hiện tại.
        for (int mask = (1 << M) - 1; mask >= 0; --mask) {
            // Nếu trạng thái dp[mask] không đạt được ở bước i-1, bỏ qua
            if (dp[mask] == -INF) continue;

            // Lựa chọn 1: Không giao công việc nào cho người i.
            // Giá trị dp[mask] (cho bước i-1) vẫn được giữ nguyên,
            // trở thành giá trị cho dp[mask] ở bước i.
            // Ta không cần làm gì thêm ở đây vì vòng lặp đã bắt đầu với
            // giá trị từ bước i-1.

            // Lựa chọn 2: Giao công việc j cho người i
            for (int j = 0; j < M; ++j) { // Thử giao công việc j (0-indexed)
                // Nếu công việc j chưa được giao trong mask
                if (!((mask >> j) & 1)) {
                    int next_mask = mask | (1 << j);
                    dp[next_mask] = max(dp[next_mask], dp[mask] + value[i][j]);
                }
            }
        }
    }

    // Kết quả là giá trị lớn nhất trong dp sau khi xem xét N người
    int max_value = 0;
    for (int mask = 0; mask < (1 << M); ++mask) {
        max_value = max(max_value, dp[mask]);
    }

    cout << "Max value (O(2^M) space with one array): " << max_value << endl;

    return 0;
}

Giải thích code:

• Chỉ sử dụng một mảng dp kích thước 2^M.
• Vòng lặp ngoài cùng vẫn duyệt người i từ 0 đến N-1.
• Vòng lặp mask for (int mask = (1 << M) - 1; mask >= 0; --mask): Đây là điểm mấu chốt. Duyệt mask từ giá trị lớn nhất xuống 0.
• Khi xem xét mask hiện tại ở người i:
  • Giá trị dp[mask] đang chứa kết quả từ người i-1.
  • Lựa chọn 1 (không giao việc): Giá trị này dp[mask] (của người i-1) chính là giá trị khi không giao việc cho người i để đạt được mask mask (của người i). Không cần cập nhật gì thêm cho dp[mask] ở đây.
  • Lựa chọn 2 (giao việc j): Chúng ta tính dp[mask | (1 << j)] = max(dp[mask | (1 << j)], dp[mask] + value[i][j]). Vì mask | (1 << j) luôn lớn hơn mask, và chúng ta đang duyệt mask từ lớn xuống nhỏ, nên khi chúng ta thực hiện cập nhật này, dp[mask | (1 << j)] chưa bị ghi đè bởi kết quả của người i. Giá trị dp[mask] được sử dụng ở đây vẫn là giá trị từ bước i-1, đảm bảo tính đúng đắn.

Kỹ thuật dùng một mảng và duyệt mask theo thứ tự đặc biệt này là cách tối ưu không gian phổ biến nhất khi DP có dạng dp[i][mask] phụ thuộc vào dp[i-1][mask'] và new_mask được tạo ra bằng cách thêm bit vào old_mask.

Ví dụ Minh Họa 2: Lựa chọn vật phẩm theo thể loại

Bài toán: Có N vật phẩm. Mỗi vật phẩm i có một giá trị v[i] và thuộc về một thể loại cat[i]. Có tổng cộng M thể loại. Chúng ta muốn chọn một tập hợp con các vật phẩm sao cho đúng một vật phẩm được chọn từ mỗi thể loại trong một tập hợp đích cho trước TARGET_MASK (một bitmask có M bit). Hãy tìm giá trị lớn nhất có thể đạt được. N có thể lớn (ví dụ 1000), M nhỏ (ví dụ 12).

Phân tích: DP có thể có dạng dp[i][mask], với:

• i: Số vật phẩm đầu tiên đã được xem xét (từ 0 đến N).
• mask: Một bitmask có M bit, bit thứ j = 1 nếu đã chọn ít nhất một vật phẩm từ thể loại j trong số i vật phẩm đầu tiên.

dp[i][mask] = giá trị lớn nhất có thể đạt được khi xem xét i vật phẩm đầu tiên, và tập các thể loại đã có ít nhất một vật phẩm được chọn là mask.

Công thức chuyển trạng thái: Xét vật phẩm thứ i (chỉ số i-1 trong mảng 0-indexed), có giá trị v = v[i-1] và thể loại c = cat[i-1]. Khi xử lý vật phẩm i, chúng ta có hai lựa chọn:

1. Không chọn vật phẩm i: Trạng thái mask sau khi xem xét i vật phẩm vẫn giống như khi xem xét i-1 vật phẩm. dp[i][mask] = max(dp[i][mask], dp[i-1][mask])
2. Chọn vật phẩm i: Nếu vật phẩm i được chọn, thể loại c của nó sẽ được thêm vào tập các thể loại đã chọn. Trạng thái mask mới sẽ là mask_truoc_do | (1 << c). dp[i][mask | (1 << c)] = max(dp[i][mask | (1 << c)], dp[i-1][mask] + v[i-1]) cho mọi mask có thể đạt được sau khi xem xét i-1 vật phẩm.

Lưu ý: Định nghĩa này dp[i][mask] là "ít nhất một vật phẩm từ thể loại trong mask". Bài toán yêu cầu "đúng một". Điều này làm cho DP phức tạp hơn một chút hoặc cần định nghĩa lại mask.

• Định nghĩa lại DP: dp[i][mask] = giá trị lớn nhất khi xem xét i vật phẩm đầu tiên, và mask biểu diễn tập các thể loại đã chọn đúng một vật phẩm từ đó. Điều này phức tạp vì khi chọn vật phẩm i thuộc thể loại c:
  • Nếu thể loại c chưa có trong mask: mask mới là mask | (1 << c), giá trị tăng.
  • Nếu thể loại c đã có trong mask: Chọn thêm vật phẩm i làm cho thể loại c có >1 vật phẩm. Trạng thái này có thể không hợp lệ hoặc cần một cách mã hóa khác.

Cách đơn giản hơn với yêu cầu "đúng một" là sử dụng DP dựa trên số người/vật phẩm đã gán/xem xét và mask biểu diễn các công việc/thể loại đã được gán/chọn. Ví dụ 1 (Gán việc) đã làm điều này.

Quay lại ví dụ 1 với một chút thay đổi trong câu hỏi để khớp với yêu cầu "đúng một": Bài toán (ví dụ 1, sửa): Có N người và M công việc (N >= M). Mỗi người i có thể làm công việc j với giá trị value[i][j]. Mỗi người chỉ làm tối đa một công việc, mỗi công việc chỉ được giao cho đúng một người. Chọn M người trong số N người để giao cho M công việc, tối đa hóa tổng giá trị. N lớn (ví dụ 200), M nhỏ (ví dụ 15).

Trạng thái dp[i][mask] vẫn là max giá trị khi xem xét i người đầu tiên, mask là tập công việc đã giao.

Công thức chuyển trạng thái: Khi xem xét người i (0-indexed):

1. Không chọn người i để làm công việc nào: dp[i+1][mask] = max(dp[i+1][mask], dp[i][mask])
2. Chọn người i làm công việc j: Chỉ khi công việc j chưa được giao (bit j trong mask không set). dp[i+1][mask | (1 << j)] = max(dp[i+1][mask | (1 << j)], dp[i][mask] + value[i][j])

Cơ sở: dp[0][0] = 0.

Kết quả cuối cùng: Giá trị dp[N][(1 << M) - 1], vì chúng ta phải chọn đúng M công việc (tức là mask phải là (1<<M)-1).

Cả hai cài đặt O(N 2^M) và O(2^M) ở trên đều áp dụng được cho phiên bản sửa đổi này. Chỉ cần thay đổi cách lấy kết quả cuối cùng từ max_element trên hàng cuối cùng thành lấy giá trị tại dp[N][(1 << M) - 1] (đối với O(N 2^M)) hoặc prev_dp[(1 << M) - 1] (đối với O(2^M) hai mảng) hoặc dp[(1 << M) - 1] (đối với O(2^M) một mảng). Nhớ kiểm tra xem giá trị cuối cùng có phải là -INF không, nếu có nghĩa là không thể hoàn thành tất cả công việc.

Cài đặt O(2^M) một mảng cho ví dụ 1 (sửa đổi)

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

using namespace std;

const int INF = 1e9; // Sử dụng giá trị âm vô cùng lớn để biểu thị trạng thái không đạt được

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M; // N: số người, M: số công việc (N >= M)
    cin >> N >> M;

    vector<vector<int>> value(N, vector<int>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> value[i][j];
        }
    }

    // dp[mask]: giá trị lớn nhất khi xem xét người i, tập công việc đã giao là mask
    vector<int> dp(1 << M, -INF);

    // Cơ sở DP: 0 người đã xem xét, 0 công việc đã giao, giá trị 0
    dp[0] = 0;

    // Lặp qua số người đã xem xét
    for (int i = 0; i < N; ++i) { // Xem xét người i (0-indexed)
        // Lặp qua tất cả các mask. DUYỆT TỪ LỚN ĐẾN NHỎ
        for (int mask = (1 << M) - 1; mask >= 0; --mask) {
            // Nếu trạng thái dp[mask] không đạt được ở bước i-1, bỏ qua
            if (dp[mask] == -INF) continue;

            // Lựa chọn 1: Không chọn người i làm công việc nào.
            // dp[mask] ở bước i giữ nguyên giá trị từ bước i-1.
            // Không cần làm gì thêm trong vòng lặp này.

            // Lựa chọn 2: Chọn người i làm công việc j
            for (int j = 0; j < M; ++j) { // Thử giao công việc j (0-indexed)
                // Nếu công việc j chưa được giao trong mask
                if (!((mask >> j) & 1)) {
                    int next_mask = mask | (1 << j);

                    // Để ý: Chỉ cập nhật nếu số công việc đã giao không vượt quá M
                    // Điều này được đảm bảo tự nhiên bởi kích thước mask (M bit)
                    // Nhưng nếu bài toán có ràng buộc khác, cần kiểm tra thêm

                    // Cập nhật giá trị cho trạng thái next_mask ở bước i
                    dp[next_mask] = max(dp[next_mask], dp[mask] + value[i][j]);
                }
            }
        }
    }

    // Kết quả cuối cùng: giá trị lớn nhất khi tất cả M công việc đã được giao
    int final_mask = (1 << M) - 1;
    int max_value = dp[final_mask];

    // Nếu dp[final_mask] vẫn là -INF, nghĩa là không thể hoàn thành M công việc
    if (max_value == -INF) {
        cout << "Cannot assign all M jobs." << endl;
    } else {
        cout << "Max value (O(2^M) space with one array, exactly M jobs): " << max_value << endl;
    }

    return 0;
}

Lưu ý:

• Trong ví dụ 1 (sửa đổi), chúng ta cần N >= M để có thể gán tất cả M công việc cho M người khác nhau.
• Kết quả cuối cùng là dp[(1 << M) - 1] (mask với tất cả M bit set) vì yêu cầu là gán đúng một công việc cho mỗi công việc (tức là tất cả M công việc phải được gán).
• Nếu yêu cầu chỉ là gán tối đa một công việc cho mỗi công việc và người (như ví dụ 1 ban đầu), thì kết quả cuối cùng là max_element trên toàn bộ mảng dp sau khi xem xét N người.

Kỹ thuật tối ưu không gian này rất hữu ích khi một trong hai chiều của DP (N hoặc M) nhỏ (để 2^M là chấp nhận được) nhưng chiều còn lại (N) lại lớn. Nó biến trạng thái O(N * 2^M) thành O(2^M).

Khi nào có thể tối ưu?

Kỹ thuật tối ưu không gian từ O(N * 2^M) xuống O(2^M) (hoặc tương tự) áp dụng khi:

1. Trạng thái DP có dạng dp[i][mask], trong đó i là chỉ số của phần tử đang được xử lý (hoặc số phần tử đã xử lý), và mask là một bitmask biểu diễn trạng thái của một tập hợp khác hoặc một tập hợp con liên quan.
2. Công thức chuyển trạng thái dp[i][...] chỉ phụ thuộc vào các giá trị từ dp[i-1][...].
3. Khi sử dụng một mảng duy nhất, thứ tự duyệt các mask phải đảm bảo rằng khi tính toán dp[new_mask] dựa trên dp[old_mask], giá trị dp[old_mask] vẫn là giá trị từ bước i-1, chưa bị ghi đè bởi bước i. Thường thì nếu new_mask được tạo ra bằng cách thêm bit vào old_mask, duyệt mask từ lớn đến nhỏ sẽ hoạt động. Nếu new_mask được tạo ra bằng cách xóa bit khỏi old_mask, duyệt mask từ nhỏ đến lớn sẽ hoạt động.

Không phải mọi DP Bitmask đều có chiều i để tối ưu theo cách này. Ví dụ, trong bài toán TSP cổ điển với trạng thái dp[mask][u] (chi phí nhỏ nhất đi qua các đỉnh trong mask và kết thúc tại đỉnh u), chúng ta không có một chiều i duyệt qua các đỉnh theo thứ tự cố định từ 0 đến N-1 để tối ưu chiều đó. Trạng thái cần cả mask và đỉnh cuối cùng, nên không thể bỏ bớt chiều nào bằng kỹ thuật này. Kích thước trạng thái vẫn là O(N * 2^N).

Tuy nhiên, trong các bài toán mà việc xử lý các đối tượng (người, vật phẩm,...) diễn ra theo một thứ tự nhất định và mask theo dõi trạng thái của một tập hợp khác, kỹ thuật tối ưu không gian này cực kỳ mạnh mẽ.

Bài tập ví dụ:

Tạo số hợp lệ

Trong một chương trình truyền hình trí tuệ, MC đã đưa ra một thử thách thú vị cho FullHouse Dev. Họ được cung cấp một dãy số và phải tìm ra có bao nhiêu cách để tạo thành các số hợp lệ.

Bài toán

FullHouse Dev nhận được một mảng \(A\) gồm \(n\) số nguyên, mỗi số là một chữ số trong khoảng từ \(0\) đến \(9\). Họ cũng được cho một số nguyên \(k\). Nhiệm vụ của họ là đếm xem có bao nhiêu dãy con của mảng \(A\) tạo thành một số hợp lệ có \(k\) chữ số.

Một dãy con có độ dài \(k\) được gọi là số hợp lệ nếu số đó không có số 0 ở đầu.

Lưu ý:

• Dãy con của một mảng không nhất thiết phải liên tiếp.
• Ví dụ, nếu mảng là \([1, 0, 2]\), thì dãy con \([1, 0]\) không được coi là số hợp lệ có 2 chữ số. Một số hợp lệ có 2 chữ số trong mảng này là \([1, 2]\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(n\) - kích thước của mảng.
• Dòng thứ hai chứa \(n\) số nguyên cách nhau bởi dấu cách - các phần tử của mảng \(A\).
• Dòng thứ ba chứa số nguyên \(k\).

OUTPUT FORMAT:

• In ra số lượng số hợp lệ có \(k\) chữ số có thể tạo được, lấy phần dư khi chia cho \(10^9 + 7\).

Ràng buộc:

• \(1 \leq n \leq 100\)
• \(0 \leq A[i] \leq 9\)
• \(1 \leq k \leq n\)

Ví dụ

INPUT

5
1 1 0 1 0
3

OUTPUT

9

Giải thích

Trong ví dụ trên, các dãy con tạo thành số hợp lệ có 3 chữ số là:

• 111
• 110
• 101
• 101
• 101
• 110
• 111
• 110
• 101

Vì vậy, có tổng cộng 9 cách để tạo số hợp lệ có 3 chữ số từ mảng đã cho. Tuyệt vời! Bài toán này là một ứng dụng kinh điển của Quy hoạch động (Dynamic Programming) trên dãy con (subsequence).

Đây là hướng giải ngắn gọn bằng C++:

1. Xác định trạng thái DP: Chúng ta cần xây dựng các dãy con có độ dài k từ các chữ số của mảng A, đồng thời theo dõi xem chữ số đầu tiên của dãy con đó có phải là số 0 hay không. Điều này gợi ý một trạng thái DP bao gồm:

   • Chỉ số phần tử đang xét trong mảng A.
   • Số lượng chữ số đã chọn cho dãy con hiện tại.
   • Trạng thái về chữ số đầu tiên (đã chọn chữ số đầu tiên và nó có phải là 0 hay không).

   Ta có thể định nghĩa trạng thái dp[i][j][state] như sau:

   • i: Số lượng phần tử đã xét từ đầu mảng A (tức là các phần tử A[0] đến A[i-1]). i sẽ chạy từ 0 đến n.
   • j: Số lượng chữ số đã chọn cho dãy con hiện tại. j sẽ chạy từ 0 đến k.
   • state: Trạng thái về chữ số đầu tiên được chọn:
     • 0: Dãy con hiện tại có độ dài j chỉ bao gồm các số 0 (hoặc là dãy rỗng khi j=0). Trạng thái này đại diện cho việc chưa chọn được chữ số đầu tiên khác 0.
     • 1: Dãy con hiện tại có độ dài j bắt đầu bằng số 0 và chứa ít nhất một số khác 0 sau đó (Đây là các dãy con có số 0 ở đầu không hợp lệ cho k > 1).
     • 2: Dãy con hiện tại có độ dài j bắt đầu bằng một chữ số khác 0. (Đây là các dãy con hợp lệ).

2. Công thức truy hồi (Transitions): Khi xét đến phần tử A[i-1] (với i từ 1 đến n), tại trạng thái dp[i-1][j][state] (đã xử lý i-1 phần tử, chọn được j chữ số, ở trạng thái state):

   • Không chọn A[i-1]: Số cách vẫn giữ nguyên như khi chỉ xét i-1 phần tử. Ta cộng dp[i-1][j][0] vào dp[i][j][0], dp[i-1][j][1] vào dp[i][j][1], và dp[i-1][j][2] vào dp[i][j][2].
   • Chọn A[i-1] (giả sử giá trị là val): Chỉ thực hiện khi số chữ số đã chọn j < k. Khi chọn, số chữ số mới sẽ là j+1. Ta xét val và trạng thái cũ state (dp[i-1][j][state]) để chuyển sang trạng thái mới state':
     • Nếu val == 0:
       • Nếu trạng thái cũ là 0 (dãy rỗng hoặc chỉ gồm số 0): Chọn 0 vẫn duy trì trạng thái 0 (chỉ gồm số 0). Cộng dp[i-1][j][0] vào dp[i][j+1][0].
       • Nếu trạng thái cũ là 1 (bắt đầu 0, có số khác 0): Chọn 0 vẫn duy trì trạng thái 1. Cộng dp[i-1][j][1] vào dp[i][j+1][1].
       • Nếu trạng thái cũ là 2 (bắt đầu khác 0): Chọn 0 vẫn duy trì trạng thái 2. Cộng dp[i-1][j][2] vào dp[i][j+1][2].
     • Nếu val != 0:
       • Nếu trạng thái cũ là 0 (dãy rỗng hoặc chỉ gồm số 0): Chọn số khác 0 làm cho dãy con mới bắt đầu bằng số khác 0. Chuyển sang trạng thái 2. Cộng dp[i-1][j][0] vào dp[i][j+1][2].
       • Nếu trạng thái cũ là 1 (bắt đầu 0, có số khác 0): Chọn số khác 0 vẫn duy trì trạng thái 1. Cộng dp[i-1][j][1] vào dp[i][j+1][1].
       • Nếu trạng thái cũ là 2 (bắt đầu khác 0): Chọn số khác 0 vẫn duy trì trạng thái 2. Cộng dp[i-1][j][2] vào dp[i][j+1][2].

   Lưu ý cần cẩn thận với chỉ số j và j+1. Khi xét dp[i][j][state], ta đang tính số cách kết thúc ở đây sau khi xử lý A[i-1] và có độ dài j. Do đó, khi chọn A[i-1] để có độ dài j, nó phải được nối vào một dãy con có độ dài j-1 từ A[0] đến A[i-2].

   Sử dụng dp[i][j][state] là số cách chọn j phần tử từ A[0...i-1]:

   • dp[i][j][0]: len j, chỉ gồm số 0.
   • dp[i][j][1]: len j, bắt đầu 0, có chứa số khác 0.
   • dp[i][j][2]: len j, bắt đầu khác 0.

   Khởi tạo: dp[0][0][0] = 1 (dãy rỗng, độ dài 0, chỉ gồm số 0 - trạng thái ban đầu trước khi chọn bất kỳ số nào). Tất cả các dp[0][j][state] khác đều bằng 0.

   Truy hồi (với i từ 1 đến n, j từ 0 đến k):

   • val = A[i-1]
   • // Case 1: Không chọn A[i-1]
   • dp[i][j][0] = dp[i-1][j][0]
   • dp[i][j][1] = dp[i-1][j][1]
   • dp[i][j][2] = dp[i-1][j][2]
   • // Case 2: Chọn A[i-1] (chỉ khi j > 0)
   • Nếu j > 0:
     • prev_j = j - 1
     • Nếu val == 0:
       • Nối vào dãy 'chỉ gồm 0' (len prev_j): Vẫn là dãy 'chỉ gồm 0' (len j). Cộng dp[i-1][prev_j][0] vào dp[i][j][0].
       • Nối vào dãy 'bắt đầu 0, mixed' (len prev_j): Vẫn là dãy 'bắt đầu 0, mixed' (len j). Cộng dp[i-1][prev_j][1] vào dp[i][j][1].
       • Nối vào dãy 'bắt đầu khác 0' (len prev_j): Vẫn là dãy 'bắt đầu khác 0' (len j). Cộng dp[i-1][prev_j][2] vào dp[i][j][2].
     • Nếu val != 0:
       • Nối vào dãy 'chỉ gồm 0' (len prev_j): Trở thành dãy 'bắt đầu khác 0' (len j). Cộng dp[i-1][prev_j][0] vào dp[i][j][2].
       • Nối vào dãy 'bắt đầu 0, mixed' (len prev_j): Vẫn là dãy 'bắt đầu 0, mixed' (len j). Cộng dp[i-1][prev_j][1] vào dp[i][j][1].
       • Nối vào dãy 'bắt đầu khác 0' (len prev_j): Vẫn là dãy 'bắt đầu khác 0' (len j). Cộng dp[i-1][prev_j][2] vào dp[i][j][2].
   • Nhớ lấy phần dư cho 10^9 + 7 sau mỗi phép cộng.

3. Kết quả: Số lượng số hợp lệ có k chữ số chính là tổng số dãy con độ dài k bắt đầu bằng chữ số khác 0. Kết quả là dp[n][k][2].

4. Kích thước mảng DP: dp[n+1][k+1][3]. Với n, k <= 100, kích thước này là hoàn toàn khả thi.

Tóm tắt các bước trong code:

1. Đọc n.
2. Đọc mảng A.
3. Đọc k.
4. Định nghĩa hằng số MOD = 10^9 + 7.
5. Khai báo mảng dp[101][101][3] và khởi tạo tất cả phần tử bằng 0.
6. Đặt dp[0][0][0] = 1.
7. Dùng 3 vòng lặp lồng nhau để tính DP: i từ 1 đến n, j từ 0 đến k, val = A[i-1]. Áp dụng các công thức truy hồi đã nêu, nhớ điều kiện j > 0 khi chọn phần tử và điều kiện về val.
8. In ra dp[n][k][2].

Làm thêm nhiều bài tập miễn phí tại đây