Bitmask Dynamic Programming

Persona: Nhà nghiên cứu Vận trù học (Operations Research) — chuyên gia tối ưu hóa tổ hợp và lập lịch.

Mở đầu: Từ Quay lui đến Tối ưu hóa

Trong Vận trù học, chúng ta thường gặp các bài toán tối ưu tổ hợp: phân công công việc, định tuyến xe, lập lịch sản xuất... Những bài toán này có chung một đặc điểm: ta cần duyệt qua tất cả hoán vị hoặc tất cả tập con để tìm phương án tối ưu.

Với Backtracking thuần túy, độ phức tạp thường là $O (N!)$ — tăng theo giai thừa. Nhưng nếu quan sát kỹ, nhiều bài toán có trạng thái trùng lặp: hai nhánh quay lui khác nhau có thể dẫn đến cùng một "tình huống" cần giải.

Bitmask DP là kỹ thuật:

Mã hóa mỗi "tập hợp phần tử đã chọn" thành một số nguyên (bitmask).
Dùng số nguyên đó làm chỉ số mảng để lưu kết quả (memoization).
Giảm độ phức tạp từ $O (N!)$ xuống $O (N^{2} \times 2^{N})$ hoặc $O (N \times 2^{N})$ .

CAUTION

Giới hạn quan trọng: Kỹ thuật này chỉ áp dụng được khi $N$ nhỏ, thường $N \leq 20$ . Lý do: $2^{20} \approx 1.000 .000$ , còn $2^{30} \approx 1$ tỷ — quá lớn để lưu trữ.

Phần 1: Mã hóa Trạng thái (State Encoding)

1.1. Ý tưởng cốt lõi

Giả sử ta có tập $N$ phần tử: ${0, 1, 2, . . ., N - 1}$ .

Mỗi tập con có thể được mã hóa thành một số nguyên $N$ bit:

Bit thứ $i$ = 1 → Phần tử $i$ có mặt trong tập.
Bit thứ $i$ = 0 → Phần tử $i$ không có mặt trong tập.

1.2. Ví dụ minh họa

Cho 4 công việc: ${A, B, C, D}$ tương ứng với các bit ${0, 1, 2, 3}$ .

Trạng thái	Nhị phân (bit 3..0)	Thập phân	Ý nghĩa
Rỗng (∅)	`0000`	0	Chưa làm việc nào
Chỉ làm A	`0001`	1	Đã làm công việc A
Làm A và C	`0101`	5	Đã làm A và C
Làm A, B, D	`1011`	11	Đã làm A, B, D
Làm tất cả	`1111`	15	Đã hoàn thành cả 4 việc

NOTE

Quy ước: Bit được đánh số từ phải sang trái, bắt đầu từ bit 0. Số 0101 = bit 0 bật (A), bit 2 bật (C) → Tập ${A, C}$ .

1.3. Tại sao dùng Bitmask?

Lý do 1: Truy cập $O (1)$

dp[mask] = chi phí tối ưu khi đã chọn các phần tử trong mask

Thay vì dùng set hoặc tuple làm key (tốn $O (N)$ để hash), ta dùng số nguyên làm chỉ số mảng — truy cập tức thì.

Lý do 2: Thao tác tập hợp cực nhanh Các phép toán trên tập hợp trở thành phép toán bitwise — chỉ 1 instruction CPU.

Phần 2: Các Thao tác Bitwise Cơ bản

Đây là "bảng công cụ" bạn sẽ dùng trong mọi bài Bitmask DP:

2.1. Kiểm tra phần tử (Check bit)

Câu hỏi: Phần tử $j$ có trong mask không?

python

# Cách 1: Dịch phải rồi AND với 1
if (mask >> j) & 1:
    print(f"Phần tử {j} đã có trong mask")

# Cách 2: AND với (1 << j)
if mask & (1 << j):
    print(f"Phần tử {j} đã có trong mask")

Giải thích:

1 << j = số có duy nhất bit thứ $j$ bật → tạo "mặt nạ" để kiểm tra.
mask & (1 << j) ≠ 0 khi bit $j$ của mask = 1.

2.2. Thêm phần tử (Set bit)

Câu hỏi: Thêm phần tử $j$ vào mask, thu được mask mới?

python

new_mask = mask | (1 << j)

Giải thích: Phép OR đảm bảo bit $j$ được bật lên 1, các bit khác giữ nguyên.

mask     = 0101  (có A, C)
1 << 1   = 0010  (vị trí B)
OR       = 0111  (có A, B, C)

2.3. Xóa phần tử (Clear bit)

Câu hỏi: Xóa phần tử $j$ khỏi mask?

python

new_mask = mask & ~(1 << j)

Giải thích: ~(1 << j) là "mặt nạ ngược" — tất cả bit = 1 trừ bit $j$ = 0. Phép AND sẽ xóa bit $j$ .

