Quy hoạch động trên tập con bằng bitmask

Lan cần giao ba công việc cho ba bạn. Mỗi bạn làm đúng một việc, nhưng chi phí phụ thuộc cả bạn lẫn việc. Nếu thử cả 3! = 6 cách, Lan tìm được đáp án. Với 15 bạn, số cách tăng lên hơn một nghìn tỉ. Bài này lưu lại kết quả của những tập công việc đã xét để tránh tính lặp.

Một số nguyên ghi lại tập công việc đã dùng

Mặt nạ bit (bitmask) dùng một bit cho mỗi phần tử. Bit i bằng 1 nghĩa là công việc i đã được chọn. Bit thấp nhất ứng với chỉ số 0. Ví dụ với bốn công việc, 0b0101 biểu diễn tập {0, 2}, không phải {1, 3}.

Thứ tự ô trong hình đi từ chỉ số nhỏ đến lớn. Ký hiệu nhị phân trong Python viết bit cao ở bên trái, nên 0b0101 được đọc từ phải sang trái khi gán chỉ số.

mask = 0b0101
i = 1
print((mask >> i) & 1)
added = mask | (1 << i)
print(bin(added), added.bit_count())
print(bin(added & ~(1 << 2)))

0
0b111 3
0b11

Đoạn mã kiểm tra việc 1, thêm việc 1 rồi bỏ việc 2. Phép | bật bit ngay cả khi bit đó đã bật. Phép & với ~ chỉ tắt bit chỉ định. Trái lại, cộng 1 << i khi bit đã bật có thể làm nhớ sang bit khác. Hàm bit_count() đếm bit 1, không cộng các chỉ số.

Với n việc, có 1 << n tập khác nhau. Tập rỗng là 0; tập đầy đủ là (1 << n) - 1. Chương trình sau cho thấy khoảng giá trị và sự tăng nhanh của số trạng thái.

for n in (3, 10, 15, 20):
    print(n, 1 << n, (1 << n) - 1)

3 8 7
10 1024 1023
15 32768 32767
20 1048576 1048575

Cùng một tập công việc có thể gộp nhiều cách phân công

Giả sử bạn xử lý người theo thứ tự 0, 1, ..., n-1. Với cùng tập việc đã dùng, hai lịch sử phân công có thể có chi phí khác nhau. Các việc còn lại và người tiếp theo lại giống nhau. Vì vậy, để tìm tổng nhỏ nhất, bạn chỉ cần giữ chi phí nhỏ hơn của hai lịch sử đó.

Trạng thái (state) dp[mask] là chi phí nhỏ nhất khi giao đúng các việc trong mask cho mask.bit_count() người đầu tiên. Các người này đã nhận mỗi người đúng một việc. Không thể suy ra ai nhận việc nào chỉ từ mask; ta giữ chi phí tốt nhất trong mọi cách như vậy.

Ví dụ ba người có các hàng chi phí dưới đây. Công việc là các cột 0, 1, 2. Giá trị âm có thể diễn tả một khoản giảm chi phí; thuật toán vẫn áp dụng.

cost = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]
for person, row in enumerate(cost):
    print(person, *row)

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

Đầu tiên dp[0] = 0, vì chưa giao việc nào thì chi phí bằng 0. Các trạng thái khác khởi tạo bằng vô cực, tức chưa tìm được cách đi tới. Với một mask chưa đầy, đặt person = mask.bit_count(). Thử từng việc job có bit chưa bật, rồi cập nhật dp[mask | (1 << job)] bằng chi phí tốt nhất.

3
9 2 7
6 4 3
5 8 1

n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]
dp = [float('inf')] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
    person = mask.bit_count()
    if person == n:
        continue
    for job in range(n):
        if not (mask & (1 << job)):
            nxt = mask | (1 << job)
            dp[nxt] = min(dp[nxt], dp[mask] + cost[person][job])
print(dp[-1])

9

Kết quả ứng với người 0 nhận việc 1, người 1 nhận việc 0 và người 2 nhận việc 2. Cần so sánh các cách khác trước khi kết luận, vì việc rẻ nhất cho người đầu có thể cản người sau.

Hình sau liệt kê chi phí tốt nhất sau khi xét các trạng thái. Cột mask dùng ba chữ số nhị phân, với công việc 0 ở bên phải.

Hãy đọc riêng trạng thái 011. Hai việc 0 và 1 đã được giao cho hai người đầu tiên. Một cách giao có chi phí 9 + 4 = 13. Cách còn lại đổi hai việc, có chi phí 2 + 6 = 8. Bảng giữ 8 vì cả hai cách đều để lại cùng việc 2 cho người tiếp theo. Từ đó, thêm việc 2 tạo ứng viên 8 + 1 = 9 cho trạng thái đầy đủ.

