पहले, हम बिटमास्किंग और डायनामिक प्रोग्रामिंग के बारे में सीखेंगे फिर हम इससे संबंधित एक समस्या हल करेंगे जो कार्यान्वयन से संबंधित आपके प्रश्नों को हल करेगी।
बिटमास्क जिसे मास्क के रूप में भी जाना जाता है, N-बिट्स का एक क्रम है जो हमारे संग्रह के उपसमुच्चय को एन्कोड करता है। मास्क का तत्व या तो सेट या अनसेट हो सकता है (यानी 0 या 1)। यह बिटमास्क में चुने गए तत्व की उपलब्धता को दर्शाता है। उदाहरण के लिए, एक तत्व i उपसमुच्चय में उपलब्ध है यदि मास्क का iवां बिट सेट है। N तत्वों के सेट के लिए, 2^N मास्क हो सकते हैं जिनमें से प्रत्येक एक उपसमुच्चय से मेल खाता है।
तो, समस्या को हल करने के लिए, हम एक मास्क यानी एक उपसमुच्चय के लिए शुरू करेंगे, इसे एक मान निर्दिष्ट करेंगे और फिर पिछले मास्क के मानों का उपयोग करके आगे के मास्क के मान ढूंढेंगे। इसका उपयोग करके हम अंततः मुख्य सेट का मान गणना करने में सक्षम होंगे।
एक मास्क के लिए इष्टतम समाधान की गणना करने के लिए, हम सभी संभावित तरीकों से एक तत्व को हटाएंगे और उन सभी मानों की गणना करेंगे जो अंतिम समाधान में योगदान देंगे।
डायनामिक प्रोग्रामिंग
डायनामिक प्रोग्रामिंग एक अनुकूलन विधि है जिसमें हम उपसमस्याओं को हल करते हैं और उनके समाधानों को अन्य ओवरलैपिंग उपसमस्याओं में उपयोग के लिए संग्रहीत करते हैं।
अब, आइए एक समस्या देखें जिसे हम बिट मास्किंग और डायनामिक प्रोग्रामिंग का उपयोग करके हल करेंगे।
समस्या
1 से 50 तक संख्या वाली 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 के रूप में होना चाहिए क्योंकि तरीकों की संख्या एक बड़ी संख्या हो सकती है।
इस समस्या को हल करने का एक सरल समाधान लोगों द्वारा टोपी पहनने के सभी संभावित संयोजन ढूंढना है। पहले सेट से शुरू करके शेष सेट्स को पुनरावृत्त करना। लेकिन यह समाधान अनुकूलित नहीं है।
एक बेहतर समाधान 10 व्यक्तियों के लिए आकार 2^10 का मास्क और आकार 51 का टोपी वेक्टर बनाकर बिटमास्किंग और DP का उपयोग करना है। फिर, हम तरीकों की संख्या में पुनरावृति करेंगे।
कार्यक्रम उदाहरण
#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;
// व्यक्ति 1 का संग्रह
caps[4].push_back(0);
caps[45].push_back(0);
caps[10].push_back(0);
// व्यक्ति 2 का संग्रह
caps[25].push_back(1);
// व्यक्ति 3 का संग्रह
caps[45].push_back(2);
caps[10].push_back(2);
allmask = (1 << n) - 1;
memset(dp, -1, sizeof dp);
cout << "पार्टी में लोग अद्वितीय टोपी पहनने के तरीकों की संख्या:\t" << uniqueCaps(0, 1);
return 0;
}
आउटपुट
पार्टी में लोग अद्वितीय टोपी पहनने के तरीकों की संख्या: 4
