इस समस्या में, हमें कुछ मूल्यों वाले n घर दिए गए हैं। हमारा कार्य घरों से चुराए जा सकने वाले अधिकतम संभावित मूल्य ज्ञात करना है।
समस्या विवरण - हमारे पास एक सरणी houses[] है जिसमें प्रत्येक घर में मौजूद मूल्य होते हैं। एक चोर घरों को लूटता है लेकिन वह दो आसन्न घरों से नहीं चुरा सकता क्योंकि पड़ोसियों को चोरी के बारे में पता चल जाता है। हमें चोर द्वारा बिना पकड़े घरों से चुराए जा सकने वाले अधिकतम संभावित मूल्य ज्ञात करना है।
आइए एक उदाहरण से समझते हैं:
इनपुट
houses[] = {5, 2, 1, 6, 7, 9, 4, 3}आउटपुट
23
व्याख्या
अधिकतम मूल्य इस प्रकार चुराए जा सकते हैं: 5, 6, 9, 3।
समाधान दृष्टिकोण
समस्या का समाधान डायनामिक प्रोग्रामिंग का उपयोग करके पाया जा सकता है। चूंकि हमें चोर द्वारा चुराए जा सकने वाले अधिकतम मूल्य को खोजने की आवश्यकता है जैसे कि यदि वह इंडेक्स i पर घर से चुराता है, तो वह इंडेक्स (i+1) पर घर से नहीं चुरा सकता। साथ ही, हमने इंडेक्स (i-1) पर घर से चोरी नहीं की होगी। समस्या को हल करने के लिए, हम आकार n की एक DP सरणी बनाएंगे। और आधार मामले के लिए हम DP[0] को houses[0] से और DP[1] को houses[1] से प्रारंभ करेंगे। फिर, हम इंडेक्स 2 से n-1 तक DP के सभी मान खोजेंगे। DP[i] का मान DP[i-2] + houses[i] या DP[i-1] में से अधिकतम होगा। और अंत में DP सरणी का अंतिम मान चुराया जा सकने वाला अधिकतम मूल्य है।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम (DP सरणी दृष्टिकोण):
उदाहरण
#include <iostream> using namespace std; int calMax(int a, int b){ if(a > b) return a; return b; } int findMaxValuesStolen(int houses[], int n) { if (n == 0) return 0; int DP[n]; DP[0] = houses[0]; DP[1] = calMax(houses[0], houses[1]); for (int i = 2; i<n; i++) DP[i] = calMax( (houses[i] + DP[i-2]), DP[i-1]); return DP[n-1]; } int main() { int houses[] = {5, 2, 1, 6, 7, 9, 4, 3}; int n = sizeof(houses)/sizeof(houses[0]); cout<<"The maximum possible values stolen from the houses is "<<findMaxValuesStolen(houses, n); return 0; }आउटपुट
The maximum possible values stolen from the houses is 23
यह समाधान अच्छा है लेकिन इसे इस तथ्य का उपयोग करके अधिक कुशल बनाया जा सकता है कि चुराया गया अधिकतम मूल्य केवल दो मानों का उपयोग करके पाया जा सकता है। चूंकि DP में, हमने प्रत्येक इंडेक्स के लिए केवल दो मानों का उपयोग किया है। इसलिए, हम समाधान खोजने के लिए केवल दो चरों का उपयोग कर सकते हैं जो समस्या की स्पेस जटिलता को कम करता है।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम (अनुकूलित स्पेस दृष्टिकोण):
उदाहरण
#include <iostream> using namespace std; int calMax(int a, int b){ if(a > b) return a; return b; } int findMaxValuesStolen(int houses[], int n) { if (n == 0) return 0; int maxValStolen; int val1 = houses[0]; int val2 = calMax(houses[0], houses[1]); for (int i = 2; i<n; i++) { maxValStolen = calMax( (houses[i]+val1) , val2); val1 = val2; val2 = maxValStolen; } return maxValStolen; } int main() { int houses[] = {5, 2, 1, 6, 7, 9, 4, 3}; int n = sizeof(houses)/sizeof(houses[0]); cout<<"The maximum possible values stolen from the houses is "<<findMaxValuesStolen(houses, n); return 0; }आउटपुट
The maximum possible values stolen from the houses is 23
