एक समस्या को हल करने के लिए जिसमें हमें अलग-अलग तत्वों से युक्त एक सरणी दी जाती है। अब हमारा कार्य उपसमुच्चय को इस प्रकार खोजना है कि प्रत्येक जोड़ी समान रूप से विभाज्य हो, अर्थात, प्रत्येक बड़ा तत्व प्रत्येक छोटे तत्व से विभाज्य हो, उदाहरण के लिए।
इनपुट :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 नेमस्पेस का उपयोग करना; // यह आईथ इंडेक्स डीपी [एन - 1] =1 से शुरू होने वाले सबसे बड़े सबसेट को स्टोर करने जा रहा है; // चूंकि अंतिम तत्व सबसे बड़ा है इसलिए इसका सबसेट आकार 1 int सबसे बड़ा =0 है; // उत्तर के लिए (int i =n - 2; i>=0; i--) { int maxi =0; // अधिकतम =0 लेना; के लिए (int j =i + 1; j आउटपुट
4
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम अब गतिशील प्रोग्रामिंग का उपयोग करके समस्या का समाधान करते हैं। सबसे पहले, हम अब अपनी सरणी को सॉर्ट करते हैं। जैसा कि हमने अभी अपने एरे को सॉर्ट किया है, हमने एक एरे डीपी बनाया है जो पिछले सभी सबसे बड़े सबसेट को स्टोर करेगा।
अब हम इसमें अपने ऐरे के अंत से शुरू करते हैं। हम पहले मानते हैं कि हमारा वर्तमान तत्व न्यूनतम है और अब अन्य गुणकों की जांच करें क्योंकि हम इसके आगे एक गुणक का सामना करते हैं। हम उलटी यात्रा कर रहे हैं, इसका मतलब है कि हमने उस तत्व का पहले भी सामना किया है। हमने अब अपने डीपी सरणी के अंदर उनके सबसे बड़े सबसेट आकार को भी सहेज लिया है। हम इस तत्व को अपने वर्तमान तत्व के dp में जोड़ते हैं, और इसी तरह हम आगे बढ़ते हैं।
निष्कर्ष
इस ट्यूटोरियल में, हम डायनेमिक प्रोग्रामिंग का उपयोग करके सबसे बड़े विभाज्य जोड़े सबसेट को खोजने के लिए एक समस्या का समाधान करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।