Quy hoạch động trạng thái bit (bitmask)

Mức độ: Chuyên sâu

Có n người và n việc, người i làm việc j tốn c_ij. Phân mỗi người một việc khác nhau, tổng chi phí nhỏ nhất bao nhiêu? Thử mọi cách phân là n!, với n = 15 là khoảng 1,3 × 10¹². Nhưng khi phân lần lượt cho người 1, 2, …, điều duy nhất cần nhớ là tập các việc đã có người làm: không cần biết việc nào giao cho ai. Có 2ⁿ tập như vậy, với n = 15 chỉ khoảng 3 × 10⁴.

Tập con là một số nguyên

Tập con của các số 0, 1, …, n - 1 được viết bằng n bit: bit thứ i bằng 1 khi phần tử i có trong tập. Ví dụ với n = 4, tập gồm 0, 2, 3 là 1101 (đọc từ phải sang: bit 0, bit 1, …), tức là số 13. Các thao tác trên tập thành phép toán bit:

Thao tác	Viết bằng bit
i có trong tập S không	S >> i & 1
thêm i vào S	S | (1 << i)
bỏ i khỏi S	S & ~(1 << i)
số phần tử của S	số bit 1 của S
tập đầy đủ	(1 << n) - 1

Bài toán phân công

Gọi f[S] là chi phí nhỏ nhất khi đã phân xong cho |S| người đầu tiên (người 0, 1, …, |S| - 1) và S là tập các việc họ làm. Người tiếp theo là người thứ k = |S|, giao cho một việc j chưa có trong S. Gọi T là tập S thêm việc j:

f[T] = min(f[T], f[S] + c_kj)

Bắt đầu f[tập rỗng] = 0, đi S từ nhỏ đến lớn (số nhỏ hơn đến trước, mà T luôn lớn hơn S). Đáp số là f[tập đầy đủ]. Cả bài khoảng 2ⁿ × n bước.

Python

import sys
du_lieu = sys.stdin.read().split()
n = int(du_lieu[0])
c = [list(map(int, du_lieu[1 + i * n:1 + (i + 1) * n])) for i in range(n)]
VO_CUNG = float('inf')
f = [VO_CUNG] * (1 << n)
f[0] = 0
for S in range(1 << n):
    if f[S] == VO_CUNG:
        continue
    k = bin(S).count('1')            # người tiếp theo
    if k == n:
        continue
    for j in range(n):
        if not (S >> j & 1):         # việc j chưa có người làm
            T = S | (1 << j)
            if f[S] + c[k][j] < f[T]:
                f[T] = f[S] + c[k][j]
print(f[(1 << n) - 1])

C++

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

int main() {
    int n;
    cin >> n;
    vector<vector<long long>> c(n, vector<long long>(n));
    for (auto &hang : c)
        for (auto &x : hang) cin >> x;
    const long long VO_CUNG = 4e18;
    vector<long long> f(1 << n, VO_CUNG);
    f[0] = 0;
    for (int S = 0; S < (1 << n); S++) {
        if (f[S] == VO_CUNG) continue;
        int k = __builtin_popcount(S);       // người tiếp theo
        if (k == n) continue;
        for (int j = 0; j < n; j++)
            if (!(S >> j & 1)) {             // việc j chưa có người làm
                int T = S | (1 << j);
                f[T] = min(f[T], f[S] + c[k][j]);
            }
    }
    cout << f[(1 << n) - 1] << "\n";
    return 0;
}

Bài toán người du lịch

Đi qua mỗi thành phố đúng một lần rồi quay về chỗ cũ, quãng đường ngắn nhất. Lần này ngoài tập đã đi còn phải biết đang đứng ở đâu: g[S][i] là quãng đường ngắn nhất xuất phát từ thành phố 0, đã đi qua đúng tập S và đang đứng ở i (i thuộc S). Đi tiếp tới j chưa thuộc S, với T là S thêm j:

g[T][j] = min(g[T][j], g[S][i] + d_ij)

Đáp số là min của g[tập đầy đủ][i] + d_i0. Có 2ⁿ × n trạng thái, mỗi trạng thái thử n bước tiếp, khoảng 2ⁿ × n² bước: n = 16 là khoảng 1,7 × 10⁷.

Duyệt mọi tập con của một tập

Nhiều bài cần, với mỗi tập S, xét mọi tập con T của S. Vòng lặp sau đi qua mọi tập con khác rỗng của S theo thứ tự giảm dần:

T = S
while T > 0:
    # xử lý tập con T của S
    T = (T - 1) & S

Trừ 1 rồi AND với S cho tập con lớn nhất của S nhỏ hơn T. Duyệt như vậy cho mọi S thì tổng số bước là 3ⁿ (mỗi phần tử có ba trạng thái: không thuộc S, thuộc S nhưng không thuộc T, thuộc T).

Lưu ý: 2ⁿ tăng rất nhanh. Quy hoạch động bitmask chỉ dùng được khi n khoảng 20 trở xuống (2²⁰ khoảng 10⁶); duyệt tập con (3ⁿ) chỉ được khi n khoảng 15.

