Tổng Quan Về Bitmask Dynamic Programming

Động lực học nén trạng thái (State Compression DP) là phương pháp hiệu quả cho các bài toán tối ưu hóa khi số lượng phần tử cần xem xét tương đối nhỏ (thường dưới 20). Kỹ thuật này sử dụng một số nguyên duy nhất để biểu diễn tập hợp các trạng thái thông qua hệ nhị phân. Mỗi bit tương ứng với việc lựa chọn hay không lựa chọn một phần tử cụ thể.

Bước chuyển tiếp từ trạng thái cũ sang mới được thực hiện chủ yếu dựa trên các phép toán bitwise như AND, OR, XOR và shift. Do độ phức tạp thời gian thường đạt mức $O(n \cdot 2^n)$, thuật toán này phù hợp để xử lý các vấn đề thuộc lớp NP-khó trong giới hạn dữ liệu chặt chẽ. Khi áp dụng, cần kiểm tra tính chất đệ quy và đảm bảo không tồn tại chu trình ngược dòng ảnh hưởng đến kết quả cuối cùng.

Ví Dụ 1: Phân Loại Nhóm Vật Phẩm Giới Hạn Dung Lượng

Bài toán yêu cầu sắp xếp $n$ vật phẩm vào các nhóm sao cho tổng trọng lượng mỗi nhóm không vượt quá giới hạn $W$, mục tiêu là tìm số lượng nhóm ít nhất.

Lời Giải Thuật Toán

Vấn đề này mang tính chất chia tổ hợp, tương tự bài toán cái túi nhưng mở rộng cho nhiều thùng chứa. Vì các quyết định trước sẽ ảnh hưởng đến khả năng xếp đặt sau, ta cần lưu trữ trạng thái đã chọn của tất cả vật phẩm. Hàm DP được xây dựng dựa trên số nhóm hiện tại và trạng thái bitmask đã bao phủ.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 20;
const int INF_VAL = 0x3f3f3f3f;
int weights[MAX_N];
int limit_capacity;
int n_val;
int dp[MAX_N][1 << MAX_N]; // dp[số_nhóm][trạng_thái_bitmask]

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n_val >> limit_capacity;
    int total_states = 1 << n_val;

    // Khởi tạo giá trị vô cùng lớn
    memset(dp, 0x3f, sizeof(dp));

    // Khởi tạo trường hợp chỉ có 1 nhóm chứa từng vật phẩm riêng lẻ
    for (int i = 0; i < n_val; ++i) {
        weights[i]; 
    }
    for (int i = 0; i < n_val; ++i) {
        dp[1][1 << i] = weights[i];
    }

    // Duyệt số nhóm từ 1 đến n
    for (int groups = 1; groups <= n_val; ++groups) {
        // Duyệt qua tất cả trạng thái bitmask
        for (int mask = 0; mask < total_states; ++mask) {
            if (dp[groups][mask] == INF_VAL) continue;

            // Thử thêm vật phẩm chưa được chọn vào nhóm hiện tại hoặc bắt đầu nhóm mới
            for (int next_item = 0; next_item < n_val; ++next_item) {
                if (!((mask >> next_item) & 1)) { // Nếu vật phẩm chưa ở trong trạng thái
                    if (dp[groups][mask] + weights[next_item] <= limit_capacity) {
                        dp[groups][mask | (1 << next_item)] = min(
                            dp[groups][mask | (1 << next_item)], 
                            dp[groups][mask] + weights[next_item]
                        );
                    } else {
                        dp[groups + 1][mask | (1 << next_item)] = min(
                            dp[groups + 1][mask | (1 << next_item)], 
                            weights[next_item]
                        );
                    }
                }
            }
        }
    }

    // Tìm đáp án nhỏ nhất
    for (int g = 1; g <= n_val; ++g) {
        if (dp[g][total_states - 1] != INF_VAL) {
            cout << g << endl;
            return 0;
        }
    }

    return 0;
}