mask     = 0111  (có A, B, C)
1 << 1   = 0010
~(1 << 1)= 1101
AND      = 0101  (còn A, C)

2.4. Đếm số phần tử (Population count)

python

count = bin(mask).count('1')  # Cách Python

# Hoặc dùng bit_count() từ Python 3.10+
count = mask.bit_count()

2.5. Mask đầy đủ (Full mask)

python

full_mask = (1 << n) - 1  # Tất cả n bit đều = 1

Ví dụ với $n = 4$ :

1 << 4   = 10000 = 16
16 - 1   = 01111 = 15 = full_mask

Phần 3: Bài toán Phân công (Assignment Problem)

3.1. Phát biểu bài toán

Đề bài: Có $N$ người và $N$ công việc. Chi phí để thuê người $i$ làm việc $j$ là cost[i][j]. Mỗi người chỉ làm đúng 1 việc, mỗi việc chỉ được giao cho đúng 1 người. Tìm cách phân công sao cho tổng chi phí nhỏ nhất.

Ví dụ: 3 người, 3 việc

cost = [
    [9, 2, 7],   # Người 0: làm việc 0 tốn 9, việc 1 tốn 2, việc 2 tốn 7
    [6, 4, 3],   # Người 1
    [5, 8, 1]    # Người 2
]

Phân công tối ưu: Người 0 → Việc 1 (cost=2), Người 1 → Việc 0 (cost=6), Người 2 → Việc 2 (cost=1). Tổng = 9.

3.2. Phân tích trạng thái

Người: Duyệt từ 0 đến $N - 1$ tuần tự.
Việc đã giao: Dùng bitmask — bit $j$ = 1 nghĩa là việc $j$ đã có người làm.

State: dp(worker_id, mask) = Chi phí tối thiểu để phân công từ người worker_id đến hết, biết rằng mask là tập các việc đã được giao.

3.3. Công thức truy hồi (Recurrence)

dp(worker_id, mask) = min over all job j where (j not in mask):
    cost[worker_id][j] + dp(worker_id + 1, mask | (1 << j))

Giải thích bằng lời:

Xét người thứ worker_id.
Thử giao mỗi việc $j$ mà chưa ai làm (bit $j$ trong mask = 0).
Chi phí = chi phí người này làm việc $j$ + chi phí tối ưu của phần còn lại.

Base case: Khi worker_id == N (đã phân công xong), trả về 0.

3.4. Triển khai Python

python

from functools import lru_cache
import sys

def solve_assignment(cost: list[list[int]]) -> int:
    """
    Giải bài toán phân công bằng Bitmask DP.
    
    Args:
        cost: Ma trận chi phí N x N, cost[i][j] = chi phí người i làm việc j.
    
    Returns:
        Chi phí tối thiểu để phân công tất cả.
    
    Time Complexity: O(N^2 * 2^N)
    Space Complexity: O(N * 2^N)
    """
    n = len(cost)
    
    @lru_cache(maxsize=None)
    def dp(worker_id: int, mask: int) -> int:
        """
        Đệ quy có nhớ (Memoization).
        
        Args:
            worker_id: Đang xét người thứ mấy (0-indexed).
            mask: Bitmask các việc đã được giao.
        
        Returns:
            Chi phí tối ưu từ đây đến hết.
        """
        # BASE CASE: Đã phân công xong mọi người
        if worker_id == n:
            return 0
        
        min_cost = sys.maxsize
        
        # Thử từng việc j
        for job in range(n):
            # Kiểm tra: việc j đã có người làm chưa?
            # (mask >> job) & 1 = lấy bit thứ job của mask
            if (mask >> job) & 1 == 0:  # Bit = 0 → Việc chưa được giao
                # Giao việc job cho người worker_id
                # mask | (1 << job) = bật bit job lên
                new_mask = mask | (1 << job)
                
                # Chi phí = chi phí hiện tại + chi phí tối ưu phần còn lại
                total_cost = cost[worker_id][job] + dp(worker_id + 1, new_mask)
                min_cost = min(min_cost, total_cost)
        
        return min_cost
    
    # Bắt đầu: Người 0, chưa việc nào được giao (mask = 0)
    return dp(0, 0)


# ===== DEMO =====
if __name__ == "__main__":
    cost_matrix = [
        [9, 2, 7],
        [6, 4, 3],
        [5, 8, 1]
    ]
    
    result = solve_assignment(cost_matrix)
    print(f"Chi phí tối thiểu: {result}")  # Output: 9

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

Số trạng thái: $N \times 2^{N}$ (N giá trị worker_id, $2^{N}$ giá trị mask).
Chi phí mỗi trạng thái: $O (N)$ (duyệt qua N việc).
Tổng: $O (N^{2} \times 2^{N})$ .

So sánh với Brute-force:

