Lesson 29 — Bitmask DP
Dùng một số nguyên làm tập hợp, rồi quy hoạch động trên các tập đó. Ba module: khám phá bitmask, giải TSP từng bước, và trick liệt kê mọi tập con.
1. Bitmask Explorer — số nguyên là tập hợp
Click vào một bit để bật/tắt, hoặc dùng các nút thao tác. Bit i bật ⟺ phần tử i thuộc tập.
mask = 0 (thập phân) = 00000 (nhị phân)
Tập = {} · popcount = 0
Thao tác sẽ hiện ở đây...
2. TSP Solver — dp[mask][i] từng bước
Xuất phát từ thành phố 0 (đỏ), thăm hết, về 0, chi phí nhỏ nhất.
Nhấn "Giải từng bước" để animate bảng dp[mask][i] điền dần; đường tối ưu tô đỏ trên đồ thị.
Chi phí tối ưu: — · Đường: —
Nhấn "Giải từng bước"...
3. Subset Enumeration — trick (s-1) & mask
Liệt kê mọi tập con của một mask bằng vòng lặp một dòng
for s := mask; s > 0; s = (s-1) & mask. Mỗi bước hiện s-1 rồi & mask.
Đã liệt kê: 0 tập con (mong đợi 2popcount − 1 khác rỗng)
Nhấn "Bước tiếp" để chạy trick từng vòng lặp...