एक समस्या को हल करने के लिए जिसमें हमें अलग-अलग तत्वों से बनी एक सरणी दी गई है। अब हमारा कार्य वह उपसमुच्चय ढूंढना है जैसे कि प्रत्येक जोड़ा समान रूप से विभाज्य हो, यानी, प्रत्येक बड़ा तत्व प्रत्येक छोटे तत्व से विभाज्य हो, उदाहरण के लिए।
इनपुट: arr[] = {10, 5, 3, 15, 20} आउटपुट: 3 व्याख्या: सबसे बड़ा उपसमुच्चय है 10, 5, 20। 10, 5 से विभाज्य है, और 20, 10 से विभाज्य है। इनपुट: arr[] = {18, 1, 3, 6, 13, 17} आउटपुट: 4 व्याख्या: सबसे बड़ा उपसमुच्चय है 18, 1, 3, 6, उपअनुक्रम में, 3, 1 से विभाज्य है, 6, 3 से और 18, 6 से।हम इस समस्या का उत्तर खोजने के लिए डायनामिक प्रोग्रामिंग लागू करेंगे, और हम देखेंगे कैसे।
समाधान खोजने का दृष्टिकोण
इस दृष्टिकोण में, हम अपनी सरणी को आरोही क्रम में सॉर्ट करने जा रहे हैं। अब हम सरणी के अंत से शुरू करके पार करेंगे। अब हम एक dp सरणी बनाए रखेंगे जिसमें ith तत्व के सबसे छोटे होने पर सबसे बड़े उपसमुच्चय का आकार होगा। फिर हम अपने dp सरणी से अधिकतम मान लौटाएंगे।
उदाहरण
#include <bits/stdc++.h> using namespace std; int largestSubsetPair(int *a, int n){ int dp[n]; // यह ith इंडेक्स से शुरू होने वाले सबसे बड़े उपसमुच्चय का आकार रखेगा dp[n - 1] = 1; // चूंकि अंतिम तत्व सबसे बड़ा है इसलिए इसका उपसमुच्चय आकार 1 है int largest = 0; // उत्तर for (int i = n - 2; i >= 0; i--) { int maxi = 0; // मैक्स = 0 लेना; for (int j = i + 1; j < n; j++) if (a[j] % a[i] == 0 || a[i] % a[j] == 0) maxi = max(maxi, dp[j]); // यदि a[j], a[i] से विभाज्य है //तो a[j] से विभाज्य सभी तत्वों को भी फॉलो करना चाहिए dp[i] = 1 + maxi; largest = max(largest, dp[i]); } return largest; } int main(){ int a[] = { 1, 3, 6, 13, 17, 18 }; // दी गई सरणी int n = sizeof(a) / sizeof(int); // हमारी सरणी का आकार cout << largestSubsetPair(a, n) << "\n"; return 0; }आउटपुट
4
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम डायनामिक प्रोग्रामिंग का उपयोग करके समस्या को हल करते हैं। सबसे पहले, हम अपनी सरणी को सॉर्ट करते हैं। अब चूंकि हमने अपनी सरणी को सॉर्ट किया है, अब हमने एक सरणी dp बनाई जो पिछले सभी सबसे बड़े उपसमुच्चय को स्टोर करेगी।
अब हम अपनी सरणी के अंत से शुरू करते हैं इसमें। हम पहले मान लेते हैं कि हमारा वर्तमान तत्व न्यूनतम है और आगे अन्य गुणकों की जांच करते हैं अब जैसे ही हम इसके आगे एक गुणक का सामना करते हैं। हम रिवर्स में यात्रा कर रहे हैं, इसलिए इसका मतलब है कि हमने उस तत्व का पहले सामना किया है। हमने उनके सबसे बड़े उपसमुच्चय का आकार अपनी dp सरणी के अंदर भी सहेजा है। अब हम इस तत्व को अपने वर्तमान तत्व के dp में जोड़ते हैं, और इस तरह हम आगे बढ़ते हैं।
निष्कर्ष
इस ट्यूटोरियल में, हम डायनामिक प्रोग्रामिंग का उपयोग करके सबसे बड़ा विभाज्य जोड़े वाला उपसमुच्चय ढूंढने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य) भी सीखा जिससे हमने इस समस्या को हल किया। हम यही प्रोग्राम C, Java, Python, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।