Luyện tập

Gồm 15 bài, chia thành 5 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Chọn dần từng phần tử

Bài 1. Phân công việc

Có n người và n việc. Dòng đầu có n (1 ≤ n ≤ 16), n dòng sau mỗi dòng có n số: số thứ j của dòng i là chi phí c_ij khi người i làm việc j (0 ≤ c_ij ≤ 10⁶). Mỗi người làm đúng một việc, mỗi việc đúng một người. In ra tổng chi phí nhỏ nhất.

Ví dụ:

Nhập	In ra
3 4 2 8 4 3 7 3 1 6	12

Kiểm tra: nhập

5
7 3 9 5 2
4 8 1 6 7
9 2 6 3 8
5 6 4 9 1
3 7 2 8 6

Xem đáp số

11

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Đếm cách xếp chỗ

Có n học sinh và n ghế. Học sinh i chỉ chịu ngồi một số ghế. Dòng đầu có n (1 ≤ n ≤ 16), n dòng sau mỗi dòng là xâu n ký tự 0/1: ký tự thứ j của dòng i là 1 nếu học sinh i chịu ngồi ghế j. In ra số cách xếp mỗi học sinh một ghế khác nhau mà ai cũng vừa ý.

Ví dụ:

Nhập	In ra
3 110 011 101	2

Kiểm tra: nhập

5
11100
01110
00111
10011
11001

Xem đáp số

13

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Thang máy

Có n người, người thứ i nặng w_i. Thang máy chở được tổng khối lượng không quá X mỗi chuyến. Dòng đầu có n, X (1 ≤ n ≤ 16, 1 ≤ w_i ≤ X ≤ 10⁹), dòng thứ hai có n số w_i. In ra số chuyến ít nhất để chở hết mọi người.

Ví dụ:

Nhập	In ra
4 10 4 8 6 1	2

Kiểm tra: nhập

8 20
13 7 5 9 2 11 6 8

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Thứ tự ít phàn nàn nhất

n bạn xếp thành một hàng. Nếu bạn i đứng trước bạn j (không cần liền kề) thì có c_ij lời phàn nàn. Dòng đầu có n (1 ≤ n ≤ 16), n dòng sau mỗi dòng có n số c_ij (0 ≤ c_ij ≤ 1000, c_ii = 0). In ra tổng số lời phàn nàn nhỏ nhất trên mọi cách xếp hàng.

Ví dụ:

Nhập	In ra
3 0 5 1 2 0 4 3 6 0	7

Kiểm tra: nhập

5
0 3 8 1 5
7 0 2 6 4
2 9 0 3 1
8 1 5 0 2
4 6 7 3 0

Xem đáp số

31

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Tập đã đi và vị trí hiện tại

Bài 5. Người du lịch

Có n thành phố đánh số 0 đến n - 1, khoảng cách từ i đến j là d_ij (có thể khác d_ji). Dòng đầu có n (2 ≤ n ≤ 16), n dòng sau mỗi dòng có n số (0 ≤ d_ij ≤ 10⁶, d_ii = 0). Xuất phát từ thành phố 0, đi qua mỗi thành phố đúng một lần rồi quay về 0. In ra tổng quãng đường ngắn nhất.

Ví dụ:

Nhập	In ra
4 0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0	80

Kiểm tra: nhập

5
0 3 9 7 2
4 0 6 3 8
9 5 0 2 6
7 3 4 0 5
2 8 6 1 0

Xem đáp số

16

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Đường đi qua mọi thành phố

Như bài 5 nhưng được xuất phát từ thành phố bất kỳ và không cần quay về. Dòng đầu có n (1 ≤ n ≤ 16), n dòng sau mỗi dòng có n số d_ij. In ra tổng quãng đường ngắn nhất đi qua mỗi thành phố đúng một lần.

Ví dụ:

Nhập	In ra
4 0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0	50

Kiểm tra: nhập

5
0 3 9 7 2
4 0 6 3 8
9 5 0 2 6
7 3 4 0 5
2 8 6 1 0

Xem đáp số

11

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Đếm đường đi qua mọi đỉnh

Đồ thị có hướng n đỉnh (đánh số 1 đến n) và m cạnh. Dòng đầu có n, m (2 ≤ n ≤ 15, 0 ≤ m ≤ n × (n - 1)), m dòng sau mỗi dòng có u, v: cạnh một chiều từ u đến v (không có cạnh lặp). In ra số đường đi từ đỉnh 1 đến đỉnh n đi qua mỗi đỉnh đúng một lần.

Ví dụ:

Nhập	In ra
4 6 1 2 1 3 2 3 3 2 2 4 3 4	2

Kiểm tra: nhập

5 12
1 2
1 3
1 4
2 3
3 2
2 4
4 2
3 4
4 3
2 5
3 5
4 5

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Thu thập kho báu

