এই টিউটোরিয়ালে একটি সমস্যা আলোচনা করা হয়েছে যেখানে পূর্ণসংখ্যার একটি অ্যারে দেওয়া আছে। আমাদের সবচেয়ে বড় সাবসেট বের করতে হবে যাতে সাবসেটের প্রতিটি জোড়ার (pair) জন্য বড় সংখ্যাটি ছোট সংখ্যাটি দিয়ে বিভাজ্য হয়। উদাহরণ −
ইনপুট: nums[] = { 1, 4, 2, 6, 7 } আউটপুট: 1 2 4 ব্যাখ্যা: সব বিভাজ্য সাবসেট: (1, 2, 4), (1, 2, 6), (1, 7) ইত্যাদি। দৈর্ঘ্য ৩-এর ২টি সাবসেট আছে।
ইনপুট: nums[] = { 1, 2, 3, 6 } আউটপুট: 6 2 1
এই টিউটোরিয়ালে দুটি ভিন্ন পদ্ধতি ব্যাখ্যা করা হয়েছে।
সহজ পদ্ধতিতে রিকার্সন (recursion) প্রয়োগ করা যায়। প্রতিটি উপাদানের জন্য দুটি অপশন: সাবসেটে রাখবো বা রাখবো না। প্রথম উপাদান নিলে, দ্বিতীয় উপাদান রাখতে হলে সেটি প্রথম উপাদান দিয়ে বিভাজ্য বা ভাগ করতে হবে। এইভাবে পুরো অ্যারে ট্রাভার্স করলে 2^n পাথ (path) বने, টাইম কমপ্লেক্সিটি O(2^n)। এখন একটি সম্ভাব্য পদ্ধতি দেখি।
এই সমস্যাতেই ডাইনামিক প্রোগ্রামিং (Dynamic Programming) প্রয়োগ করে দক্ষ সমাধান করা যায়।
অ্যারেটি সর্ট (sort) করি যাতে বামের এলিমেন্ট ডানের 엘িমেন্ট দিয়ে বিভাজ্য হয় কিনা একবার চেক করলেই হয়।
Longest Increasing Subsequence (LIS)-এর মতো dp[] অ্যারে ব্যবহার করি যেটি i-তম ইনডেক্স পর্যন্ত সবচেয়ে বড় বিভাজ্য সাবসেট রাখে। প্রতিটি ইনডেক্স ১ দিয়ে ইনিশিয়ালাইজ (প্রতিটি উপাদান নিজে নিজে দিয়ে বিভাজ্য)।
২য় ইনডেক্স থেকে ট্রাভার্স করে প্রতিটি উপাদানের জন্য সর্বোচ্চ বিভাজ্য সাবসেট বের করি যেটি বর্তমান ইনডেক্সে শেষ হয়।
অ্যারে ট্রাভার্স করে প্রতিটি উপাদানের জন্য এমন ভাজক (divisor) খুঁজি যেকোনো সর্বোচ্চ বিভাজ্য কাউন্ট থাকে। এবং বর্তমান ইনডেক্সের ভ্যালু সেটি + ১ করি।
উপরোক্ত পদ্ধতির C++ কোড
#include<bits/stdc++.h> using namespace std; int main(){ int nums[] = {1, 2, 3, 6}; int n = sizeof(nums)/sizeof(int); // অ্যারে সর্ট করে এক শর্ত বাদ দেওয়া sort(nums, nums+n); vector <int> prev_res(n, -1); // ভাজক রাখার ভেক্টর vector <int> dp(n, 1); // dp অ্যারে, ১ দিয়ে ইনিশিয়ালাইজ int max = 1; for (int i=1; i<n; i++){ // i-তম উপাদানের ভাজক j-তম ইনডেক্সে আছে কিনা for (int j=0; j<i; j++){ if (nums[i] % nums[j] == 0){ // ভাজক পেলে if (dp[i] < dp[j] + 1){ // সাবসিকোয়েন্স বাড়লে dp[i] = dp[j] + 1; prev_res[i] = j; } } } if(max < dp[i]) max = dp[i]; // সর্বোচ্চ সাবসেট সাইজ } cout << "Largest divisible subset in the array: "; // সর্বোচ্চ সাবসেট প্রিন্ট int k = max; while (k >= 0){ cout << nums[k] << " "; k = prev_res[k]; } return 0; }
Largest divisible subset in the array: 6 2 1
এই টিউটোরিয়ালে আমরা একটি সমস্যা আলোচনা করেছি: দিয়ে হয়ে অ্যারেতে সবচেয়ে বড় বিভাজ্য সাবসেট বের করা যেখানে প্রতিটি জোড়ায় বড় সংখ্যা ছোট সংখ্যা দিয়ে বিভাজ্য। রিকার্সন থেকে এক্সপোনেনশিয়াল টাইম কমপ্লেক্সিটি পাওয়া যায়, তাই ডাইনামিক প্রোগ্রামিং সমাধান দেওয়া হয়েছে। এই সমস্যার C++ প্রোগ্রামও দেওয়া আছে যা C, Java, Python ইত্যাদি ভাষায়ও করা যাবে। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।