Ví Dụ 2: Tối Thiểu化 Quãng Đường Di Chuyển Đến Mọi Điểm

Khi phải truy cập tất cả các điểm tọa độ trên mặt phẳng bắt đầu từ gốc $(0,0)$, đây là bài toán dạng TSP (Traveling Salesman Problem) đơn giản hóa.

Lựa Chọn Cấu Trúc Dữ Liệu

Trạng thái cần lưu bao gồm tập hợp các điểm đã thăm và điểm vừa thăm gần nhất để tính khoảng cách bước tiếp theo. Ma trận khoảng cách giữa các cặp điểm được tính toán trước để tăng tốc độ truy cập.

#include <cmath>
#include <iostream>
using namespace std;

const double MAX_DIST = 1e8;
double dist_mat[20][20];
double x_pos[20], y_pos[20];
int num_points;
double memo[1 << 20][20]; // [trạng_thái_bitmask][điểm_kết_thúc_nửa]

int main() {
    scanf("%d", &num_points);
    
    // Khởi tạo ma trận nhớ
    for(int s=0; s<(1<<num_points); ++s){
        for(int p=0; p<num_points; ++p){
            memo[s][p] = MAX_DIST;
        }
    }

    for (int i = 0; i < num_points; ++i) {
        scanf("%lf %lf", &x_pos[i], &y_pos[i]);
        // Khoảng cách từ gốc đến điểm thứ i
        double d = sqrt(x_pos[i]*x_pos[i] + y_pos[i]*y_pos[i]);
        memo[1 << i][i] = d;
    }

    // Tính sẵn khoảng cách giữa mọi cặp điểm
    for (int i = 0; i < num_points; ++i) {
        for (int j = 0; j < num_points; ++j) {
            double dx = x_pos[j] - x_pos[i];
            double dy = y_pos[j] - y_pos[i];
            dist_mat[i][j] = sqrt(dx*dx + dy*dy);
        }
    }

    // Duyệt theo thứ tự bitmask tăng dần
    for (int s = 1; s < (1 << num_points); ++s) {
        for (int curr = 0; curr < num_points; ++curr) {
            if ((s >> curr) & 1) { // Đương nhiên điểm curr phải nằm trong trạng thái s
                int prev_s = s ^ (1 << curr); // Trạng thái chưa bao gồm điểm curr
                if (prev_s == 0) continue;

                for (int prev = 0; prev < num_points; ++prev) {
                    if ((prev_s >> prev) & 1) {
                        memo[s][curr] = min(memo[s][curr], memo[prev_s][prev] + dist_mat[prev][curr]);
                    }
                }
            }
        }
    }

    double result = MAX_DIST;
    for (int i = 0; i < num_points; ++i) {
        result = min(result, memo[(1 << num_points) - 1][i]);
    }
    printf("%.2f\n", result);

    return 0;
}

Ví Dụ 3: Tính Giá Trị Tối Đa Với Phần Thưởng Theo Thứ Tự

Chọn ra tối đa $m$ món ăn trong $n$ món có sẵn. Một số món ăn sẽ mang lại lợi ích bổ sung nếu được chọn ngay sau một món khác nhất định.

Cấu Hình Logic

Sử dụng mảng hai chiều $DP[mask][last\_item]$ để lưu giá trị cao nhất đạt được. Vòng lặp chính sẽ duyệt qua từng trạng thái bitmask. Khi chuyển sang trạng thái mới bằng cách thêm một món chưa chọn, ta cần cộng thêm lợi ích cơ bản và lợi ích bonus nếu trùng khớp với điều kiện tiền đề.

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int LIMIT_STATE = 1 << 18;
const int MAX_ITEM = 20;

ll value_bonus[MAX_ITEM][MAX_ITEM];
int base_value[MAX_ITEM];
ll dp[LIMIT_STATE][MAX_ITEM];
int n_q, m_q, k_q;

