Bitmask DP — Quy hoạch động trên tập con

Khi Google Maps tính toán tuyến đường tối ưu cho đội giao hàng qua 15 điểm, khi hệ thống lập lịch phân công N công việc cho N nhân viên với chi phí tối thiểu, khi compiler tối ưu register allocation — tất cả đều là bài toán tối ưu tổ hợp mà Backtracking thuần O(N!) không kham nổi. Bitmask DP giảm xuống O(N² × 2^N), biến "không khả thi" thành "chạy trong vài giây".

Ý tưởng cốt lõi: mã hóa mỗi tập con phần tử thành một số nguyên (bitmask), dùng số nguyên đó làm chỉ số mảng để lưu kết quả DP. Mỗi phép toán trên tập hợp (thêm, xóa, kiểm tra phần tử) trở thành phép toán bitwise — chỉ 1 CPU instruction.

Giới hạn quan trọng: kỹ thuật này chỉ áp dụng khi N nhỏ, thường N ≤ 20. Lý do: 2²⁰ ≈ 1 triệu (chấp nhận được), nhưng 2³⁰ ≈ 1 tỷ (quá lớn cho cả memory lẫn time).

Bức tranh tư duy

Hãy tưởng tượng bạn là quản lý một nhà hàng ở Sài Gòn với 5 bàn, mỗi bàn có trạng thái: đã đặt hoặc trống. Thay vì ghi "Bàn 1: đặt, Bàn 2: trống, Bàn 3: đặt...", bạn ghi một con số: 10110 — bit 1, 2, 4 bật nghĩa là bàn 1, 2, 4 đã đặt. Một con số 5 chữ số nhị phân thay thế cả bảng trạng thái.

Mã hóa tập hợp bằng bitmask:
Tập {A, B, C, D} → 4 bit, mỗi phần tử 1 bit

  Tập con         Nhị phân    Thập phân
  ∅ (rỗng)        0000          0
  {A}              0001          1
  {A, C}           0101          5
  {A, B, D}        1011         11
  {A, B, C, D}     1111         15

Thao tác tập hợp = Phép bitwise:
  Kiểm tra j ∈ mask:    (mask >> j) & 1
  Thêm j vào mask:      mask | (1 << j)
  Xóa j khỏi mask:      mask & ~(1 << j)
  Toggle j:              mask ^ (1 << j)
  Đếm phần tử:          popcount(mask)
  Mask đầy đủ N bit:    (1 << N) - 1

  Ví dụ: mask = 0101 (có A, C), thêm B:
  mask     = 0101
  1 << 1   = 0010  (vị trí B)
  OR       = 0111  (có A, B, C) ✓

Điểm mấu chốt: truy cập dp[mask] là O(1) — nhanh hơn hẳn dùng set hay tuple làm key (tốn O(N) để hash).

Cốt lõi kỹ thuật

Các phép bitwise nền tảng

Đây là "bộ công cụ" bắt buộc nắm vững trước khi viết bất kỳ bài Bitmask DP nào:

C++PythonJavaGo

cpp

// Kiểm tra bit j
bool hasBit(int mask, int j) { return (mask >> j) & 1; }

// Bật bit j
int setBit(int mask, int j) { return mask | (1 << j); }

// Tắt bit j
int clearBit(int mask, int j) { return mask & ~(1 << j); }

// Đếm số bit 1
int countBits(int mask) { return __builtin_popcount(mask); }

// Mask đầy đủ N bit
int fullMask(int n) { return (1 << n) - 1; }

// Bit thấp nhất đang bật
int lowestBit(int mask) { return mask & (-mask); }

// Gosper's hack: tập con tiếp theo cùng kích thước
int nextSamePopcount(int mask) {
    int c = mask & (-mask);
    int r = mask + c;
    return (((r ^ mask) >> 2) / c) | r;
}

python

# Kiểm tra bit j
def has_bit(mask: int, j: int) -> bool:
    return (mask >> j) & 1 == 1

# Bật bit j
def set_bit(mask: int, j: int) -> int:
    return mask | (1 << j)

# Tắt bit j
def clear_bit(mask: int, j: int) -> int:
    return mask & ~(1 << j)

# Đếm số bit 1
def count_bits(mask: int) -> int:
    return bin(mask).count('1')  # hoặc mask.bit_count() (Python 3.10+)

# Mask đầy đủ N bit
def full_mask(n: int) -> int:
    return (1 << n) - 1

