Khi giải các bài toán về Quy hoạch động (QHĐ), chúng ta đã làm quen với các trạng thái là vị trí hoặc giá trị. Ví dụ, trong bài toán Knapsack, chúng ta đã gọi là giá trị lớn nhất thu được khi đến vị trí thứ , thu được khối lượng là .
Với việc sử dụng biểu diễn nhị phân (bitmask), chúng ta hoàn toàn có thể sử dụng phương pháp QHĐ với trạng thái là các tập hợp.
Để đọ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ề:
Đầu tiên, ta nhắc lại đôi chút về các phép toán bit.
Như chúng ta đã biết, mọi số nguyên trong hệ thập phân đều có thể biểu diễn được dưới dạng nhị phân. Với các số nhị phân này, ta có thêm một số phép toán bên cạnh các phép toán thông thường như AND (& trong C++), OR (| trong C++), XOR (^ trong C++), dịch trái (<< trong C++), dịch phải (>> trong C++), … Khi sử dụng C++, ngôn ngữ này hỗ trợ chúng ta thêm một số hàm liên quan đến dãy bit như __builtin_popcount() (đếm số bit ), __builtin_ctz() (đếm số bit ở tận cùng bên phải), ...
Sử dụng các phép toán trên, chúng ta có thể dễ dàng thực hiện các thao tác:
(mask >> i) & 1mask ^= (1 << i)Có thể thấy các thao tác này có những điểm tương đồng với việc thao tác trên các tập hợp: kiểm tra một phần tử có nằm trong tập hợp hay không, thêm/bớt một phần tử trong tập hợp, đếm số phần tử của tập hợp. Điều đó cho ta ý tưởng về việc dùng biểu diễn nhị phân để biểu diễn các tập hợp con của một tập hợp.
Ta có thể biểu diễn một tập con của một tập hợp bằng một xâu nhị phân, trong đó bit thứ bằng / khi phần tử thứ không/có nằm trong tập hợp. Xâu nhị phân này được gọi là bitmask.
Giả sử có một tập hợp . Xét một tập con . của . Khi đó ta có thể biểu diễn bằng một xâu nhị phân độ dài , với bit thứ (ở đây là bit có giá trị cao thứ hay bit thứ từ phải sang) bằng nếu nằm trong tập :
với các vị trí bằng là .
Do là một xâu nhị phân, ta có thể biểu diễn nó bằng một số ở dạng thập phân. Ví dụ:
biểu diễn tập con của
biểu diễn tập con của
biểu diễn tập con của
Khi duyệt tất cả các số từ đến , ta sẽ duyệt qua mọi xâu nhị phân độ dài , và cũng là duyệt qua tất cả các tập con của . Công việc duyệt này có độ phức tạp thời gian là .
Bạn đọc có thể làm thử bài này để hiểu rõ hơn về biểu diễn tập hợp bằng bitmask.
Đề bài: Codeforces - 100589G
Cho hai số nguyên dương và số tự nhiên (). Một hoán vị của dãy là một cách sắp xếp lại dãy sao cho mọi phần tử của dãy đều xuấ hiện chính xác một lần. Đếm số hoán vị độ dài của dãy mà trong hoán vị đó, hai phần tử liên tiếp chênh lệch nhau không quá .
Ví dụ, với , là một hoán vị thoả mãn, còn là một hoán vị không thoả mãn do .
Cách làm tự nhiên nhất đối với bài toán trên là sinh ra mọi hoán vị có thể của dãy (tạm gọi là dãy ) bằng cách sử dụng thuật toán quay lui. Độ phức tạp thời gian là ; với thì ta không thể sử dụng cách này.
Ta thử áp dụng tư tưởng quy hoạch động. Nếu xét theo vị trí, ta thấy phần tử ở vị trí phải sai khác phần tử ở của một khoảng không quá . Cách này đưa ta tới cách gọi là số lượng dãy hoán vị sao cho phần tử thứ là và dễ dàng biểu diễn nó theo . Tuy nhiên, cách gọi này không đảm bảo được tính chất quan trọng của hoán vị: tất cả các phần tử trong dãy ban đầu phải xuất hiện chính xác một lần.
Để có được tính chất này, thay vì chỉ dùng vị trí, ta dùng hẳn một tập hợp để lưu lại tất cả các vị trí đã được thêm vào dãy trước đó. Gọi là số lượng dãy là hoán vị của và có phần tử cuối cùng được thêm vào là . Khi thêm một phần tử vào , ta cần chắc chắn rằng , và . Như vậy:
.
Với trường hợp cơ sở, ta có thể chọn . Dĩ nhiên, ta không thể biểu diễn trong mảng khi cài đặt được; trong trường hợp này ta có thể thay thế nó bằng và chấp nhận mọi trường hợp thêm vào nếu xuất hiện . Kết quả của bài toán là tổng số dãy được tạo ra từ dãy ban đầu với đầy đủ phần tử ở mọi trường hợp phần tử cuối cùng, tức .
Còn để biểu diễn tập hợp khi cài đặt, ta sử dụng bitmask như đã nói ở trên.
mask.mask = (1 << N) - 1((mask >> q) & 1) != 1 (tức là bit thứ của mask khác )mask | (1 << q).mask.Trong bài toán này, hoán vị phải được tạo thành bởi các số từ đến . Nếu sử dụng cách biểu diễn trên, bit ở vị trí thứ không biểu diễn cái gì cả, hơn nữa phải dùng bit mới biểu diễn hết được số này. Vì vậy, thay vì dùng bit thứ để biểu diễn việc có thuộc hay không, ta dùng bit thứ . Bằng cách này, ta chỉ cần đúng bit để biểu diễn tập hợp mà không lãng phí bit nào.
const int MAXN = (1 << 15) + 1;
int n, k;
long long dp[MAXN][16];
//Lấy bit thứ k của số x
int getBit(int x, int k)
{
return (x >> k) & 1;
}
int solve(int n, int k)
{
for (int mask = 0; mask < (1 << n); mask++)
for (int k = 0; k <= n; k++)
dp[mask][k] = 0;
//base case
dp[0][0] = 1;
for (int mask = 0; mask < (1 << n); mask++)
for (int q = 1; q <= n; q++)
{
//check q nằm trong tập hợp (biểu diễn bằng mask)
if (getBit(mask, q - 1)) continue;
for (int p = 0; p <= n; p++)
{
//check chênh lệch của q và p
if (p != 0 && abs(q - p) > k) continue;
//thêm q vào tập hợp
int newMask = mask | (1 << (q - 1));
dp[newMask][q] += dp[mask][p];
}
}
long long res = 0;
int fullMask = (1 << n) - 1;
for (int k = 1; k <= n; k++)
res += dp[fullMask][k];
return res;
}
Độ phức tạp về thời gian của cách cài đặt trên là , còn độ phức tạp về không gian là .
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