N	Brute-force $O (N!)$	Bitmask DP $O (N^{2} \times 2^{N})$
10	3,628,800	102,400
15	1.3 × 10¹²	7,372,800
20	2.4 × 10¹⁸	419,430,400

Bitmask DP nhanh hơn hàng tỷ lần với N = 15!

Phần 4: Mở rộng — Bài toán Người bán hàng (TSP)

4.1. Phát biểu bài toán

Traveling Salesman Problem (TSP): Một người bán hàng cần thăm $N$ thành phố, mỗi thành phố đúng 1 lần, rồi quay về điểm xuất phát. Tìm lộ trình có tổng quãng đường nhỏ nhất.

4.2. State definition

State: dp(mask, last) = Quãng đường ngắn nhất để:

Đã thăm các thành phố trong mask.
Thành phố cuối cùng vừa thăm là last.

4.3. Recurrence

dp(mask, last) = min over all city prev in mask (prev ≠ last):
    dp(mask without last, prev) + dist[prev][last]

Hoặc viết theo chiều "tiến tới":

python

# Từ trạng thái (mask, last), thử đi tới city next chưa thăm
for next in range(n):
    if (mask >> next) & 1 == 0:  # next chưa thăm
        new_mask = mask | (1 << next)
        dp[new_mask][next] = min(dp[new_mask][next], 
                                  dp[mask][last] + dist[last][next])

4.4. Code mẫu

python

from functools import lru_cache
import sys

def solve_tsp(dist: list[list[int]]) -> int:
    """
    Giải TSP bằng Bitmask DP.
    
    Args:
        dist: Ma trận khoảng cách N x N.
    
    Returns:
        Độ dài lộ trình ngắn nhất (xuất phát và kết thúc tại thành phố 0).
    
    Time Complexity: O(N^2 * 2^N)
    Space Complexity: O(N * 2^N)
    """
    n = len(dist)
    
    @lru_cache(maxsize=None)
    def dp(mask: int, last: int) -> int:
        """
        Args:
            mask: Tập các thành phố đã thăm.
            last: Thành phố vừa thăm xong.
        
        Returns:
            Chi phí tối ưu để hoàn thành lộ trình từ đây.
        """
        # BASE CASE: Đã thăm hết tất cả thành phố
        if mask == (1 << n) - 1:  # full_mask
            return dist[last][0]  # Quay về thành phố xuất phát (0)
        
        min_cost = sys.maxsize
        
        # Thử đi tới thành phố next chưa thăm
        for next_city in range(n):
            if (mask >> next_city) & 1 == 0:  # Chưa thăm
                new_mask = mask | (1 << next_city)
                cost = dist[last][next_city] + dp(new_mask, next_city)
                min_cost = min(min_cost, cost)
        
        return min_cost
    
    # Xuất phát từ thành phố 0 (đã "thăm" thành phố 0, nên mask = 1)
    return dp(1, 0)


# ===== DEMO =====
if __name__ == "__main__":
    distance = [
        [0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]
    ]
    
    result = solve_tsp(distance)
    print(f"Độ dài lộ trình ngắn nhất: {result}")  # Output: 80
    # Lộ trình: 0 → 1 → 3 → 2 → 0 (10 + 25 + 30 + 15 = 80)

4.5. Phân tích

Độ phức tạp: $O (N^{2} \times 2^{N})$ — giống Assignment Problem.
So với Brute-force $O (N!)$ : Nhanh hơn rất nhiều khi $N \geq 10$ .
Giới hạn thực tế: Với RAM 8GB, có thể giải TSP đến khoảng $N = 20$ .

Phần 5: Ví dụ minh họa — Hamiltonian Path

5.1. Phát biểu bài toán

Hamiltonian Path: Cho đồ thị $N$ đỉnh. Tìm số lượng đường đi đi qua mọi đỉnh đúng 1 lần. (Không yêu cầu quay về đỉnh ban đầu như TSP)

Ví dụ: Đồ thị 4 đỉnh với các cạnh:

0 -- 1
|    |
3 -- 2

Có nhiều Hamiltonian Path: 0→1→2→3, 0→3→2→1, 1→0→3→2, ...

5.2. State & Recurrence

State: dp(mask, last) = Số cách để:

Đã thăm các đỉnh trong mask.
Đỉnh cuối cùng là last.

Recurrence:

dp(mask, last) = Σ dp(mask without last, prev)
                 với mọi prev có cạnh nối tới last

5.3. Triển khai Python

python

from functools import lru_cache