# Duyệt tất cả submask của mask
def enumerate_submasks(mask: int):
    sub = mask
    while sub > 0:
        yield sub
        sub = (sub - 1) & mask
    yield 0  # tập rỗng

java

// Kiểm tra bit j
boolean hasBit(int mask, int j) { return ((mask >> j) & 1) == 1; }

// Bật bit j
int setBit(int mask, int j) { return mask | (1 << j); }

// Tắt bit j
int clearBit(int mask, int j) { return mask & ~(1 << j); }

// Đếm số bit 1
int countBits(int mask) { return Integer.bitCount(mask); }

// Mask đầy đủ N bit
int fullMask(int n) { return (1 << n) - 1; }

import "math/bits"

// Kiểm tra bit j
func hasBit(mask, j int) bool { return (mask>>j)&1 == 1 }

// Bật bit j
func setBit(mask, j int) int { return mask | (1 << j) }

// Tắt bit j
func clearBit(mask, j int) int { return mask & ^(1 << j) }

// Đếm số bit 1
func countBits(mask int) int { return bits.OnesCount(uint(mask)) }

// Mask đầy đủ N bit
func fullMask(n int) int { return (1 << n) - 1 }

Assignment Problem — Bài toán phân công

Bài toán: N người, N công việc. Chi phí người i làm việc j là cost[i][j]. Mỗi người đúng 1 việc, mỗi việc đúng 1 người. Tìm phân công tổng chi phí nhỏ nhất.

State: dp(worker, mask) = chi phí tối thiểu để phân công từ người worker trở đi, khi mask là tập các việc đã giao.

Transition: dp(w, mask) = min{ cost[w][j] + dp(w+1, mask | (1<<j)) } cho mọi j chưa trong mask.

C++PythonJavaGo

cpp

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

int n;
int cost[20][20];
int memo[20][1 << 20];

int dp(int worker, int mask) {
    if (worker == n) return 0;
    if (memo[worker][mask] != -1) return memo[worker][mask];

    int res = INT_MAX;
    for (int job = 0; job < n; job++) {
        if (!((mask >> job) & 1)) {
            res = min(res, cost[worker][job] + dp(worker + 1, mask | (1 << job)));
        }
    }
    return memo[worker][mask] = res;
}

int solve(int sz, int c[][20]) {
    n = sz;
    memcpy(cost, c, sizeof(cost));
    memset(memo, -1, sizeof(memo));
    return dp(0, 0);
}

python

from functools import lru_cache
import sys

def solve_assignment(cost: list[list[int]]) -> int:
    """
    Bài toán phân công. Time: O(N² × 2^N), Space: O(N × 2^N)
    """
    n = len(cost)

    @lru_cache(maxsize=None)
    def dp(worker: int, mask: int) -> int:
        if worker == n:
            return 0
        min_cost = sys.maxsize
        for job in range(n):
            if not ((mask >> job) & 1):
                new_cost = cost[worker][job] + dp(worker + 1, mask | (1 << job))
                min_cost = min(min_cost, new_cost)
        return min_cost

    return dp(0, 0)

java

public int solveAssignment(int[][] cost) {
    int n = cost.length;
    int[][] memo = new int[n][1 << n];
    for (int[] row : memo) Arrays.fill(row, -1);
    return dp(0, 0, cost, memo, n);
}

private int dp(int worker, int mask, int[][] cost, int[][] memo, int n) {
    if (worker == n) return 0;
    if (memo[worker][mask] != -1) return memo[worker][mask];

    int res = Integer.MAX_VALUE;
    for (int job = 0; job < n; job++) {
        if (((mask >> job) & 1) == 0) {
            res = Math.min(res, cost[worker][job] + dp(worker + 1, mask | (1 << job), cost, memo, n));
        }
    }
    return memo[worker][mask] = res;
}

func solveAssignment(cost [][]int) int {
    n := len(cost)
    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, 1<<n)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    var dp func(int, int) int
    dp = func(worker, mask int) int {
        if worker == n {
            return 0
        }
        if memo[worker][mask] != -1 {
            return memo[worker][mask]
        }
        res := 1<<31 - 1
        for job := 0; job < n; job++ {
            if (mask>>job)&1 == 0 {
                val := cost[worker][job] + dp(worker+1, mask|(1<<job))
                if val < res {
                    res = val
                }
            }
        }
        memo[worker][mask] = res
        return res
    }
    return dp(0, 0)
}

TSP — Traveling Salesman Problem