int count_bits(int mask) {
    int c = 0;
    for(int i=0; i<n_q; ++i) {
        if((mask >> i) & 1) c++;
    }
    return c;
}

int main() {
    cin >> n_q >> m_q >> k_q;
    memset(value_bonus, 0, sizeof(value_bonus));
    memset(dp, 0, sizeof(dp)); // Mặc định khởi tạo 0 hoặc âm tùy case, ở đây max nên 0 đủ

    for (int i = 1; i <= n_q; ++i) {
        cin >> base_value[i];
        dp[1 << (i-1)][i] = base_value[i];
    }

    for (int i = 0; i < k_q; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        value_bonus[u][v] = c; // u rồi thì tới v
    }

    ll global_max = 0;

    for (int mask = 1; mask < (1 << n_q); ++mask) {
        int cnt = count_bits(mask);
        if (cnt > m_q) continue;

        for (int j = 1; j <= n_q; ++j) {
            // Cập nhật kết quả nếu đúng số lượng món
            if ((mask >> (j-1)) & 1 && cnt == m_q) {
                global_max = max(global_max, dp[mask][j]);
            }

            for (int nxt = 1; nxt <= n_q; ++nxt) {
                // Chỉ thêm món nếu chưa có trong mask
                if (!((mask >> (nxt-1)) & 1)) {
                    int new_mask = mask | (1 << (nxt-1));
                    // Try transition from all previously visited 'l'
                    for (int l = 1; l <= n_q; ++l) {
                        if ((mask >> (l-1)) & 1) {
                            ll gain = base_value[nxt] + value_bonus[l][nxt];
                            if (dp[new_mask][nxt] < dp[mask][l] + gain) {
                                dp[new_mask][nxt] = dp[mask][l] + gain;
                            }
                        }
                    }
                }
            }
        }
    }

    cout << global_max << endl;
    return 0;
}

Ví Dụ 4: Sắp Xếp Quân Vua Không Giao Thấm Lẫn

Trên bàn cờ kích thước $N \times N$, đặt $K$ quân sao cho chúng không công kích lẫn nhau. Một quân tấn công xung quanh 8 hướng. Đây là bài toán đếm phương án.

Xử Lý Hàng Đơn Giản Hóa

Một hàng được coi là hợp lệ nếu không có hai quân nào kề nhau theo chiều ngang. Hai hàng liên tiếp phải không vi phạm điều kiện va chạm dọc và chéo. Sử dụng DFS để tiền xử lý danh sách trạng thái hàng hợp lệ và đếm số quân.

#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

int n_size, k_total;
long long dp[25][1000][25]; // [hàng hiện tại][trạng thái hàng][số quân đã đặt]
vector<int> valid_rows;
vector<int> row_counts;

// Sinh ra các cấu hình hàng hợp lệ
void generate_masks(int current_mask, int current_cnt, int col_idx) {
    if (col_idx == n_size) {
        valid_rows.push_back(current_mask);
        row_counts.push_back(current_cnt);
        return;
    }
    generate_masks(current_mask, current_cnt, col_idx + 1);
    
    if (current_cnt + 1 <= k_total) { // Pruning cơ bản
       // Kiểm tra không kề nhau trong hàng này
       if (!(current_mask & (1 << col_idx))) {
           generate_masks(current_mask | (1 << col_idx), current_cnt + 1, col_idx + 2);
       }
    }
}

bool check_compat(int row_a, int row_b) {
    // Cùng cột
    if ((row_a & row_b) != 0) return false;
    // Chéo trái
    if ((row_a & (row_b << 1)) != 0) return false;
    // Chéo phải
    if ((row_a & (row_b >> 1)) != 0) return false;
    return true;
}