def count_hamiltonian_paths(n: int, edges: list[tuple[int, int]]) -> int:
    """
    Đếm số đường đi Hamiltonian trong đồ thị vô hướng.
    
    Args:
        n: Số đỉnh (0 đến n-1).
        edges: Danh sách cạnh [(u, v), ...].
    
    Returns:
        Số lượng Hamiltonian Path.
    
    Time Complexity: O(N^2 * 2^N)
    """
    # Xây dựng danh sách kề
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    @lru_cache(maxsize=None)
    def dp(mask: int, last: int) -> int:
        """
        Args:
            mask: Tập đỉnh đã thăm.
            last: Đỉnh vừa thăm xong.
        
        Returns:
            Số cách từ trạng thái ban đầu đến (mask, last).
        """
        # BASE CASE: Chỉ có đúng 1 đỉnh (đỉnh last)
        if mask == (1 << last):
            return 1  # 1 cách: bắt đầu từ đỉnh last
        
        count = 0
        # Xét tất cả đỉnh prev có thể đi tới last
        for prev in adj[last]:
            # prev phải đã được thăm (nằm trong mask)
            if (mask >> prev) & 1:
                # Đệ quy: bỏ last ra khỏi mask
                prev_mask = mask ^ (1 << last)  # XOR để tắt bit last
                count += dp(prev_mask, prev)
        
        return count
    
    full_mask = (1 << n) - 1
    total = 0
    
    # Thử kết thúc tại mỗi đỉnh
    for last in range(n):
        total += dp(full_mask, last)
    
    return total


# ===== DEMO =====
if __name__ == "__main__":
    # Đồ thị hình vuông: 0-1, 1-2, 2-3, 3-0
    n = 4
    edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
    
    result = count_hamiltonian_paths(n, edges)
    print(f"Số Hamiltonian Path: {result}")  # Output: 8
    # Các path: 0→1→2→3, 0→3→2→1, 1→0→3→2, 1→2→3→0, 
    #           2→1→0→3, 2→3→0→1, 3→0→1→2, 3→2→1→0

5.4. Phân biệt TSP vs Hamiltonian Path

Đặc điểm	TSP	Hamiltonian Path
Yêu cầu	Quay về đỉnh xuất phát	Không cần quay về
Kết quả	Chi phí nhỏ nhất	Đếm số đường đi
Base case	`mask == full` → +dist về gốc	`mask == (1 << last)` → 1

Phần 6: Ví dụ minh họa — Chia tập bằng nhau (Partition Equal Subset Sum)

6.1. Phát biểu bài toán

Đề bài: Cho mảng $N$ số nguyên dương. Hỏi có thể chia thành 2 phần có tổng bằng nhau không?

Ví dụ:

[1, 5, 11, 5] → Yes: {1, 5, 5} và {11} đều có tổng 11.
[1, 2, 3, 5] → No: Tổng = 11 (lẻ), không chia được.

6.2. Phân tích

Điều kiện cần: Tổng mảng phải chẵn.
Bài toán con: Tìm tập con có tổng = total / 2.

State: dp(mask) = Tổng của các phần tử trong mask.

Nhưng với bài này, ta dùng DP truyền thống (không Bitmask) hiệu quả hơn. Tuy nhiên, nếu $N \leq 20$ , Bitmask DP vẫn giải được!

6.3. Giải bằng Bitmask (Meet in the Middle)

Khi $N \leq 40$ , ta dùng kỹ thuật Meet in the Middle:

Chia mảng thành 2 nửa (mỗi nửa $\leq 20$ phần tử).
Duyệt tất cả tập con của mỗi nửa.
Ghép kết quả.

python

from typing import List

def can_partition(nums: List[int]) -> bool:
    """
    Kiểm tra có thể chia mảng thành 2 phần có tổng bằng nhau.
    
    Approach: Meet in the Middle (cho N <= 40).
    
    Time Complexity: O(2^(N/2))
    """
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    n = len(nums)
    
    # Chia thành 2 nửa
    mid = n // 2
    left_half = nums[:mid]
    right_half = nums[mid:]
    
    def all_subset_sums(arr: List[int]) -> set:
        """Tính tổng của tất cả tập con."""
        sums = {0}
        for num in arr:
            # Thêm num vào mỗi tổng hiện có
            sums = sums | {s + num for s in sums}
        return sums
    
    left_sums = all_subset_sums(left_half)
    right_sums = all_subset_sums(right_half)
    
    # Tìm: left_sum + right_sum == target
    for ls in left_sums:
        if (target - ls) in right_sums:
            return True
    
    return False


# ===== DEMO =====
if __name__ == "__main__":
    print(can_partition([1, 5, 11, 5]))  # True
    print(can_partition([1, 2, 3, 5]))   # False
    print(can_partition([1, 2, 3, 4, 5, 6, 7]))  # True (14 = 1+6+7 = 2+3+4+5)

6.4. Bitmask thuần túy (N ≤ 20)

python

def can_partition_bitmask(nums: list[int]) -> bool:
    """
    Giải bằng Bitmask DP thuần túy.
    Chỉ dùng khi N <= 20.
    
    Time Complexity: O(2^N)
    """
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    n = len(nums)
    
    # Duyệt tất cả 2^N tập con
    for mask in range(1 << n):
        subset_sum = 0
        for i in range(n):
            if (mask >> i) & 1:
                subset_sum += nums[i]
        
        if subset_sum == target:
            return True
    
    return False