State: dp(mask, last) = quãng đường ngắn nhất khi đã thăm các thành phố trong mask, kết thúc tại last.

Transition: dp(mask, last) = min{ dp(mask \ {last}, prev) + dist[prev][last] } cho mọi prev ∈ mask, prev ≠ last.

C++PythonJavaGo

cpp

int solveTSP(vector<vector<int>>& dist) {
    int n = dist.size();
    int full = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    dp[1][0] = 0; // bắt đầu từ thành phố 0

    for (int mask = 1; mask <= full; mask++) {
        for (int last = 0; last < n; last++) {
            if (dp[mask][last] == INT_MAX) continue;
            if (!((mask >> last) & 1)) continue;
            for (int next = 0; next < n; next++) {
                if ((mask >> next) & 1) continue;
                int newMask = mask | (1 << next);
                dp[newMask][next] = min(dp[newMask][next],
                                        dp[mask][last] + dist[last][next]);
            }
        }
    }

    int ans = INT_MAX;
    for (int last = 0; last < n; last++) {
        if (dp[full][last] != INT_MAX)
            ans = min(ans, dp[full][last] + dist[last][0]);
    }
    return ans;
}

python

from functools import lru_cache
import sys

def solve_tsp(dist: list[list[int]]) -> int:
    """
    TSP bằng Bitmask DP. Time: O(N² × 2^N), Space: O(N × 2^N)
    Xuất phát và kết thúc tại thành phố 0.
    """
    n = len(dist)

    @lru_cache(maxsize=None)
    def dp(mask: int, last: int) -> int:
        if mask == (1 << n) - 1:
            return dist[last][0]
        min_cost = sys.maxsize
        for nxt in range(n):
            if not ((mask >> nxt) & 1):
                new_cost = dist[last][nxt] + dp(mask | (1 << nxt), nxt)
                min_cost = min(min_cost, new_cost)
        return min_cost

    return dp(1, 0)  # Bắt đầu từ thành phố 0

java

public int solveTSP(int[][] dist) {
    int n = dist.length, full = (1 << n) - 1;
    int[][] dp = new int[1 << n][n];
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
    dp[1][0] = 0;

    for (int mask = 1; mask <= full; mask++) {
        for (int last = 0; last < n; last++) {
            if (dp[mask][last] == Integer.MAX_VALUE) continue;
            if (((mask >> last) & 1) == 0) continue;
            for (int next = 0; next < n; next++) {
                if (((mask >> next) & 1) == 1) continue;
                int nm = mask | (1 << next);
                dp[nm][next] = Math.min(dp[nm][next],
                                         dp[mask][last] + dist[last][next]);
            }
        }
    }

    int ans = Integer.MAX_VALUE;
    for (int last = 0; last < n; last++)
        if (dp[full][last] != Integer.MAX_VALUE)
            ans = Math.min(ans, dp[full][last] + dist[last][0]);
    return ans;
}

func solveTSP(dist [][]int) int {
    n := len(dist)
    full := (1 << n) - 1
    const INF = 1<<31 - 1

    dp := make([][]int, 1<<n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = INF
        }
    }
    dp[1][0] = 0

    for mask := 1; mask <= full; mask++ {
        for last := 0; last < n; last++ {
            if dp[mask][last] == INF || (mask>>last)&1 == 0 {
                continue
            }
            for nxt := 0; nxt < n; nxt++ {
                if (mask>>nxt)&1 == 1 {
                    continue
                }
                nm := mask | (1 << nxt)
                if val := dp[mask][last] + dist[last][nxt]; val < dp[nm][nxt] {
                    dp[nm][nxt] = val
                }
            }
        }
    }

    ans := INF
    for last := 0; last < n; last++ {
        if dp[full][last] != INF {
            if v := dp[full][last] + dist[last][0]; v < ans {
                ans = v
            }
        }
    }
    return ans
}

Gosper's Hack — Duyệt tập con cùng kích thước

Khi cần duyệt tất cả tập con có đúng k phần tử trong N phần tử, thay vì duyệt toàn bộ 2^N mask rồi kiểm tra popcount, Gosper's hack sinh trực tiếp mask tiếp theo cùng số bit 1:

python

