Quy hoạch động Bitmask Phần 1

Nguời viết:

Nguyễn Hải Nam

Reviewer:

Đỗ Thị Hồng Ngát, Trần Gia Khánh

Giới thiệu

Quy hoạch động bitmask là một phương pháp mạnh mẽ trong lập trình, đặc biệt phù hợp cho các bài toán liên quan đến tập hợp và lựa chọn. Kỹ thuật này sử dụng biểu diễn nhị phân để đại diện cho các tập hợp, trong đó mỗi bit trong một số nguyên tương ứng với sự hiện diện hoặc vắng mặt của một phần tử. Điều này không chỉ giúp tiết kiệm bộ nhớ mà còn đơn giản hóa việc xử lý trạng thái. Quy hoạch động bitmask thường được áp dụng trong các bài toán như tìm kiếm tập con, bài toán Knapsack,, và các vấn đề trong đồ thị. Nhờ vào khả năng xử lý nhanh chóng và tính hiệu quả cao, phương pháp này đã trở thành công cụ đắc lực cho lập trình viên trong việc giải quyết các bài toán tối ưu hóa phức tạp.

Mục lục

Kiến thức cần biết

Để đọc hiểu bài viết sau một cách hiệu quả, bạn đọc nên có sẵn các kiến thức về:

Các phép toán trên bit

Đầu tiên, ta nhắc lại đôi chút về các phép toán bit.

Các thao tác xử lý bit cơ bản là những kỹ thuật quan trọng trong lập trình, giúp thao tác trực tiếp với các bit trong dữ liệu. Dưới đây là một số thao tác phổ biến:

Phép AND (&): Được sử dụng để kiểm tra các bit tương ứng. Kết quả chỉ có bit 1 khi cả hai bit đều là 1. Ví dụ, 5 & 3 (0101 & 0011) sẽ cho kết quả là 1 (0001).
Phép OR (|): Kết hợp các bit, cho kết quả là 1 nếu ít nhất một trong hai bit là 1. Ví dụ, 5 | 3 (0101 | 0011) sẽ cho kết quả là 7 (0111).
Phép XOR (^): Cho kết quả là 1 khi các bit khác nhau. Ví dụ, 5 ^ 3 (0101 ^ 0011) sẽ cho kết quả là 6 (0110).
Phép NOT (~): Đảo ngược tất cả các bit, biến 0 thành 1 và ngược lại. Ví dụ, ~5 (đối với số nguyên 32 bit) sẽ cho kết quả là -6.
Dịch trái (<<): Dịch tất cả các bit sang trái một số vị trí nhất định, thêm 0 vào bên phải. Ví dụ, 5 << 1 sẽ cho kết quả là 10 (1010).
Dịch phải (>>): Dịch các bit sang phải, có thể giữ nguyên dấu tùy thuộc vào kiểu dữ liệu. Ví dụ, 5 >> 1 sẽ cho kết quả là 2 (0010).

Các thao tác này cho phép lập trình viên thực hiện nhiều phép toán phức tạp một cách hiệu quả, đặc biệt trong các bài toán liên quan đến quy hoạch động bitmask và xử lý dữ liệu nhị phân.

Biểu diễn các tập hợp bằng bitmask

Biểu diễn tập hợp bằng bitmask là một kỹ thuật mạnh mẽ trong lập trình, cho phép chúng ta đại diện các tập hợp bằng cách sử dụng các bit trong một số nguyên. Kỹ thuật này rất hữu ích khi làm việc với các bài toán có số lượng phần tử nhỏ, thường từ 20 đến 30. Mỗi bit trong một số nguyên sẽ tương ứng với một phần tử trong tập hợp.

Ví dụ, giả sử chúng ta có một tập hợp gồm 5 phần tử: ${0,1,2,3,4}$. Ta có thể sử dụng một số nguyên 5 bit (từ 0 đến 31) để biểu diễn trạng thái của tập hợp. Một tập hợp con như ${1,3}$ có thể được biểu diễn bằng số nguyên 1010 trong hệ nhị phân. Ở đây, bit thứ 1 và thứ 3 được đặt là 1, trong khi các bit còn lại là 0.

Việc thực hiện các phép toán trên tập hợp bằng bitmask rất đơn giản và nhanh chóng. Các phép toán bitwise như $AND$, $OR$, và $XOR$ có thể được sử dụng để thực hiện các phép toán hợp, giao, và hiệu của các tập hợp.

Ví dụ cụ thể:

Hợp (OR):
- Giả sử ta có hai tập hợp: $A$ = {1, 3} (biểu diễn bằng bitmask 1010) và $B$ = {2, 3} (biểu diễn bằng bitmask 0110).
- Phép hợp $(A$ $OR$ $B)$ sẽ cho kết quả 1110, tương ứng với tập hợp {1, 2, 3}.
Giao (AND):
- Với hai tập hợp $A $ và $B$ như trên, phép giao $(A$ $AND$ $B)$ sẽ cho kết quả 0010, tương ứng với tập hợp {3}.
Hiệu (XOR):
- Phép hiệu $(A$ $XOR$ $B)$ sẽ cho kết quả 1100, tương ứng với tập hợp {1, 2}.