TIP

Khi nào dùng cách nào?

$N \leq 20$ : Bitmask thuần túy $O (2^{N})$ .
$20 < N \leq 40$ : Meet in the Middle $O (2^{N / 2})$ .
$N > 40$ : DP truyền thống $O (N \times sum)$ .

Phần 7: Ví dụ minh họa — SOS DP (Sum over Subsets)

7.1. Phát biểu bài toán

SOS DP: Cho mảng $A$ với $2^{N}$ phần tử. Với mỗi mask, tính:
$F [m a s k] = \sum_{s u b m a s k \subseteq m a s k} A [s u b m a s k]$
Tức là tổng của tất cả $A [i]$ mà $i$ là tập con của mask.

Ví dụ với $N = 2$ :

A = [1, 2, 3, 4]  # A[00]=1, A[01]=2, A[10]=3, A[11]=4

F[00] = A[00] = 1
F[01] = A[00] + A[01] = 1 + 2 = 3
F[10] = A[00] + A[10] = 1 + 3 = 4
F[11] = A[00] + A[01] + A[10] + A[11] = 1 + 2 + 3 + 4 = 10

7.2. Naive approach — $O (3^{N})$

python

# Cách naive: duyệt tất cả submask của mask
for mask in range(1 << n):
    submask = mask
    while submask >= 0:
        F[mask] += A[submask]
        if submask == 0:
            break
        submask = (submask - 1) & mask  # Trick: lấy submask tiếp theo

Độ phức tạp: $\sum_{k = 0}^{N} (\binom{N}{k}) 2^{k} = 3^{N}$ (quá chậm!).

7.3. SOS DP — $O (N \times 2^{N})$

Ý tưởng: Xây dựng $F$ theo từng chiều bit.

python

def sos_dp(A: list[int], n: int) -> list[int]:
    """
    Sum over Subsets DP.
    
    Với mỗi mask, tính tổng A[submask] cho mọi submask ⊆ mask.
    
    Args:
        A: Mảng 2^n phần tử.
        n: Số bit.
    
    Returns:
        F: Mảng kết quả.
    
    Time Complexity: O(N * 2^N)
    Space Complexity: O(2^N)
    """
    F = A.copy()  # F[mask] khởi tạo = A[mask]
    
    # Xử lý từng chiều bit
    for i in range(n):
        for mask in range(1 << n):
            # Nếu bit i bật, cộng thêm F của mask với bit i tắt
            if (mask >> i) & 1:
                F[mask] += F[mask ^ (1 << i)]
    
    return F


# ===== DEMO =====
if __name__ == "__main__":
    n = 3
    A = [1, 2, 3, 4, 5, 6, 7, 8]  # 2^3 = 8 phần tử
    
    F = sos_dp(A, n)
    
    print("Kết quả SOS DP:")
    for mask in range(1 << n):
        print(f"  F[{mask:03b}] = {F[mask]}")
    
    # Output:
    # F[000] = 1
    # F[001] = 1+2 = 3
    # F[010] = 1+3 = 4
    # F[011] = 1+2+3+4 = 10
    # F[100] = 1+5 = 6
    # F[101] = 1+2+5+6 = 14
    # F[110] = 1+3+5+7 = 16
    # F[111] = 1+2+3+4+5+6+7+8 = 36

7.4. Giải thích thuật toán

Bất biến: Sau khi xử lý bit $i$ , $F [m a s k]$ chứa tổng của tất cả $A [s u b m a s k]$ mà $s u b m a s k$ chỉ khác $m a s k$ ở các bit $0, 1, . . ., i$ .

Ví dụ với $m a s k = 111$ (bit 2, 1, 0 đều bật):

Sau bit 0: $F [111]$ += $F [110]$ → có $A [111] + A [110]$ .
Sau bit 1: $F [111]$ += $F [101]$ → có thêm $A [101] + A [100]$ .
Sau bit 2: $F [111]$ += $F [011]$ → có thêm $A [011] + A [010] + A [001] + A [000]$ .

7.5. Ứng dụng SOS DP

Đếm số lượng: Có bao nhiêu số trong mảng mà tất cả bit của nó là tập con của $x$ ?
AND/OR problems: Tính tổng $A [i]$ cho mọi $i$ mà $i AND m a s k = i$ .
Combinatorial optimization: Tối ưu trên tất cả tập con.

Phần 8: Ví dụ minh họa — Steiner Tree Problem

8.1. Phát biểu bài toán

Steiner Tree: Cho đồ thị $N$ đỉnh và tập $K$ đỉnh terminal. Tìm cây con có trọng số nhỏ nhất chứa tất cả terminal.

Đây là bài toán NP-hard, nhưng với $K \leq 20$ , ta dùng Bitmask DP.