def gosper_hack(n: int, k: int):
    """Duyệt tất cả mask N bit có đúng k bit bật."""
    mask = (1 << k) - 1  # mask nhỏ nhất: k bit thấp bật
    limit = 1 << n
    while mask < limit:
        yield mask
        c = mask & (-mask)          # bit thấp nhất đang bật
        r = mask + c                # tắt nhóm bit thấp liên tiếp
        mask = (((r ^ mask) >> 2) // c) | r

Thực chiến

Tình huống: Lập lịch giao hàng tối ưu

Bối cảnh: Đội logistics có 1 xe tải cần giao hàng đến 12 điểm trong thành phố, rồi quay về kho. Ma trận khoảng cách giữa các điểm đã biết. Tìm lộ trình ngắn nhất (TSP).

Mục tiêu: Tối ưu quãng đường, tiết kiệm nhiên liệu và thời gian.

python

def optimize_delivery_route(
    depot: int,
    distances: list[list[int]],
    location_names: list[str]
) -> tuple[int, list[str]]:
    """
    Tối ưu lộ trình giao hàng bằng TSP + traceback.
    depot: index của kho (điểm xuất phát/kết thúc)
    """
    n = len(distances)
    INF = float('inf')
    full = (1 << n) - 1

    # dp[mask][last] = min distance
    dp = [[INF] * n for _ in range(1 << n)]
    parent = [[-1] * n for _ in range(1 << n)]
    dp[1 << depot][depot] = 0

    for mask in range(1, 1 << n):
        for last in range(n):
            if dp[mask][last] == INF:
                continue
            if not ((mask >> last) & 1):
                continue
            for nxt in range(n):
                if (mask >> nxt) & 1:
                    continue
                new_mask = mask | (1 << nxt)
                new_dist = dp[mask][last] + distances[last][nxt]
                if new_dist < dp[new_mask][nxt]:
                    dp[new_mask][nxt] = new_dist
                    parent[new_mask][nxt] = last

    # Tìm điểm cuối tối ưu
    best_dist, best_last = INF, -1
    for last in range(n):
        total = dp[full][last] + distances[last][depot]
        if total < best_dist:
            best_dist = total
            best_last = last

    # Traceback route
    route = []
    mask, cur = full, best_last
    while cur != -1:
        route.append(location_names[cur])
        prev = parent[mask][cur]
        mask = mask ^ (1 << cur) if prev != -1 else mask
        cur = prev
    route.reverse()
    route.append(location_names[depot])

    return best_dist, route

Phân tích:

Với 12 điểm: 2¹² × 12 × 12 ≈ 590K operations — chạy dưới 1 giây
Brute-force: 12! ≈ 479 triệu — chậm hơn 800 lần
Trade-off: cần O(N × 2^N) memory, nhưng time giảm đáng kể

Sai lầm điển hình

❌ Sai lầm 1: Quên kiểm tra bit trước khi dùng

Vấn đề: Duyệt mà không kiểm tra phần tử đã có trong mask chưa.

python

# SAI: Không check → thêm phần tử đã có
for job in range(n):
    new_mask = mask | (1 << job)  # Nếu job đã trong mask, mask không đổi!
    dp[new_mask][...] = ...       # Cập nhật sai: job được "lấy lại"

Tại sao sai: mask | (1 << job) khi job đã bật sẽ cho kết quả bằng chính mask. Vòng lặp không tạo state mới mà ghi đè state cũ — dẫn đến kết quả sai âm thầm.

python

# ĐÚNG: Luôn check trước khi thao tác
for job in range(n):
    if (mask >> job) & 1 == 0:  # Chỉ xét job CHƯA được giao
        new_mask = mask | (1 << job)
        # ...

❌ Sai lầm 2: Dùng bitmask khi N > 20

Vấn đề: Áp dụng Bitmask DP cho N=25 và thắc mắc tại sao MLE/TLE.

python

# SAI: N=25 → 2^25 = 33 triệu states × N = 800 triệu operations
dp = [[0] * 25 for _ in range(1 << 25)]  # ~3.2 GB RAM!

Tại sao sai: Memory: 2²⁵ × 25 × 4 bytes ≈ 3.2 GB. Time: 25² × 2²⁵ ≈ 20 tỷ operations. Cả hai đều không khả thi. Giải pháp: Meet in the Middle (chia đôi tập, mỗi nửa ≤ 12-13) hoặc heuristic approach.

python

# ĐÚNG: Kiểm tra giới hạn trước khi code
if n > 20:
    # Dùng approach khác: meet in the middle, approximation, heuristic
    raise ValueError(f"N={n} quá lớn cho Bitmask DP")

❌ Sai lầm 3: Nhầm TSP với Assignment Problem

Vấn đề: TSP yêu cầu quay về điểm xuất phát, Assignment thì không.

python

# SAI: Quên cộng khoảng cách quay về depot trong TSP
if mask == full_mask:
    return 0  # Assignment: đúng. TSP: SAI!

# ĐÚNG cho TSP:
if mask == full_mask:
    return dist[last][0]  # Quay về thành phố xuất phát

Tại sao sai: TSP là chu trình Hamilton (quay về gốc), Assignment là phân công 1-1 (không cần quay về). Base case khác nhau dẫn đến kết quả khác hoàn toàn.

Under the Hood

Hiệu năng

Bài toán	Brute-force	Bitmask DP	N thực tế
Assignment	O(N!)	O(N² × 2^N)	N ≤ 20
TSP	O(N!)	O(N² × 2^N)	N ≤ 20
Hamiltonian Path	O(N!)	O(N² × 2^N)	N ≤ 20
SOS DP	O(3^N)	O(N × 2^N)	N ≤ 22

So sánh cụ thể:

N	N!	N² × 2^N	Speedup
10	3.6M	102K	35×
15	1.3 × 10¹²	7.4M	175,000×
20	2.4 × 10¹⁸	419M	5.7 × 10⁹×

Memory Footprint

Bitmask DP tiêu tốn memory đáng kể:

dp[2^N][N] với int32:
  N=15: 2^15 × 15 × 4 bytes ≈ 1.9 MB   ✓
  N=18: 2^18 × 18 × 4 bytes ≈ 18.9 MB   ✓
  N=20: 2^20 × 20 × 4 bytes ≈ 80 MB     ⚠️
  N=22: 2^22 × 22 × 4 bytes ≈ 369 MB    ❌

Kỹ thuật nâng cao — Profile DP

Khi bitmask biểu diễn "trạng thái theo cột" (ví dụ: lát gạch domino, bảng nhị phân), ta gọi là Profile DP. State là mask biểu diễn profile của cột hiện tại, transition kiểm tra compatibility với cột trước.

Trade-offs

Yếu tố	Bitmask DP	Brute-force	Heuristic/Approx
Kết quả	Chính xác	Chính xác	Xấp xỉ
Time	O(N² × 2^N)	O(N!)	O(N² ~ N³)
Memory	O(N × 2^N)	O(N)	O(N²)
N tối đa	~20	~12	~10⁶
Use case	Competitive/exact	Tiny N	Production/large N

Checklist ghi nhớ

✅ Checklist triển khai

Nhận diện bài toán

[ ] N nhỏ (≤ 20) + tối ưu trên tập con/hoán vị → Bitmask DP
[ ] "Phân công 1-1" → Assignment Problem pattern
[ ] "Thăm tất cả đỉnh + quay về" → TSP pattern
[ ] "Đếm đường đi qua tất cả đỉnh" → Hamiltonian Path

Thiết kế state

[ ] Xác định mask biểu diễn gì (tập con đã chọn/đã thăm)
[ ] Cần thêm chiều nào ngoài mask? (last, worker_id, current position)
[ ] Base case: mask rỗng? mask đầy? mask chỉ 1 phần tử?

Phép bitwise

[ ] Kiểm tra bit: (mask >> j) & 1
[ ] Bật bit: mask | (1 << j)
[ ] Tắt bit: mask & ~(1 << j) hoặc mask ^ (1 << j)
[ ] Full mask: (1 << N) - 1
[ ] Duyệt submask: sub = (sub - 1) & mask

Tối ưu hóa

[ ] Kiểm tra N ≤ 20 trước khi dùng Bitmask DP
[ ] N > 20 → Meet in the Middle (chia đôi)
[ ] Dùng __builtin_popcount (C++) hoặc bit_count() (Python 3.10+)
[ ] Bỏ qua state không reachable (dp[mask][last] == INF)

Bài tập luyện tập

Bài 1: Assignment Problem — Intermediate

Đề bài: 3 nhân viên, 3 công việc. Ma trận chi phí:

cost = [[9, 2, 7],
        [6, 4, 3],
        [5, 8, 1]]

Tìm phân công tổng chi phí nhỏ nhất.

🧠 Quiz

Câu hỏi kiểm tra: Tổng chi phí tối thiểu là?

[ ] A. 7
[x] B. 9
[ ] C. 11
[ ] D. 12 Giải thích: Phân công tối ưu: Người 0→Việc 1 (2), Người 1→Việc 0 (6), Người 2→Việc 2 (1). Tổng = 2+6+1 = 9. Các phân công khác đều cho chi phí cao hơn.

💡 Gợi ý

State: dp(worker, mask) — mask là tập các việc đã giao
Người 0 chọn trước, rồi người 1, rồi người 2
N=3 nhỏ, có thể trace bằng tay

✅ Lời giải

python

cost = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]
print(solve_assignment(cost))  # 9

