ขั้นแรก เราจะเรียนรู้เกี่ยวกับบิตมาสก์และการเขียนโปรแกรมแบบไดนามิก จากนั้นเราจะแก้ปัญหาที่เกี่ยวข้องซึ่งจะแก้ปัญหาการสืบค้นของคุณที่เกี่ยวข้องกับการใช้งาน
บิตมาสก์ หรือที่เรียกว่า หน้ากาก เป็นลำดับของ N-bits ที่เข้ารหัสชุดย่อยของคอลเล็กชันของเรา องค์ประกอบของมาสก์สามารถตั้งค่าหรือไม่ตั้งค่าก็ได้ (เช่น 0 หรือ 1) นี่แสดงถึงความพร้อมใช้งานขององค์ประกอบที่เลือกในบิตมาสก์ ตัวอย่างเช่น อิลิเมนต์ i จะพร้อมใช้งานในเซ็ตย่อย ถ้าบิตของมาสก์ถูกตั้งค่าไว้ สำหรับชุดองค์ประกอบ N สามารถมีได้ 2 N มาสก์แต่ละรายการที่สอดคล้องกับเซตย่อย
ดังนั้น ในการแก้ปัญหา เราจะเริ่มใช้มาสก์ นั่นคือ เซตย่อยกำหนดค่าแล้วค้นหาค่าสำหรับมาสก์เพิ่มเติมโดยใช้ค่าของมาสก์ก่อนหน้า เมื่อใช้สิ่งนี้เราจะสามารถคำนวณมูลค่าของชุดหลักได้ในที่สุด
ในการคำนวณวิธีแก้ปัญหาที่เหมาะสมที่สุดสำหรับมาสก์ เราจะลบหนึ่งองค์ประกอบในทุกวิถีทางที่เป็นไปได้ และคำนวณค่าทั้งหมดที่จะนำไปสู่การแก้ปัญหาขั้นสุดท้าย
การเขียนโปรแกรมแบบไดนามิก
การเขียนโปรแกรมแบบไดนามิกเป็นวิธีการปรับให้เหมาะสมที่เราแก้ปัญหาย่อยและจัดเก็บโซลูชันสำหรับการใช้งานในปัญหาย่อยที่ทับซ้อนกันอื่นๆ
ตอนนี้ มาดูปัญหาที่เราจะแก้ไขโดยใช้ bit masking และ dynamic programming
ปัญหา
มี 50 ตัวพิมพ์ใหญ่ที่มีตัวเลขตั้งแต่ 1 ถึง 50 คน N มีตัวพิมพ์ใหญ่บางส่วนในคอลเล็กชันของพวกเขา วันหนึ่งพวกเขาทั้งหมดสวมหมวกเพื่อไปงานเลี้ยง แต่ทุกคนต้องดูมีเอกลักษณ์ ดังนั้นพวกเขาจึงตัดสินใจสวมหมวกที่มีหมายเลขต่างกัน เราได้รับจำนวน n คนและหมายเลขหมวกในคอลเล็กชันของพวกเขา งานของเราคือค้นหาจำนวนวิธีที่พวกเขาสามารถสวมหมวกเพื่อให้ทุกคนดูมีเอกลักษณ์
ในปัญหา บรรทัดแรกมีค่า n นั่นคือ จำนวนคน n บรรทัดถัดไปมีคอลเล็กชันของพวกเขา
ป้อนข้อมูล −
3 4 45 10 25 45 10
ผลผลิต −
4
คำอธิบาย −
วิธีที่เป็นไปได้ทั้งหมดคือ (4, 25, 45) , (4, 25, 10), (45, 25, 10), (10, 25, 45)
ผลลัพธ์ควรอยู่ในรูปแบบ 1000000007 เนื่องจากจำนวนวิธีอาจเป็นจำนวนมากได้
ในการแก้ปัญหานี้ วิธีแก้ไขง่ายๆ คือค้นหากลุ่มคนที่เป็นไปได้ทั้งหมดโดยใช้ตัวพิมพ์ใหญ่ เริ่มตั้งแต่เซ็ตแรกและเซ็ตที่เหลือซ้ำ แต่โซลูชันนี้ไม่ได้รับการปรับให้เหมาะสม
ทางออกที่ดีกว่าคือการใช้ Bitmasking และ DP โดยการสร้างมาสก์ขนาด 210 สำหรับ 10 คน และเวกเตอร์ตัวพิมพ์ใหญ่ขนาด 51 จากนั้น จะเกิดขึ้นซ้ำในหลายๆ วิธี
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชัน −
#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;
} ผลลัพธ์
The number of ways the person can wear unique cap in party is: 4