8.2. State

State: dp[mask][v] = Chi phí nhỏ nhất để:

Cây chứa các terminal trong mask.
Cây có gốc tại đỉnh v.

8.3. Transitions

Mở rộng cây (đi sang đỉnh kề):

dp[mask][v] = min(dp[mask][u] + weight(u, v))

Hợp nhất hai cây con (combine):

dp[mask][v] = min(dp[sub1][v] + dp[sub2][v])
với sub1 | sub2 = mask, sub1 & sub2 = {v nếu v là terminal}

8.4. Code mẫu (Simplified)

python

import heapq
from typing import List, Tuple

def steiner_tree(
    n: int,
    edges: List[Tuple[int, int, int]],  # (u, v, weight)
    terminals: List[int]
) -> int:
    """
    Tìm Steiner Tree nhỏ nhất.
    
    Args:
        n: Số đỉnh.
        edges: Danh sách cạnh có trọng số.
        terminals: Danh sách đỉnh terminal.
    
    Returns:
        Trọng số của Steiner Tree nhỏ nhất.
    
    Time Complexity: O(3^K * N + 2^K * N^2 * log(N))
    với K = số terminal
    """
    INF = float('inf')
    k = len(terminals)
    
    # Đánh số lại terminal: terminal[i] -> bit i
    term_to_bit = {t: i for i, t in enumerate(terminals)}
    
    # Xây đồ thị
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    # dp[mask][v] = chi phí min để cây chứa terminals trong mask, gốc tại v
    dp = [[INF] * n for _ in range(1 << k)]
    
    # Base case: mỗi terminal chỉ chứa chính nó
    for t, bit in term_to_bit.items():
        dp[1 << bit][t] = 0
    
    # Duyệt theo mask tăng dần (subset DP)
    for mask in range(1, 1 << k):
        # Bước 1: Combine hai cây con
        # Duyệt tất cả cách chia mask thành sub1, sub2
        sub = mask
        while sub > 0:
            complement = mask ^ sub
            if complement > 0 and sub <= complement:  # Tránh đếm trùng
                for v in range(n):
                    if dp[sub][v] < INF and dp[complement][v] < INF:
                        dp[mask][v] = min(dp[mask][v], 
                                         dp[sub][v] + dp[complement][v])
            sub = (sub - 1) & mask
        
        # Bước 2: Dijkstra để mở rộng cây (relaxation)
        # dp[mask][v] có thể cập nhật từ dp[mask][u] + edge(u,v)
        dist = dp[mask].copy()
        pq = [(d, v) for v, d in enumerate(dist) if d < INF]
        heapq.heapify(pq)
        
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(pq, (dist[v], v))
        
        dp[mask] = dist
    
    # Kết quả: mask = full, gốc có thể ở bất kỳ đâu
    full_mask = (1 << k) - 1
    return min(dp[full_mask])


# ===== DEMO =====
if __name__ == "__main__":
    # Đồ thị 5 đỉnh, terminal = {0, 2, 4}
    n = 5
    edges = [
        (0, 1, 1), (1, 2, 1),  # 0 - 1 - 2
        (0, 3, 2), (3, 4, 2),  # 0 - 3 - 4
        (2, 4, 3)              # 2 - 4
    ]
    terminals = [0, 2, 4]
    
    result = steiner_tree(n, edges, terminals)
    print(f"Steiner Tree weight: {result}")  # Output: 4
    # Cây tối ưu: 0-1-2 và 0-3-4 (tổng = 1+1+2 = 4? Không!)
    # Thực ra: 0-1-2 (cost=2) + 2-4 (cost=3) = 5
    # Hoặc: 0-1-2 (2) + 0-3-4 (4) - 0 = 6-0 = 6? 
    # Cần kiểm tra lại...

WARNING

Steiner Tree là bài toán phức tạp. Code trên là phiên bản đơn giản hóa. Production code cần xử lý nhiều edge case hơn.

Phần 9: Tổng kết & Best Practices

9.1. Khi nào dùng Bitmask DP?

Dấu hiệu	Giải thích
$N \leq 20$	Để $2^{N}$ vừa bộ nhớ
Bài toán dạng "chọn/không chọn"	Mỗi phần tử có 2 trạng thái → phù hợp bit
Cần tìm min/max/count	Bài toán tối ưu tổ hợp điển hình
Backtracking có nhiều trạng thái trùng	Có thể cache bằng mask

9.2. Template chung

python

from functools import lru_cache

def bitmask_dp_template(n: int, ...):
    @lru_cache(maxsize=None)
    def dp(mask: int, ...other_params) -> int:
        # BASE CASE
        if mask == (1 << n) - 1:  # hoặc điều kiện khác
            return ...
        
        result = ...  # Giá trị khởi tạo (inf hoặc -inf)
        
        for i in range(n):
            if (mask >> i) & 1 == 0:  # Phần tử i chưa được chọn
                new_mask = mask | (1 << i)
                result = optimize(result, dp(new_mask, ...))
        
        return result
    
    return dp(0, ...)  # Hoặc dp(1, ...) nếu đã chọn 1 phần tử ban đầu