Phân tích: 3² × 2³ = 72 operations. Phân công: {0→1, 1→0, 2→2}.

Bài 2: TSP nhỏ — Intermediate

Đề bài: 4 thành phố với ma trận khoảng cách. Tìm tour ngắn nhất từ thành phố 0 và quay về.

dist = [[0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]]

🧠 Quiz

Câu hỏi kiểm tra: Tour ngắn nhất có độ dài?

[x] A. 80
[ ] B. 85
[ ] C. 90
[ ] D. 75 Giải thích: Tour: 0→1→3→2→0 (10+25+30+15 = 80). Đây là optimal — thử các hoán vị khác đều cho kết quả lớn hơn.

✅ Lời giải

python

dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
print(solve_tsp(dist))  # 80

Phân tích: 4² × 2⁴ = 256 operations. Tour: 0→1→3→2→0.

Bài 3: Gosper's Hack Application — Advanced

Đề bài: Cho mảng N=8 số nguyên. Tìm tập con có đúng 3 phần tử có tổng lớn nhất.

💡 Gợi ý

Dùng Gosper's hack để duyệt tất cả C(8,3) = 56 tập con 3 phần tử
Nhanh hơn duyệt 2⁸ = 256 mask rồi filter popcount

✅ Lời giải

python

def max_sum_k_subset(nums: list[int], k: int) -> int:
    n = len(nums)
    mask = (1 << k) - 1
    limit = 1 << n
    best = float('-inf')
    while mask < limit:
        total = sum(nums[i] for i in range(n) if (mask >> i) & 1)
        best = max(best, total)
        c = mask & (-mask)
        r = mask + c
        mask = (((r ^ mask) >> 2) // c) | r
    return best

nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_sum_k_subset(nums, 3))  # 20 (5+9+6)

