C++-এ বিটমাস্কিং এবং ডাইনামিক প্রোগ্রামিং

প্রথমে আমরা বিটমাস্কিং এবং ডাইনামিক প্রোগ্রামিং সম্পর্কে জানব তারপর একটি সম্পর্কিত সমস্যা সমাধান করব যা আপনার ইমপ্লিমেন্টেশন सम्बन्धী প্রশ্নের সমাধান করবে।

বিটমাস্ক যাকে মাস্ক ও বলা হয়, N-বিটের একটি সিকোয়েন্স যা আমাদের কালেকশনের সাবসেটকে এনকোড করে। মাস্কের এলিমেন্ট বা সেট হতে পারে বা না (অর্থাৎ 0 বা 1)। এটি বিটমাস্কে বেছে নেওয়া এলিমেন্টের উপলব্ধতা নির্দেশ করে। উদাহরণস্বরূপ, একটি এলিমেন্ট i সাবসেটে উপলব্ধ যদি মাস্কের i-তম বিট সেট থাকে। N এলিমেন্টের সেটের জন্য 2^Nটি মাস্ক থাকতে পারে যারা প্রতিটি একটি সাবসেটের সাথে মিলে।

সমস্যা সমাধানের জন্য, আমরা একটি মাস্ক অর্থাৎ একটি সাবসেট থেকে শুরু করব, এটিকে একটি মান অ্যাসাইন করব এবং তারপর আগের মাস্কের মান ব্যবহার করে পরবর্তী মাস্কগুলোর মান বের করব। এর মাধ্যমে আমরা 最終 সেটের মান ক্যালকুলেট করতে পারব।

একটি মাস্কের জন্য অপ্টিমাল সমাধান ক্যালকুলেট করতে, আমরা সব সম্ভাব্যভাবে একটি এলিমেন্ট সরিয়ে মানগুলো ক্যালকুলেট করব যা ফাইনাল সমাধানে অবদান রাখবে।

ডাইনামিক প্রোগ্রামিং

ডাইনামিক প্রোগ্রামিং হচ্ছে একটি অপ্টিমাইজেশন মেথড যেখানে আমরা সাবপ্রব্লেম সমাধান করি এবং তাদের সমাধান স্টোর করি অন্য ওভারল্যাপিং সাবপ্রব্লেমে ব্যবহার করার জন্য।

এখন, একটি সমস্যা দেখি যা আমরা বিট মাস্কিং এবং ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করব।

সমস্যা

১ থেকে ৫০ নম্বর পর্যন্ত ৫০টি ক্যাপ আছে। N জন মানুষের কাছে এই ক্যাপগুলোর কিছু আছে। একদিন সবাই একটি পার্টিতে ক্যাপ পories। কিন্তু সবাই অনন্য দেখতে চান তাই তারা সিদ্ধান্ত নেন প্রত্যেকে আলাদা নম্বরের ক্যাপ পরবে। আমাদের দেওয়া আছে n জন মানুষের সংখ্যা এবং তাদের কালেকশনে ক্যাপের নম্বর। আমাদের কাজ হলো কতভাবে তারা ক্যাপ পরতে পারে যেন সবাই অনন্য দেখে।

সমস্যায়, প্রথম লাইনে n মান আছে অর্থাৎ মানুষের সংখ্যা। পরবর্তী n লাইনে তাদের কালেকশন।

ইনপুট −

3 
4 45 10 
25 45 10

আউটপুট −

4

ব্যাখ্যা −

সম্ভাব্য সব পদ্ধতি হচ্ছে (4, 25, 45) , (4, 25, 10), (45, 25, 10), (10, 25, 45)।

আউটপুট 1000000007 মডুলো দিতে হবে কারণ পদ্ধতির সংখ্যা বড় হতে পারে।

এই সমস্যা সমাধানের একটি সহজ সমাধান হচ্ছে মানুষের ক্যাপ ব্যবহার করে সব সম্ভাব্য কম্বিনেশন বের করা। প্রথম সেট থেকে শুরু করে বাকি সেটগুলো রিকার্শন করা। কিন্তু এই সমাধান অপ্টিমাইজড নয়।

একটি ভালো সমাধান হচ্ছে বিটমাস্কিং এবং 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; 
    // Person 1's collection 
    caps[4].push_back(0); 
    caps[45].push_back(0); 
    caps[10].push_back(0); 
    // Person 2's collection 
    caps[25].push_back(1); 
    // Person 3's collection 
    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