9.3. Bảng tổng hợp các bài toán

Bài toán	State	Độ phức tạp	Đặc điểm
Assignment	`dp(worker, mask)`	$O (N^{2} \cdot 2^{N})$	1-1 matching
TSP	`dp(mask, last)`	$O (N^{2} \cdot 2^{N})$	Cycle, min cost
Hamiltonian Path	`dp(mask, last)`	$O (N^{2} \cdot 2^{N})$	Path, count
Subset Partition	Meet in Middle	$O (2^{N / 2})$	Sum = target
SOS DP	`F[mask]`	$O (N \cdot 2^{N})$	Sum over subsets
Steiner Tree	`dp(mask, v)`	$O (3^{K} \cdot N)$	Tree covering K terminals

9.4. Các trick thường dùng

python

# 1. Duyệt tất cả submask của mask
sub = mask
while sub > 0:
    # Xử lý sub
    sub = (sub - 1) & mask

# 2. Duyệt tất cả superset của mask (cần full_mask)
sup = mask
while sup < (1 << n):
    # Xử lý sup
    sup = (sup + 1) | mask

# 3. Lowest set bit
lowest_bit = mask & (-mask)

# 4. Bỏ lowest set bit
mask_without_lowest = mask & (mask - 1)

# 5. Đếm trailing zeros (vị trí bit thấp nhất)
import math
pos = int(math.log2(mask & (-mask))) if mask else -1
# Hoặc: pos = (mask & -mask).bit_length() - 1

Bài tập thực hành

Bài 1: Đơn giản

Cho tập ${A, B, C, D, E}$ (5 phần tử). Hãy tính:

Mask của tập ${B, D, E}$ ?
Biểu thức Python để kiểm tra D có trong mask không?
Biểu thức Python để thêm C vào mask trên?

Đáp án

python

# B=1, D=3, E=4 → mask = 0b11010 = 26
mask = (1 << 1) | (1 << 3) | (1 << 4)  # = 26

# Kiểm tra D (bit 3)
has_D = (mask >> 3) & 1  # = 1 (True)

# Thêm C (bit 2)
new_mask = mask | (1 << 2)  # = 0b11110 = 30

Bài 2: Trung bình

Sửa hàm solve_assignment để trả về cả cách phân công tối ưu (người nào làm việc nào), không chỉ chi phí.

Gợi ý

Thêm một hàm backtrack sau khi tính xong DP:

python

def get_assignment(cost, dp_cache):
    n = len(cost)
    assignment = []
    mask = 0
    
    for worker in range(n):
        for job in range(n):
            if (mask >> job) & 1 == 0:
                new_mask = mask | (1 << job)
                if dp_cache[(worker, mask)] == cost[worker][job] + dp_cache[(worker+1, new_mask)]:
                    assignment.append((worker, job))
                    mask = new_mask
                    break
    
    return assignment

Bài 3: Nâng cao

Biến thể TSP: Người bán hàng không cần quay về điểm xuất phát. Tìm đường đi ngắn nhất thăm tất cả thành phố đúng 1 lần (có thể kết thúc ở bất kỳ thành phố nào).

Gợi ý

Sửa base case:

python

# Thay vì: return dist[last][0]
# Đổi thành:
if mask == (1 << n) - 1:
    return 0  # Không cần quay về gốc

Bài 4: Thử thách

Cho mảng $N$ số nguyên ( $N \leq 20$ ). Đếm số cách chia mảng thành đúng 3 phần có tổng bằng nhau.

Gợi ý

Kiểm tra tổng mảng chia hết cho 3.
Target = total / 3.
Duyệt tất cả mask, tìm các subset có tổng = target.
Với mỗi mask có tổng = target, duyệt các submask cũng có tổng = target.
Đếm số cách chia hợp lệ.

Tài liệu tham khảo

Competitive Programmer's Handbook — Chương 10: Bit manipulation.
CSES Problem Set — Section: "Dynamic Programming" có nhiều bài Bitmask DP.
Introduction to Algorithms (CLRS) — Chapter 22: Traveling Salesman Problem.
CF Blog: SOS DP — Tutorial on SOS DP
AtCoder Educational DP Contest — Bài U (Grouping) là Bitmask DP kinh điển.

Bitmask Dynamic Programming ​

Mở đầu: Từ Quay lui đến Tối ưu hóa ​

Phần 1: Mã hóa Trạng thái (State Encoding) ​

1.1. Ý tưởng cốt lõi ​

1.2. Ví dụ minh họa ​

1.3. Tại sao dùng Bitmask? ​