Phân tích: Chỉ duyệt C(8,3)=56 mask thay vì 256. Với N lớn hơn, tiết kiệm đáng kể.

Liên kết học tiếp

Từ khóa glossary: bitmask DP, traveling salesman problem, TSP, assignment problem, Hamiltonian path, Gosper's hack, subset enumeration, SOS DP, profile DP, bit manipulation, combinatorial optimization

Tìm kiếm liên quan: DP bitmask, bài toán người bán hàng, phân công tối ưu, duyệt tập con, thao tác bit, tối ưu tổ hợp

Bitmask DP — Quy hoạch động trên tập con ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Các phép bitwise nền tảng ​

Assignment Problem — Bài toán phân công ​

TSP — Traveling Salesman Problem ​

Gosper's Hack — Duyệt tập con cùng kích thước ​

Thực chiến ​

Tình huống: Lập lịch giao hàng tối ưu ​

Sai lầm điển hình ​

❌ Sai lầm 1: Quên kiểm tra bit trước khi dùng ​

❌ Sai lầm 2: Dùng bitmask khi N > 20 ​

❌ Sai lầm 3: Nhầm TSP với Assignment Problem ​

Under the Hood ​

Hiệu năng ​

Memory Footprint ​

Kỹ thuật nâng cao — Profile DP ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Assignment Problem — Intermediate ​

Bài 2: TSP nhỏ — Intermediate ​

Bài 3: Gosper's Hack Application — Advanced ​

Liên kết học tiếp ​

Bitmask DP — Quy hoạch động trên tập con

Bức tranh tư duy

Cốt lõi kỹ thuật

Các phép bitwise nền tảng

Assignment Problem — Bài toán phân công

TSP — Traveling Salesman Problem

Gosper's Hack — Duyệt tập con cùng kích thước

Thực chiến

Tình huống: Lập lịch giao hàng tối ưu

Sai lầm điển hình

❌ Sai lầm 1: Quên kiểm tra bit trước khi dùng

❌ Sai lầm 2: Dùng bitmask khi N > 20

❌ Sai lầm 3: Nhầm TSP với Assignment Problem

Under the Hood

Hiệu năng

Memory Footprint

Kỹ thuật nâng cao — Profile DP

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Assignment Problem — Intermediate

Bài 2: TSP nhỏ — Intermediate

Bài 3: Gosper's Hack Application — Advanced

Liên kết học tiếp