Bitmasking และ Dynamic Programming ใน C++

ก่อนอื่น เราจะเรียนรู้เกี่ยวกับ Bitmasking และ Dynamic Programming แล้วค่อยแก้ปัญหาที่เกี่ยวข้อง ซึ่งจะช่วยแก้ข้อสงสัยเกี่ยวกับการนำไปใช้

Bitmask หรือที่เรียกว่า mask คือลำดับของ N-bits ที่เข้ารหัส subset ของคอลเลกชันของเรา องค์ประกอบของ mask สามารถเป็น set หรือ not set (เช่น 0 หรือ 1) ซึ่งแสดงถึงความพร้อมใช้งานขององค์ประกอบที่เลือกใน bitmask เช่น องค์ประกอบ i พร้อมใช้งานใน subset หากบิตที่ i ของ mask ถูก set สำหรับเซต N องค์ประกอบ สามารถมี mask ได้ 2^N ตัว แต่ละตัวตรงกับ subset หนึ่ง

ดังนั้น เพื่อแก้ปัญหา เราจะเริ่มจาก mask หนึ่งตัว คือ subset หนึ่ง กำหนดค่าให้มัน แล้วหาค่าสำหรับ mask ต่อไปโดยใช้ค่าของ mask ก่อนหน้า ด้วยวิธีนี้ เราจะสามารถคำนวณค่าของเซตหลักได้ในที่สุด

เพื่อคำนวณคำตอบที่เหมาะสมที่สุดสำหรับ mask เราจะเอาองค์ประกอบออกทีละตัวในทุกวิธีที่เป็นไปได้ และคำนวณค่าทั้งหมด ซึ่งจะมีส่วนช่วยให้ได้คำตอบสุดท้าย

Dynamic Programming

Dynamic programming เป็นวิธีการเพิ่มประสิทธิภาพที่เราแก้ subproblem และเก็บคำตอบของพวกมันไว้เพื่อนำไปใช้ใน subproblem อื่นๆ ที่ทับซ้อนกัน

ตอนนี้ มาดูปัญหาที่เราจะแก้โดยใช้ 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)

เอาต์พุตควรเป็นในรูปแบบ modulo 1000000007 เนื่องจากจำนวนวิธีอาจเป็นตัวเลขใหญ่

วิธีง่ายคือหาการจัดหมู่ทั้งหมดของคนที่สวมหมวก เริ่มจากเซตแรกและ recurrence เซตที่เหลือ แต่วิธีนี้ไม่ได้รับการเพิ่มประสิทธิภาพ

วิธีที่ดีกว่าคือใช้ Bitmasking และ DP โดยสร้าง mask ขนาด 2^10 สำหรับ 10 คน และ vector ของหมวกขนาด 51 แล้วเราจะ recurrence หาจำนวนวิธี

ตัวอย่างโปรแกรม

#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