Phần 2: Các Thao tác Bitwise Cơ bản ​

2.1. Kiểm tra phần tử (Check bit) ​

2.2. Thêm phần tử (Set bit) ​

2.3. Xóa phần tử (Clear bit) ​

2.4. Đếm số phần tử (Population count) ​

2.5. Mask đầy đủ (Full mask) ​

Phần 3: Bài toán Phân công (Assignment Problem) ​

3.1. Phát biểu bài toán ​

3.2. Phân tích trạng thái ​

3.3. Công thức truy hồi (Recurrence) ​

3.4. Triển khai Python ​

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

Phần 4: Mở rộng — Bài toán Người bán hàng (TSP) ​

4.1. Phát biểu bài toán ​

4.2. State definition ​

4.3. Recurrence ​

4.4. Code mẫu ​

4.5. Phân tích ​

Phần 5: Ví dụ minh họa — Hamiltonian Path ​

5.1. Phát biểu bài toán ​

5.2. State & Recurrence ​

5.3. Triển khai Python ​

5.4. Phân biệt TSP vs Hamiltonian Path ​

Phần 6: Ví dụ minh họa — Chia tập bằng nhau (Partition Equal Subset Sum) ​

6.1. Phát biểu bài toán ​

6.2. Phân tích ​

6.3. Giải bằng Bitmask (Meet in the Middle) ​

6.4. Bitmask thuần túy (N ≤ 20) ​

Phần 7: Ví dụ minh họa — SOS DP (Sum over Subsets) ​

7.1. Phát biểu bài toán ​

7.2. Naive approach — O(3N) ​

7.3. SOS DP — O(N×2N) ​

7.4. Giải thích thuật toán ​

7.5. Ứng dụng SOS DP ​

Phần 8: Ví dụ minh họa — Steiner Tree Problem ​

8.1. Phát biểu bài toán ​

8.2. State ​

8.3. Transitions ​

8.4. Code mẫu (Simplified) ​

Phần 9: Tổng kết & Best Practices ​

9.1. Khi nào dùng Bitmask DP? ​

9.2. Template chung ​

9.3. Bảng tổng hợp các bài toán ​

9.4. Các trick thường dùng ​

Bài tập thực hành ​

Bài 1: Đơn giản ​

Bài 2: Trung bình ​

Bài 3: Nâng cao ​

Bài 4: Thử thách ​

Tài liệu tham khảo ​

Bitmask Dynamic Programming

Mở đầu: Từ Quay lui đến Tối ưu hóa

Phần 1: Mã hóa Trạng thái (State Encoding)

1.1. Ý tưởng cốt lõi

1.2. Ví dụ minh họa

1.3. Tại sao dùng Bitmask?

Phần 2: Các Thao tác Bitwise Cơ bản

2.1. Kiểm tra phần tử (Check bit)

2.2. Thêm phần tử (Set bit)

2.3. Xóa phần tử (Clear bit)

2.4. Đếm số phần tử (Population count)

2.5. Mask đầy đủ (Full mask)

Phần 3: Bài toán Phân công (Assignment Problem)

3.1. Phát biểu bài toán

3.2. Phân tích trạng thái

3.3. Công thức truy hồi (Recurrence)

3.4. Triển khai Python

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

Phần 4: Mở rộng — Bài toán Người bán hàng (TSP)

4.1. Phát biểu bài toán

4.2. State definition

4.3. Recurrence

4.4. Code mẫu

4.5. Phân tích

Phần 5: Ví dụ minh họa — Hamiltonian Path

5.1. Phát biểu bài toán

5.2. State & Recurrence

5.3. Triển khai Python

5.4. Phân biệt TSP vs Hamiltonian Path

Phần 6: Ví dụ minh họa — Chia tập bằng nhau (Partition Equal Subset Sum)

6.1. Phát biểu bài toán

6.2. Phân tích

6.3. Giải bằng Bitmask (Meet in the Middle)

6.4. Bitmask thuần túy (N ≤ 20)

Phần 7: Ví dụ minh họa — SOS DP (Sum over Subsets)

7.1. Phát biểu bài toán

7.2. Naive approach — $O (3^{N})$

7.3. SOS DP — $O (N \times 2^{N})$

7.4. Giải thích thuật toán

7.5. Ứng dụng SOS DP

Phần 8: Ví dụ minh họa — Steiner Tree Problem

8.1. Phát biểu bài toán

8.2. State

8.3. Transitions

8.4. Code mẫu (Simplified)

Phần 9: Tổng kết & Best Practices

9.1. Khi nào dùng Bitmask DP?

9.2. Template chung

9.3. Bảng tổng hợp các bài toán

9.4. Các trick thường dùng

Bài tập thực hành

Bài 1: Đơn giản

Bài 2: Trung bình

Bài 3: Nâng cao

Bài 4: Thử thách

Tài liệu tham khảo