Một trạng thái có thể nhận nhiều ứng viên từ những tập trước khác nhau. Chẳng hạn, tập đầy đủ cũng nhận ứng viên khi việc cuối là 0 hoặc 1. Không được ghi đè tùy ý: cần so sánh ứng viên mới với giá trị đang lưu. Bảng được tính dần, nên giá trị tạm thời có thể giảm khi một chuyển tốt hơn xuất hiện.

Để thấy tại sao chọn rẻ nhất từng hàng có thể thất bại, xét bảng hai người sau. Nếu người đầu lấy việc 0 vì giá 1, người sau phải trả 100. Giao việc 1 cho người đầu để người sau nhận việc 0 sẽ tốt hơn nhiều.

cost = [[1, 2], [1, 100]]
print(cost[0][0] + cost[1][1])
print(cost[0][1] + cost[1][0])

101
3

Giá trị dp[mask] chỉ đủ vì người được xử lý theo thứ tự cố định. Nếu đề có điều kiện phụ thuộc chính xác người nào đã làm việc nào, hai lịch sử cùng tập việc có thể không tương đương. Khi đó cần bổ sung thông tin trạng thái hoặc chọn cách mô hình hóa khác.

Bất biến (invariant) là ý nghĩa được giữ đúng trong quá trình tính. Giả sử dp[mask] đã là chi phí nhỏ nhất cho tập đó. Bất kỳ cách hợp lệ nào tới tập mới đều có một việc cuối được giao cho người tiếp theo. Khi xét việc cuối đó, ta kết hợp chi phí tốt nhất của tập trước với chi phí mới. Lấy nhỏ nhất trên tất cả việc cuối nên không bỏ sót cách tối ưu.

Mỗi lần bật thêm một bit đang tắt, số nguyên của mặt nạ tăng. Vì vậy duyệt mask tăng dần đảm bảo trạng thái trước được xử lý trước trạng thái sau. Điều kiện này phụ thuộc hướng chuyển; không nên áp dụng máy móc cho mọi dạng DP.

Có 2^n trạng thái và tối đa n lựa chọn mỗi trạng thái, nên thời gian là O(n * 2^n), bộ nhớ O(2^n). Với n = 15, cận trên là 491 520 lần xét việc. Với n = 20, cận trên vượt 20 triệu lần xét; thời gian Python còn phụ thuộc máy và giới hạn chấm. Danh sách Python cũng tốn nhiều hơn một byte cho mỗi ô, nên cần đo trước khi chọn n lớn.

Cận trên này tính cả những lần vòng lặp gặp việc đã dùng và bỏ qua. Số lần chuyển thực sự ít hơn, nhưng cùng bậc tăng theo n * 2^n. Bạn không nên kết luận rằng n = 20 chạy kịp chỉ vì số ô khoảng một triệu. Hãy tính cả số vòng lặp, kích thước dữ liệu, giới hạn bộ nhớ và thời gian của máy chấm. Với tập rỗng, phép đếm bit cho người 0; với tập đầy, nó cho n, nên không truy cập hàng thứ n.

Với n = 0 trong bài toán cho phép tập rỗng, trạng thái gốc cũng là trạng thái đầy. Khi đó chi phí phân công rỗng là 0 và có một cách ghép rỗng. Các bài thực hành dưới đây quy định n từ 1 để tập trung vào các chuyển trạng thái.

Bỏ chuyển trạng thái giúp biểu diễn việc không thể giao

Giả sử một số người không đủ điều kiện làm một số việc. Ta dùng bảng allowed, trong đó 1 là được phép. Đừng gán chi phí 0 cho việc bị cấm, vì như vậy thuật toán sẽ tưởng đó là lựa chọn rẻ.

allowed = [[1, 0], [1, 0]]
n = len(allowed)
ways = [0] * (1 << n)
ways[0] = 1
for mask in range(1 << n):
    i = mask.bit_count()
    if i == n:
        continue
    for j in range(n):
        if allowed[i][j] and not mask & (1 << j):
            ways[mask | (1 << j)] += ways[mask]
print(ways[-1])

0

Ở đây hai người chỉ được nhận cùng việc 0, nên không có cách ghép đầy đủ. ways[mask] đếm số cách, thay vì lưu chi phí nhỏ nhất. Trạng thái rỗng có đúng một cách: chưa giao việc nào. Mỗi cách ở mask cộng vào mỗi trạng thái kế tiếp hợp lệ.

Một cách ghép đầy đủ được đếm đúng một lần. Lý do là thứ tự xét người cố định, nên tập việc của từng tiền tố và việc vừa thêm đều được xác định. Nếu đề yêu cầu lấy dư, cập nhật với % mod; không dùng một số dư cụ thể khi đề không yêu cầu.