Bản đồ là bảng h hàng, w cột gồm . (đi được), # (tường), S (vị trí xuất phát, có đúng một), T (kho báu, có không quá 10). Mỗi bước đi sang ô chung cạnh. Dòng đầu có h, w (1 ≤ h, w ≤ 50), h dòng sau là bản đồ. In ra số bước ít nhất để nhặt hết kho báu (thứ tự tùy ý, không cần quay về), hoặc -1 nếu không nhặt được hết.

Ví dụ:

Nhập	In ra
3 5 S..T. .#.#. T...T	9

Kiểm tra: nhập

5 6
S.#..T
..#.#.
T...#.
.##...
...T.T

Xem đáp số

13

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Duyệt tập con

Bài 9. Bữa tiệc không ai ghét nhau

Có n người, m cặp ghét nhau. Mời nhiều người nhất có thể sao cho không có hai người ghét nhau cùng được mời. Dòng đầu có n, m (1 ≤ n ≤ 20, 0 ≤ m ≤ n × (n - 1) / 2), m dòng sau mỗi dòng có u, v (1 ≤ u, v ≤ n, u khác v). In ra số người nhiều nhất được mời.

Ví dụ:

Nhập	In ra
5 5 1 2 2 3 3 4 4 5 5 1	2

Kiểm tra: nhập

8 10
1 2
1 3
2 4
3 4
4 5
5 6
6 7
7 8
8 5
2 6

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Chia nhóm hợp nhau nhất

Có n bạn, mỗi cặp bạn i, j có độ hợp nhau a_ij (có thể âm). Chia n bạn thành các nhóm (số nhóm tùy ý, mỗi bạn đúng một nhóm). Điểm của cách chia là tổng a_ij trên mọi cặp i, j cùng nhóm. Dòng đầu có n (1 ≤ n ≤ 13), n dòng sau mỗi dòng có n số (a_ij = a_ji, a_ii = 0, |a_ij| ≤ 10⁶). In ra điểm lớn nhất.

Ví dụ:

Nhập	In ra
3 0 3 -1 3 0 2 -1 2 0	4

Kiểm tra: nhập

5
0 4 -2 1 -3
4 0 5 -1 2
-2 5 0 3 -4
1 -1 3 0 6
-3 2 -4 6 0

Xem đáp số

13

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Ít người nhất đủ mọi kỹ năng

Dự án cần k kỹ năng đánh số 0 đến k - 1. Có n ứng viên, mỗi người có một số kỹ năng. Dòng đầu có n, k (1 ≤ n ≤ 100, 1 ≤ k ≤ 16), n dòng sau: dòng thứ i bắt đầu bằng số c rồi c kỹ năng của người i. In ra số người ít nhất cần tuyển để đủ cả k kỹ năng, hoặc -1 nếu không thể.

Ví dụ:

Nhập	In ra
4 3 1 0 2 0 1 1 2 2 1 2	2

Kiểm tra: nhập

6 5
2 0 1
2 1 2
2 3 4
1 4
3 0 2 4
2 1 3

Xem đáp số

2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Tổng trên tập con

Bài 12. Tổng trên mọi tập con

Dòng đầu có k (1 ≤ k ≤ 20), dòng thứ hai có 2^k số nguyên a₀, …, a_{2^k - 1} (|a_i| ≤ 10⁶). Với mỗi S từ 0 đến 2^k - 1, tính b_S = tổng a_T qua mọi T là tập con của S (mọi bit của T đều có trong S). In ra b₀, …, b_{2^k - 1}.

Ví dụ:

Nhập	In ra
2 1 2 3 4	1 3 4 10

Kiểm tra: nhập

3
5 -1 2 0 3 7 -4 1

Xem đáp số

5 4 7 6 8 14 6 13

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Cặp số không chung bit

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i nhỏ hơn 2²⁰). In ra số cặp vị trí i đứng trước j mà a_i AND a_j = 0.

Ví dụ:

Nhập	In ra
4 1 2 3 4	4

Kiểm tra: nhập

8
0 5 10 3 12 0 7 8

Xem đáp số

18

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 5. Quy hoạch động theo hàng

Bài 14. Lát gạch domino

Bảng có n hàng, m cột. Đếm số cách lát kín bảng bằng các viên gạch 1 × 2 (đặt ngang hoặc dọc, không chồng lên nhau, không thừa ra ngoài). Dòng duy nhất có n, m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 8). In ra số cách, chia lấy dư 10⁹ + 7.

Ví dụ: nhập 2 3 thì in ra 3.

Kiểm tra: nhập 10 6.

Xem đáp số

4213133

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Đặt vua không ăn nhau

Bảng n hàng, m cột. Đặt các quân vua vào một số ô sao cho không có hai quân nào kề nhau (chung cạnh hoặc chung góc). Dòng duy nhất có n, m (1 ≤ n ≤ 100, 1 ≤ m ≤ 10). In ra số cách đặt (kể cả không đặt quân nào), chia lấy dư 10⁹ + 7.

Ví dụ: nhập 2 2 thì in ra 5.

Kiểm tra: nhập 8 8.

Xem đáp số

355115594

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.