सबसे पहले, हम बिटमास्किंग और डायनेमिक प्रोग्रामिंग के बारे में जानेंगे, फिर हम इससे संबंधित एक समस्या का समाधान करेंगे जो कार्यान्वयन से संबंधित आपके प्रश्नों का समाधान करेगी।
बिटमास्क मास्क . के रूप में भी जाना जाता है एन-बिट्स का एक क्रम है जो हमारे संग्रह के सबसेट को एन्कोड करता है। मुखौटा का तत्व या तो सेट किया जा सकता है या सेट नहीं किया जा सकता है (यानी 0 या 1)। यह बिटमास्क में चुने हुए तत्व की उपलब्धता को दर्शाता है। उदाहरण के लिए, एक तत्व i सबसेट में उपलब्ध है यदि मास्क का ith बिट सेट है। N तत्व सेट के लिए, एक 2 N . हो सकता है प्रत्येक उपसमुच्चय के अनुरूप मुखौटा।
इसलिए, समस्या को हल करने के लिए, हम एक मास्क के लिए शुरू करेंगे यानी एक सबसेट इसे एक मान प्रदान करता है और फिर पिछले मास्क के मूल्यों का उपयोग करके आगे के मास्क के लिए मान ढूंढता है। इसका उपयोग करके हम अंततः मुख्य सेट के मूल्य की गणना करने में सक्षम होंगे।
एक मुखौटा के लिए इष्टतम समाधान की गणना करने के लिए, हम सभी संभावित तरीकों से एक तत्व को हटा देंगे और उन सभी मूल्यों की गणना करेंगे जो अंतिम समाधान में योगदान देंगे।
डायनामिक प्रोग्रामिंग
गतिशील प्रोग्रामिंग एक अनुकूलन विधि है जिसमें हम उप-समस्याओं को हल करते हैं और अन्य अतिव्यापी उप-समस्याओं में उपयोग के लिए उनके समाधान संग्रहीत करते हैं।
अब, एक समस्या देखते हैं जिसे हम बिट मास्किंग और डायनेमिक प्रोग्रामिंग का उपयोग करके हल करेंगे
समस्या
1 से 50 तक की संख्या के साथ 50 कैप हैं। एन लोगों के संग्रह में इनमें से कुछ कैप हैं। एक दिन सभी ने एक पार्टी के लिए टोपी पहन रखी है। लेकिन सभी को अद्वितीय दिखने की जरूरत है, इसलिए उन्होंने अलग-अलग नंबर वाली टोपी पहनने का फैसला किया। हमें लोगों की संख्या और उनके संग्रह में कैप नंबर दिए गए हैं। हमारा काम उन तरीकों की कुल संख्या का पता लगाना है जिसमें वे टोपी पहन सकते हैं ताकि हर कोई अद्वितीय दिखे।
समस्या में, पहली पंक्ति में मान n यानी लोगों की संख्या है। अगली n पंक्तियों में उनका संग्रह है।
इनपुट -
3 4 45 10 25 45 10
आउटपुट -
4
स्पष्टीकरण -
सभी संभावित तरीके हैं (4, 25, 45) , (4, 25, 10), (45, 25, 10), (10, 25, 45)।
आउटपुट 1000000007 के रूप में होना चाहिए क्योंकि तरीकों की संख्या एक बड़ी संख्या हो सकती है।
इस समस्या को हल करने के लिए, कैप्स का उपयोग करने वाले लोगों के सभी संभावित संयोजनों को ढूंढना एक आसान समाधान है। पहले सेट से शुरू करें और शेष सेटों की पुनरावृत्ति करें। लेकिन यह समाधान अनुकूलित नहीं है।
10 व्यक्तियों के लिए 210 आकार का मास्क बनाकर बिटमास्किंग और डीपी का उपयोग करना एक बेहतर समाधान है। और 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