Khóa học Python từ Cơ bản đến Nâng cao

Bài 15.4 - Kết hợp DP với bitmask trong Python

Khi phải giải các bài toán tổ hợp phức tạp, ví dụ như đi qua tất cả các điểm một lần (Traveling Salesman Problem - TSP) hoặc chọn nhóm tối ưu, việc kết hợp Dynamic Programming (DP) với bitmask là một kỹ thuật cực kỳ mạnh mẽ. 💡

1. Bitmask là gì?

Bitmask là cách biểu diễn tập hợp con dưới dạng nhị phân. Với n phần tử, bạn có thể dùng một số nguyên từ 0 đến (1 << n) - 1 để biểu diễn toàn bộ các tập con của chúng.

Ví dụ:

n = 3
for mask in range(1 << n):
    print(f"Mask {mask:03b}")

Kết quả:

Mask 000
Mask 001
Mask 010
Mask 011
Mask 100
Mask 101
Mask 110
Mask 111

👉 Mỗi bit 1 trong mask thể hiện phần tử đang được chọn trong tập hợp con.

2. Kết hợp với DP: Bài toán TSP (Traveling Salesman Problem)

Mô tả: Cho n thành phố, chi phí di chuyển giữa mỗi cặp thành phố. Tìm đường đi ngắn nhất bắt đầu từ thành phố 0, đi qua tất cả các thành phố đúng 1 lần rồi quay lại 0.

Cách giải bằng DP + Bitmask

import sys
n = 4
INF = sys.maxsize
cost = [
    [0, 20, 42, 35],
    [20, 0, 30, 34],
    [42, 30, 0, 12],
    [35, 34, 12, 0]
]

# dp[mask][u]: chi phí tối thiểu để đi qua các thành phố trong mask, kết thúc tại u
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0  # Bắt đầu từ thành phố 0

for mask in range(1 << n):
    for u in range(n):
        if not (mask & (1 << u)):
            continue
        for v in range(n):
            if mask & (1 << v):
                continue
            next_mask = mask | (1 << v)
            dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + cost[u][v])

res = INF
for u in range(1, n):
    res = min(res, dp[(1 << n) - 1][u] + cost[u][0])

print("Chi phí ngắn nhất:", res)

Giải thích:

• mask lưu trạng thái những thành phố đã đi qua.
• dp[mask][u]: chi phí tối thiểu để đến u sau khi đi qua các thành phố trong mask.
• Từng bước, ta thử thêm một thành phố mới vào mask, cập nhật chi phí nhỏ nhất.

3. Một ví dụ khác: Chia đội sao cho cân bằng

Cho n người (n chẵn), và một ma trận điểm tương tác giữa họ. Chia thành 2 đội sao cho chênh lệch tổng điểm tương tác giữa 2 đội là nhỏ nhất.

import sys
from itertools import combinations

def calc_diff(team, matrix):
    total = 0
    for i in team:
        for j in team:
            total += matrix[i][j]
    return total

n = 4
matrix = [
    [0, 1, 2, 3],
    [4, 0, 5, 6],
    [7, 1, 0, 2],
    [3, 4, 5, 0]
]

players = list(range(n))
min_diff = sys.maxsize

for mask in range(1 << n):
    if bin(mask).count('1') != n // 2:
        continue
    team1 = [i for i in range(n) if (mask & (1 << i))]
    team2 = [i for i in range(n) if not (mask & (1 << i))]
    diff = abs(calc_diff(team1, matrix) - calc_diff(team2, matrix))
    min_diff = min(min_diff, diff)

print("Chênh lệch nhỏ nhất:", min_diff)

Giải thích:

• Mỗi mask biểu diễn một tổ hợp chọn n/2 người vào đội 1.
• Đội 2 là phần còn lại.
• Duyệt tất cả mask thoả điều kiện và cập nhật độ chênh lệch nhỏ nhất.

Kết luận

Sự kết hợp giữa DP và bitmask giúp giải quyết hiệu quả những bài toán có không gian trạng thái lớn nhưng có thể biểu diễn bằng tập hợp con. Dù có vẻ phức tạp lúc đầu, nhưng khi hiểu rồi thì sẽ thấy cực kỳ mạnh mẽ! 🚀

✨ Thành thạo bitmask và DP sẽ giúp bạn vượt qua nhiều bài toán khó nhằn trong lập trình thi đấu và thực tế.

#FullhouseDev chúc bạn học vui! 💻🚀