इस समस्या में, हमें n मकान दिए गए हैं जिनमें कुछ मान हैं। हमारा काम घरों से अधिकतम संभव चोरी मूल्य का पता लगाना है।
समस्या का विवरण - हमारे पास एक सरणी घर हैं [] जिसमें प्रत्येक घर में मौजूद मान शामिल हैं। एक चोर घरों को लूटता है लेकिन वह दो आसन्न घरों से चोरी नहीं कर सकता क्योंकि पड़ोसियों को चोरी के बारे में पता है। हमें उस अधिकतम संभव मूल्य का पता लगाने की आवश्यकता है जिसे चोर बिना पकड़े घर से चुरा सकता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
houses[] = {5, 2, 1, 6, 7, 9, 4, 3} आउटपुट
23
स्पष्टीकरण
The max values can be stolen as : 5, 6, 9, 3.
समाधान दृष्टिकोण
डायनेमिक प्रोग्रामिंग का उपयोग करके समस्या का समाधान पाया जा सकता है। जैसा कि हमें चोर द्वारा चुराई गई अधिकतम मूल्य का पता लगाने की आवश्यकता है जैसे कि यदि वह सूचकांक i पर एक घर से चोरी करता है, तो वह घर से सूचकांक (i + 1) पर चोरी नहीं कर सकता है। साथ ही, हम इंडेक्स (i-1) पर घर से चोरी नहीं करते। समस्या को हल करने के लिए, हम n आकार की एक DP सरणी बनाएंगे। और बेस केस के लिए हम डीपी [0] को घरों के साथ [0] और डीपी [1] को घरों के साथ शुरू करेंगे [1]। फिर, हम DP के सभी मान इंडेक्स 2 से n-1 तक पाएंगे। DP का मान [i] DP [i-2] + घरों [i] या DP [i-1] में से अधिकतम मूल्य होगा। और अंत में 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