allowed = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
n = len(allowed)
ways = [0] * (1 << n)
ways[0] = 1
for mask in range(1 << n):
    i = mask.bit_count()
    if i < n:
        for j in range(n):
            if allowed[i][j] and not mask & (1 << j):
                ways[mask | (1 << j)] += ways[mask]
print(ways[-1])

3

Chi phí thời gian và bộ nhớ có cùng số trạng thái và số chuyển như bài phân công. Khác biệt nằm ở phép gộp: đếm dùng cộng, tối ưu dùng min. Với bài tối ưu có cặp bị cấm, giữ float('inf') cho trạng thái chưa tới được và kiểm tra đáp án cuối trước khi in.

Xét thêm hai trường hợp biên. Nếu chỉ có một người và cặp duy nhất được phép, số cách là 1. Nếu cặp duy nhất bị cấm, số cách là 0. Trong cả hai trường hợp, không đặt đáp án của tập rỗng theo số người. Giá trị gốc 1 mô tả một lịch sử rỗng, còn kết quả cuối do các chuyển hợp lệ quyết định.

for allowed in ([[1]], [[0]]):
    ways = [1, 0]
    if allowed[0][0]:
        ways[1] += ways[0]
    print(ways[1])

1
0

Đếm cách và kiểm tra khả thi có liên quan nhưng khác mục tiêu. Nếu chỉ cần biết có cách hay không, bạn có thể lưu giá trị đúng hoặc sai cho từng tập. Còn khi đề hỏi số cách, chỉ lưu đúng hoặc sai sẽ làm mất số lịch sử khác nhau. Python hỗ trợ số nguyên lớn, nhưng phép cộng trên số rất lớn vẫn có chi phí thực tế.

Đường đi cần nhớ cả tập điểm lẫn điểm cuối

Lan giao hàng qua các điểm 0, 1, 2. Cùng tập {0, 1, 2}, đường đi kết thúc ở 1 có thể có giá khác đường đi kết thúc ở 2. Giá để đi tiếp cũng phụ thuộc điểm cuối. Vì vậy một giá trị dp[mask] không đủ mô tả thông tin cần dùng.

Đặt dp[mask][last] là chi phí nhỏ nhất của đường đi bắt đầu ở 0, thăm đúng các điểm trong mask một lần và kết thúc tại last. Trạng thái gốc là dp[1][0] = 0. Với mọi nxt chưa thăm, cộng cost[last][nxt] rồi cập nhật trạng thái mới.

Hai trạng thái cuối khác nhau dù có cùng tập đã thăm. Trong mã sau, cost[u][v] là giá đi trực tiếp từ u đến v. Bảng có thể bất đối xứng; đi từ u sang v không bắt buộc có cùng giá chiều ngược lại.

cost = [[0, 2, 9], [1, 0, 3], [4, 6, 0]]
n = len(cost)
inf = float('inf')
dp = [[inf] * n for _ in range(1 << n)]
dp[1][0] = 0
for mask in range(1 << n):
    for last in range(n):
        if dp[mask][last] == inf:
            continue
        for nxt in range(n):
            if not mask & (1 << nxt):
                new = mask | (1 << nxt)
                dp[new][nxt] = min(dp[new][nxt], dp[mask][last] + cost[last][nxt])
print(min(dp[-1]))

5

Đường đi tốt nhất kết thúc ở một điểm bất kỳ, nên lấy nhỏ nhất trong hàng đầy đủ. Không cộng giá trở về 0 nếu đề không yêu cầu. Nếu đề yêu cầu quay về, lấy nhỏ nhất của dp[full][last] + cost[last][0] trên các điểm cuối hợp lệ.

Với mỗi đường đi có ít nhất hai điểm, bỏ điểm cuối sẽ thu được một đường đi hợp lệ của trạng thái trước. Thuật toán xét mọi điểm cuối trước đó và giữ chi phí nhỏ nhất, nên tìm được đường đi tối ưu. Có tối đa n * 2^n trạng thái, mỗi trạng thái thử tối đa n điểm tiếp theo. Thời gian là O(n^2 * 2^n) và bộ nhớ là O(n * 2^n). Với n = 15, cận trên khoảng 7,4 triệu lượt xét, và có gần nửa triệu ô trạng thái.

cost = [[0]]
dp = [[float('inf')] for _ in range(2)]
dp[1][0] = 0
print(min(dp[-1]))

0

Trường hợp một điểm cho kết quả 0 vì điểm xuất phát đã là điểm duy nhất. Khi một cạnh không tồn tại, cần bỏ chuyển đó và giữ trạng thái bất khả thi. Chi phí âm vẫn hợp lệ vì mỗi bước thêm một điểm mới, không thể đi vòng lặp vô hạn.

