Đầu tiên, chúng ta sẽ tìm hiểu về bitmasking và lập trình động, sau đó chúng ta sẽ giải quyết một vấn đề liên quan đến nó để giải quyết các truy vấn của bạn liên quan đến việc triển khai.
Bitmask còn được gọi là mặt nạ là một chuỗi N -bit mã hóa tập hợp con của bộ sưu tập của chúng ta. Phần tử của mặt nạ có thể được đặt hoặc không được đặt (tức là 0 hoặc 1). Điều này biểu thị tính khả dụng của phần tử đã chọn trong bitmask. Ví dụ, một phần tử i có sẵn trong tập hợp con nếu bit thứ i của mặt nạ được đặt. Đối với tập hợp N phần tử, có thể có 2 N mỗi mặt nạ tương ứng với một tập hợp con.
Vì vậy, để giải quyết vấn đề, chúng ta sẽ bắt đầu cho một mặt nạ, tức là một tập hợp con gán cho nó một giá trị và sau đó tìm các giá trị cho các mặt nạ khác bằng cách sử dụng các giá trị của mặt nạ trước đó. Sử dụng điều này, cuối cùng chúng tôi sẽ có thể tính toán giá trị của tập hợp chính.
Để tính toán giải pháp tối ưu cho mặt nạ, chúng tôi sẽ loại bỏ một phần tử theo tất cả các cách có thể và tính toán tất cả các giá trị mà sau đó sẽ đóng góp vào giải pháp cuối cùng.
Lập trình động
Lập trình động là một phương pháp tối ưu hóa trong đó chúng tôi giải quyết vấn đề con và lưu trữ các giải pháp của chúng để sử dụng trong vấn đề con chồng chéo khác.
Bây giờ, hãy xem một vấn đề mà chúng ta sẽ giải quyết bằng cách sử dụng lập trình động và lập trình mặt nạ bit
Sự cố
Có 50 cái mũ với các số từ 1 đến 50. Người N có một số cái mũ này trong bộ sưu tập của họ. Một ngày nọ, tất cả bọn họ đều đội mũ lưỡi trai đi dự tiệc. Nhưng tất cả đều cần phải trông độc đáo, họ quyết định đội những chiếc mũ được đánh số khác nhau. Chúng tôi được cung cấp số người n và số giới hạn trong bộ sưu tập của họ. Nhiệm vụ của chúng tôi là tìm tổng số cách họ có thể đội mũ lưỡi trai để mọi người trông thật độc đáo.
Trong bài toán, dòng đầu tiên chứa giá trị n tức là số người. N dòng tiếp theo chứa bộ sưu tập của họ.
Đầu vào -
3 4 45 10 25 45 10
Đầu ra -
4
Giải thích -
Tất cả các cách có thể là (4, 25, 45), (4, 25, 10), (45, 25, 10), (10, 25, 45).
Đầu ra phải ở dạng 1000000007 vì số lượng cách có thể là một số lớn.
Để giải quyết vấn đề này, một giải pháp đơn giản là tìm tất cả các kết hợp có thể có của những người sử dụng mũ. Bắt đầu từ bộ đầu tiên và lặp lại các bộ còn lại. Nhưng giải pháp này không được tối ưu hóa.
Một giải pháp tốt hơn là sử dụng Bitmasking và DP bằng cách tạo một mặt nạ có kích thước 210 cho 10 người. Và một vectơ có mũ có kích thước 51. Sau đó, chúng tôi sẽ lặp lại theo một số cách.
Ví dụ
Chương trình hiển thị việc triển khai giải pháp -
#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;
// Collection of person 1
caps[4].push_back(0);
caps[45].push_back(0);
caps[10].push_back(0);
// Collection of person 2
caps[25].push_back(1);
// Collection of person 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