2 x n ग्रिड में अधिकतम योग जहाँ कोई दो आसन्न तत्व न हों - C++

इस समस्या में, हमें 2 x n आकार का एक आयताकार ग्रिड दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में 2 x n ग्रिड में अधिकतम योग ढूंढे जहाँ कोई दो आसन्न तत्व न हों।

समस्या विवरण

अधिकतम योग ढूंढने के लिए, हम उन तत्वों का चयन नहीं कर सकते जो वर्तमान तत्व के आसन्न हैं - लंबवत, क्षैतिज या विकर्ण रूप से।

आइए एक उदाहरण से इस समस्या को समझते हैं,

इनपुट

rectGrid[2][] = {{3, 8, 9}, {4, 1, 1}}

आउटपुट

13

व्याख्या

सभी संभावित योग हैं:

यदि हम rectGrid[0][0] यानी 3 से शुरू करते हैं, तो हम केवल 9 या 1 जोड़ सकते हैं। अधिकतम योग 12 है।

यदि हम rectGrid[1][0] यानी 4 से शुरू करते हैं, तो हम केवल 9 या 1 जोड़ सकते हैं। अधिकतम योग 13 है।

यदि हम rectGrid[0][1] यानी 8 से शुरू करते हैं, तो हम कोई तत्व नहीं जोड़ सकते। अधिकतम योग 8 है।

यदि हम rectGrid[1][1] यानी 1 से शुरू करते हैं, तो हम कोई तत्व नहीं जोड़ सकते। अधिकतम योग 1 है।

यदि हम rectGrid[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