Trong trạng thái đường đi, last phải thuộc mask. Ngoài ra, mọi trạng thái đạt được đều chứa điểm xuất phát 0. Các ô còn lại được giữ ở vô cực; không nên xem chúng là đường đi thực. Kiểm tra vô cực trước khi chuyển giúp mã dễ đọc và tránh tạo ứng viên từ đường không tồn tại.

Một sai lầm Python đáng chú ý là tạo bảng bằng [[inf] * n] * (1 << n). Phép nhân danh sách ngoài sao chép tham chiếu, không tạo các hàng độc lập. Nếu đổi một ô, ô cùng cột của các hàng khác cũng đổi. Biểu thức [[inf] * n for _ in range(1 << n)] tạo hàng riêng cho từng tập.

inf = float('inf')
dp = [[inf] * 2 for _ in range(4)]
dp[1][0] = 0
print(dp[0][0])
print(dp[1][0])

inf
0

Nếu cần in chính đường đi, bạn có thể lưu điểm trước đó mỗi khi tìm được chi phí tốt hơn. Sau khi chọn điểm cuối tối ưu, lần ngược các trạng thái và đảo thứ tự điểm. Mảng lưu vết tốn thêm O(n * 2^n) bộ nhớ. Nếu chỉ cần chi phí, không cần cấp phát mảng đó.

Có thể dùng mask để chọn đội đủ kỹ năng

Một đội cần ba kỹ năng đánh số từ 0 đến 2. Mỗi ứng viên có chi phí và một số kỹ năng; hãy chọn đội đủ cả ba với chi phí nhỏ nhất. Khác bài phân công, mặt nạ ở đây ghi tập kỹ năng đã có, không ghi tập người được chọn. Bài 30 giới thiệu cách xét mỗi đối tượng một lần trong bài toán ba lô.

Sau khi xét một số ứng viên, dp[mask] là chi phí nhỏ nhất để có đúng tập kỹ năng mask. Ban đầu chỉ tập rỗng đạt được với chi phí 0. Mỗi ứng viên có mặt nạ skill và chi phí c. Bạn giữ phương án bỏ qua người đó, hoặc chọn người đó và cập nhật tập mask | skill.

k = 3
people = [(4, [0, 1]), (3, [1, 2]), (2, [2])]
inf = float('inf')
dp = [inf] * (1 << k)
dp[0] = 0
for cost, skills in people:
    skill = 0
    for i in skills:
        skill |= 1 << i
    new_dp = dp.copy()
    for mask in range(1 << k):
        new = mask | skill
        new_dp[new] = min(new_dp[new], dp[mask] + cost)
    dp = new_dp
print(dp[-1] if dp[-1] != inf else -1)

6

Hai ứng viên đầu có đủ kỹ năng với tổng chi phí 7. Ứng viên đầu kết hợp người thứ ba có giá 6, nên chương trình chọn phương án sau. Nếu không ai có một kỹ năng cần thiết, trạng thái đầy vẫn là vô cực và kết quả là -1.

Phép | gộp kỹ năng trùng mà không cộng hai lần. Khi ứng viên không có kỹ năng mới, mask | skill có thể bằng mask. Đoạn mã tạo new_dp riêng, nên mỗi lần xét chỉ dùng một ứng viên tối đa một lần. Sau mỗi ứng viên, mọi đội hợp lệ được chia thành hai nhóm: có chọn hoặc không chọn người đó. Hai nhánh cập nhật bao quát cả hai nhóm và giữ chi phí nhỏ nhất.

Với chi phí không âm, duyệt mask tăng và cập nhật tại chỗ cũng cho cùng giá trị tối ưu. Nếu một trạng thái mới lại dùng cùng người đó, phép OR lần nữa không thêm kỹ năng; chi phí không giảm. Lý do này không áp dụng nếu chi phí âm: chọn lặp có thể giảm giá giả tạo. Dùng bảng riêng vẫn thể hiện quy tắc chọn mỗi người tối đa một lần rõ ràng hơn.

Với n ứng viên và k kỹ năng, có 2^k trạng thái và xét mỗi trạng thái cho từng ứng viên. Thời gian là O(n * 2^k) và bộ nhớ là O(2^k), chưa kể danh sách đầu vào. Với n = 100, k = 12, có tối đa 409 600 lượt chuyển.

Lỗi thường gặp

Tóm tắt

Mặt nạ lưu tập đã dùng. bit_count() xác định người tiếp theo khi thứ tự xử lý người cố định. Chọn ý nghĩa trạng thái, giá trị gốc và phép gộp trước khi viết vòng lặp. Đường đi cần thêm điểm cuối vì tập đã thăm chưa quyết định chi phí đi tiếp. Số trạng thái tăng theo 2^n, nên cần đối chiếu giới hạn thời gian và bộ nhớ.

Kiểm tra nhanh

Đọc thêm

• Python: phép toán bit và int.bit_count.
• AtCoder Educational DP Contest: Matching.