Ngoài ra, việc kiểm tra sự tồn tại của một phần tử trong tập hợp hoặc thêm/bỏ phần tử cũng trở nên đơn giản. Ví dụ, để kiểm tra xem phần tử 2 có trong tập hợp hay không, ta chỉ cần sử dụng phép $AND$ với bitmask của phần tử $2$ (0001 0000) và bitmask hiện tại. Nếu kết quả khác 0, phần tử đó có mặt trong tập hợp.

Kỹ thuật biểu diễn tập hợp bằng bitmask không chỉ giúp tiết kiệm bộ nhớ mà còn cải thiện hiệu suất của các thuật toán. Điều này đặc biệt có giá trị trong các bài toán tối ưu hóa phức tạp, nơi tốc độ và hiệu quả là rất quan trọng.

Phương pháp QHĐ Bitmask

Bài toán

Đề bài: Spoj- ASSIGN

Một lớp học có $n$ học sinh, cô giáo phân công cho học sinh trong lớp nghiên cứu $n$ chủ đề học tập. Mỗi học sinh có sở thích học tập khác nhau, và không có học sinh nào muốn mình phải học một chủ đề không yêu thích.

Yêu cầu: Đếm số cách phân chia $n$ chủ đề học tập cho $n$học sinh (mỗi học sinh một chủ đề), sao cho mỗi học sinh đều được học đúng chủ đề mình yêu thích?

Phân tích

Ở bài toán này, mục tiêu cần đi tìm số cách phân chia $n$ chủ đề hợp lí cho $n$ học sinh. Vậy các trạng thái nhỏ hơn sẽ là số cách phân chia $i$ chủ đề hợp lý cho $i$học sinh $(0<i<n+1)$

Ta đánh số các học sinh và các chủ đề từ $0$ tới $n-1$.

Sử dụng bitmask, ta sẽ biểu diễn việc một học sinh thứ $(-1<i<n)$ đã được phân chia chủ đề yêu thích của mình hay chưa. Gọi $mask$ là trạng thái thể hiện học sinh thứ $i$đã được phân chia chủ đề hay chưa,$mask[i]=0$ tương ứng với chưa và $mask[i]=1$ tương ứng với đã phân chia rồi. Ta sẽ lần lượt tìm cách phân chia cho từng chủ đề, vậy gọi $k(-1<k<n)$ là chỉ số của chủ đề đang được phân chia. Như vậy bảng phương án sẽ có dạng $dp[mask][k]$.

Ban đầu, coi như chưa có học sinh nào được phân chia chủ đề, tức là $mask=0$ và mọi $dp[mask[k]=-1$ Xét chủ đề thứ $k$ ta cần tìm một học sinh $i$ sao cho $a_{i,k}$ và bit thứ $i$ của $mask$ đang tắt, khi đó ta có thể phân chia chủ đề $k$ này cho học sinh thứ $i$ rồi tiếp tục chuyển qua chủ đề thứ $k+1$ và tìm học sinh để phân chia như đã làm ở bước trước. Nếu như có thể tiến tới $k=n$ tức là đã phân chia được hết $n$ chủ đề cho $n$ học sinh, thì ta sẽ có $dp[mask][k]$ được cộng thêm $1$. Như vậy, ta có công thức truy hồi: $dp[mask][k]=dp[new_mask][k+1]$.

Cài đặt

const int MAXN = (1 << 15) + 1;

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 20;
int dp[1 << maxn], a[maxn][maxn];

int calc(int n, int mask)
{
    int k = __builtin_popcount(mask);
    if (k == n)
        return 1;

    if (dp[mask] != -1)
        return dp[mask];

    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (a[i][k] && !(mask & (1 << i)))
            ans += calc(n, mask | (1 << i)); return dp[mask] = ans; } main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) cin >> a[i][j];

        // Xuất phát từ trạng thái 0 - chưa có học sinh nào được phân chia chủ đề.
        memset(dp, -1, sizeof(dp));
        calc(n, 0);

        // Kết quả sẽ nằm ở dp[0] do cách thực hiện đệ quy có nhớ.
        cout << dp[0] << '\n';
    }

    return 0;
}

Độ phức tạp về thời gian của cách cài đặt trên là $O (2^^{n} \times n)$ .

Chú ý thêm

Ta thấy rằng nếu lớn, thuật toán cũng sẽ mất rất nhiều thời gian để chạy. Vì vậy, để thực hiện được phương pháp này thì cần phải đủ nhỏ, thường là nếu thuật toán chỉ yêu cầu ta phải duyệt qua các tập hợp.

Việc sử dụng biểu diễn bitmask của tập hợp và QHĐ bitmask giúp chúng ta kiểm tra được mọi tập hợp con của một tập hợp lớn hơn. Do vậy, trong nhiều trường hợp, đây là phương pháp đơn giản và đáng để thử khi muốn kiếm điểm một cách hiệu quả từ các subtask bé, cũng như có một code chắc chắn để làm tiếp với các subtask lớn hơn