Trước tiên tìm hiểu về bitmasking và quy hoạch động, sau đó giải bài toán liên quan để hiểu triển khai.
Bitmask (mặt nạ bit) là dãy N-bit mã hóa tập con của tập hợp. Mỗi bit trong mask hoặc được set (1) hoặc không (0), biểu thị sự hiện diện của phần tử trong tập con. Phần tử i có trong tập con nếu bit thứ i của mask = 1. Với N phần tử, có 2ᴺ mask tương ứng 2ᴺ tập con.
Để giải bài toán, bắt đầu từ một mask (tập con), gán giá trị, rồi tính giá trị cho các mask lớn hơn dùng giá trị mask nhỏ hơn. Cuối cùng tính được giá trị của tập hợp đầy đủ.
Để tính giải pháp tối ưu cho một mask, loại bỏ từng phần tử theo mọi cách, tính giá trị, dùng để đóng góp vào giải pháp cuối.
Quy hoạch động (Dynamic Programming)
Phương pháp tối ưu hóa: giải bài toán con, lưu kết quả để dùng cho các bài toán con chồng chéo.
Bài toán
Có 50 mũ có số 1..50. N người mỗi người có một số mũ. Một ngày tất cả đi tiệc, mỗi người đội một mũ, yêu cầu số mũ khác nhau. Cho số người N và danh sách mũ của mỗi người. Tìm số cách đội mũ sao cho mọi người khác nhau.
Dòng đầu: N. N dòng tiếp theo: bộ sưu tập mũ của mỗi người.
Đầu vào** –
3 4 45 10 25 45 10
Đầu ra** –
4
Giải thích** – Các cách: (4,25,45), (4,25,10), (45,25,10), (10,25,45).
Kết quả modulo 1000000007.
Cách đơn giản: sinh tất cả tổ hợp, đệ quy. Không tối ưu.
Cách tốt hơn: Bitmasking + DP. Mask kích thước 2¹⁰ cho 10 người. Vector mũ kích thước 51. Đệ quy với memoization.
Ví dụ
Chương trình triển khai:**
#include<bits/stdc++.h>
using namespace std;
vector<int> caps[101];
int dp[1025][101];
int allmask;
long long int uniqueCaps(int mask, int i) {
if (mask == allmask) return 1;
if (i > 100) return 0;
if (dp[mask][i] != -1) return dp[mask][i];
long long int ways = uniqueCaps(mask, i+1);
int size = caps[i].size();
for (int j = 0; j < size; j++) {
if (mask & (1 << caps[i][j])) continue;
else ways += uniqueCaps(mask | (1 << caps[i][j]), i+1);
ways %= (1000000007);
}
return dp[mask][i] = ways;
}
int main() {
int n = 3;
// Người 1
caps[4].push_back(0);
caps[45].push_back(0);
caps[10].push_back(0);
// Người 2
caps[25].push_back(1);
// Người 3
caps[45].push_back(2);
caps[10].push_back(2);
allmask = (1 << n) - 1;
memset(dp, -1, sizeof dp);
cout << "The number of ways the person can wear unique cap in party is:\t" << uniqueCaps(0, 1);
return 0;
}
Đầu ra
The number of ways the person can wear unique cap in party is: 4