int main() {
    cin >> n_size >> k_total;
    
    generate_masks(0, 0, 0);
    
    int sz = valid_rows.size();
    memset(dp, 0, sizeof(dp));
    
    // Trường hợp hàng đầu tiên
    for (int i = 0; i < sz; ++i) {
        if (row_counts[i] <= k_total) {
            dp[1][i][row_counts[i]] = 1;
        }
    }

    for (int r = 2; r <= n_size; ++r) {
        for (int curr = 0; curr < sz; ++curr) {
            for (int prev = 0; prev < sz; ++prev) {
                if (check_compat(valid_rows[curr], valid_rows[prev])) {
                    for (int count_used = row_counts[curr]; count_used <= k_total; ++count_used) {
                        if (dp[r-1][prev][count_used] == 0) continue;
                        if (count_used + row_counts[curr] <= k_total) {
                            dp[r][curr][count_used + row_counts[curr]] += dp[r-1][prev][count_used];
                        }
                    }
                }
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < sz; ++i) {
        ans += dp[n_size][i][k_total];
    }
    cout << ans << endl;

    return 0;
}

Ví Dụ 5: Đếm Số Cách Lấp Lưới Bằng Domino

Lót một bàn cờ $N \times M$ bằng các viên gạch $1 \times 2$. Có thể tính số cách lát kín bàn cờ này.

Góc Nhìn Từ Hàng

Thay vì đếm vị trí gạch, ta quan sát đường viền tiếp giáp giữa hai hàng. Nếu một ô ở hàng trên không bị gạch đứng lấp đầy, nó buộc phải được nối dài xuống hàng dưới. Điều này đồng nghĩa với việc ta chỉ cần xác định vị trí các gạch nằm ngang.

#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;
const int MAX_DIM = 12;
const int MAX_STATE = 1 << MAX_DIM;
bool is_ok_mask[MAX_STATE];
vector<int> transitions[MAX_STATE];
ll dp_grid[MAX_DIM][MAX_STATE];
int R_dim, C_dim;

// Kiểm tra xem một hàng có chứa số chẵn ô trống liên tiếp (có thể lắp gạch đứng)
bool isValidRow(int mask) {
    int gap = 0;
    for (int j = 0; j < C_dim; ++j) {
        if ((mask >> j) & 1) {
            if (gap % 2 != 0) return false;
            gap = 0;
        } else {
            gap++;
        }
    }
    return gap % 2 == 0;
}

int main() {
    while (cin >> R_dim >> C_dim, R_dim || C_dim) {
        int total_states = 1 << C_dim;
        
        // Tiền xử lý hàng hợp lệ
        for(int s=0; s<total_states; ++s) {
            is_ok_mask[s] = isValidRow(s);
        }
        
        // Xây dựng đồ thị chuyển tiếp hợp lệ
        for (int i = 0; i < total_states; ++i) {
            transitions[i].clear();
            for (int j = 0; j < total_states; ++j) {
                // Hai hàng không chồng lên nhau về chỗ trống
                // Và khi gộp lại phải hợp lệ
                if (!is_ok_mask[i] || !is_ok_mask[j]) continue;
                
                int combined = i | j;
                // Kiểm tra xem khi ghép lại có tồn tại chuỗi ô trống lẻ không
                // Thực tế i và j đại diện cho vị trí gạch đứng nhô ra
                // Nếu i&j == 0 thì không chồng lên nhau
                if ((i & j) == 0 && is_ok_mask[combined]) {
                   transitions[i].push_back(j); 
                }
            }
        }

        memset(dp_grid, 0, sizeof(dp_grid));
        dp_grid[0][0] = 1; // Bàn cờ 0 hàng, trạng thái 0 có 1 cách (trống)

        for (int r = 1; r <= R_dim; ++r) {
            for (int curr = 0; curr < total_states; ++curr) {
                for (int prev : transitions[curr]) {
                     dp_grid[r][curr] += dp_grid[r-1][prev];
                }
            }
        }
        
        cout << dp_grid[R_dim][0] << endl;
    }
    return 0;
}