প্রথমে, আমরা বিটমাস্কিং এবং ডাইনামিক প্রোগ্রামিং সম্পর্কে শিখব তারপর আমরা এর সাথে সম্পর্কিত একটি সমস্যা সমাধান করব যা বাস্তবায়ন সম্পর্কিত আপনার প্রশ্নের সমাধান করবে।
বিটমাস্ক মাস্ক নামেও পরিচিত N -bits এর একটি ক্রম যা আমাদের সংগ্রহের উপসেটকে এনকোড করে। মুখোশের উপাদান হয় সেট বা সেট করা যাবে না (যেমন 0 বা 1)। এটি বিটমাস্কে নির্বাচিত উপাদানের প্রাপ্যতা নির্দেশ করে। উদাহরণস্বরূপ, ith বিট অফ মাস্ক সেট করা থাকলে উপসেটে একটি উপাদান i পাওয়া যায়। N উপাদান সেটের জন্য, একটি 2 N থাকতে পারে প্রতিটি উপসেটের সাথে সম্পর্কিত মাস্ক করুন।
সুতরাং, সমস্যা সমাধানের জন্য, আমরা একটি মুখোশের জন্য শুরু করব অর্থাৎ একটি উপসেট এটিকে একটি মান নির্ধারণ করে এবং তারপরে পূর্ববর্তী মুখোশের মানগুলি ব্যবহার করে আরও মুখোশের মানগুলি খুঁজে বের করে। এটি ব্যবহার করে আমরা অবশেষে মূল সেটের মান গণনা করতে সক্ষম হব।
একটি মুখোশের জন্য সর্বোত্তম সমাধান গণনা করতে, আমরা সমস্ত সম্ভাব্য উপায়ে একটি উপাদান সরিয়ে ফেলব এবং সমস্ত মান গণনা করব যা চূড়ান্ত সমাধানে অবদান রাখবে৷
ডাইনামিক প্রোগ্রামিং
ডাইনামিক প্রোগ্রামিং হল একটি অপ্টিমাইজেশান পদ্ধতি যেখানে আমরা সাব-সমস্যা সমাধান করি এবং অন্যান্য ওভারল্যাপিং সাব-প্রবলেমে ব্যবহারের জন্য তাদের সমাধান সংরক্ষণ করি।
এখন, আসুন একটি সমস্যা দেখি যা আমরা বিট মাস্কিং এবং ডাইনামিক প্রোগ্রামিং ব্যবহার করে সমাধান করব
সমস্যা
1 থেকে 50 পর্যন্ত সংখ্যা সহ 50টি ক্যাপ রয়েছে। 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 জন ব্যক্তির জন্য 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
