इस समस्या में, हमें 2 x n आकार का एक आयताकार ग्रिड दिया गया है। हमारा काम 2 x n ग्रिड में अधिकतम योग खोजने के लिए एक प्रोग्राम बनाना है, ताकि कोई भी दो तत्व C++ में आसन्न न हों।
समस्या का विवरण
अधिकतम योग ज्ञात करने के लिए, हम उन तत्वों का चयन नहीं कर सकते जो वर्तमान तत्व से सटे हैं, लंबवत, क्षैतिज या तिरछे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
rectGrid[2][] =389 411
आउटपुट
13
स्पष्टीकरण
सभी संभावित राशियाँ हैं
अगर हम rectGrid[0][0] यानी 3 से शुरू करते हैं, तो हम केवल 9 या 1 जोड़ सकते हैं। अधिकतम राशि 12 है।
अगर हम rectGrid[1][0] यानी 4 से शुरू करते हैं, तो हम केवल 9 या 1 जोड़ सकते हैं। अधिकतम राशि 13 है।
अगर हम रेक्टग्रिड [0] [1] यानी 8 से शुरू करते हैं, तो हम कोई तत्व नहीं जोड़ सकते हैं। अधिकतम योग 8 है।
अगर हम रेक्टग्रिड [1] [1] यानी 1 से शुरू करते हैं, तो हम कोई तत्व नहीं जोड़ सकते हैं। अधिकतम राशि 1 है।
अगर हम रेक्टग्रिड [0] [2] यानी 9 से शुरू करते हैं, तो हम केवल 3 या 4 जोड़ सकते हैं। अधिकतम राशि 13 है।
अगर हम rectGrid[1][2] यानी 1 से शुरू करते हैं, तो हम केवल 3 या 4 जोड़ सकते हैं। अधिकतम राशि 5 है।
कुल मिलाकर अधिकतम राशि 13 है।
समाधान दृष्टिकोण
समस्या अधिकतम योग के समान है जैसे कि कोई भी दो तत्व आसन्न नहीं हैं जैसा कि हमने पिछली पोस्ट में देखा है। अंतर वह सरणी है जो यहां 2D है और आसन्न तत्वों की स्थिति है। इसलिए, हम पंक्तियों और स्तंभों दोनों के लिए शर्तों का उपयोग करते हुए अधिकतम तत्व पर विचार करेंगे। चूंकि प्रत्येक कॉलम में दो पंक्तियां हैं, हम वैकल्पिक तत्वों पर अधिकतम संभव विचार करेंगे।
उदाहरण
समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#include<iostream>
using namespace std;
int findMax(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSum(int rectGrid[2][20], int N){
int currectSum = 0;
int nextSum = 0;
int altSum;
for (int i = 0; i<N; i++ ){
altSum = findMax(nextSum, currectSum);
currectSum = nextSum + findMax(rectGrid[0][i], rectGrid[1][i]);
nextSum = altSum;
}
int maxSum = findMax(nextSum, currectSum);
return maxSum;
}
int main(){
int rectGrid[2][20] = {{3, 8, 9, 5},
{4, 1, 2, 7}};
int N = 4;
cout<<"The maximum sum in a 2 x "<<N<<" grid such that no two elements are adjacent is "<<calcMaxSum(rectGrid, N);
return 0;
} आउटपुट
The maximum sum in a 2 x 4 grid such that no two elements are adjacent is 15