तीन ऐरे से अधिकतम योग जहाँ लगातार एक ही ऐरे से तत्व चुनने की अनुमति नहीं - C++

इस समस्या में, हमें समान आकार N के तीन ऐरे arr1[], arr2[], और arr3[] दिए गए हैं। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में तीन ऐरे से अधिकतम योग ढूंढे जहाँ लगातार एक ही ऐरे से तत्व चुनने की अनुमति नहीं है।

समस्या विवरण

हम N तत्वों को चुनकर अधिकतम योग ढूंढेंगे। i-वां तत्व i-वें इंडेक्स के तत्व से चुना जा सकता है यानी i-वां योग arr1[i]/ arr2[i]/ arr3[i] से हो सकता है। साथ ही, ध्यान रखें कि हम लगातार दो तत्व एक ही ऐरे से नहीं चुन सकते।

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

इनपुट

arr1[] = {5, 8, 9, 20}, arr2[] = {7, 12, 1, 10}, arr3[] = {8, 9, 10, 11} N = 4

आउटपुट

50

व्याख्या

i = 1 के लिए, हम योग के लिए arr3 से 8 लेंगे। i = 2 के लिए, हम योग के लिए arr2 से 12 लेंगे। i = 3 के लिए, हम योग के लिए arr3 से 10 लेंगे। i = 4 के लिए, हम योग के लिए arr1 से 20 लेंगे। योग = 8 + 12 + 10 + 20 = 50

समाधान दृष्टिकोण

समस्या को हल करने के लिए, हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे, हमें अतिरिक्त गणनाओं से बचने के लिए इंडेक्स तक के योगों का मेमोइजेशन भी चाहिए। हम एक 2-D मैट्रिक्स DP[][] बनाएंगे। इंडेक्स i,j पर तत्व i-वें इंडेक्स तक के तत्वों का योग होगा और j-वें ऐरे का उपयोग करके। हम वर्तमान के लिए तत्वों को पुनरावर्ती रूप से ढूंढेंगे और फिर अन्य दो ऐरे से अगले तत्वों का योग कॉल करेंगे।

उदाहरण

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

#include <bits/stdc++.h> using namespace std; const int N = 3; int findMaxVal(int a, int b){    if(a > b)       return a;       return b; } int FindMaximumSum(int index, int arrNo, int arr1[], int arr2[], int arr3[], int n, int DP[][N]){    if (index == n)       return 0;    if (DP[index][arrNo] != -1)       return DP[index][arrNo];       int maxVal = -1;    if (arrNo == 0){       maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));       maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));    }    else if (arrNo == 1){       maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));       maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));    }    else if (arrNo == 2){       maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));       maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));    }    return DP[index][arrNo] = maxVal; } int main(){    int arr1[] = { 5, 8, 9, 20 };    int arr2[] = { 7, 12, 1, 10 };    int arr3[] = { 8, 9, 10, 11 };    int n = sizeof(arr1) / sizeof(arr1[0]);    int DP[n][N];    memset(DP, -1, sizeof DP);    int val1 = FindMaximumSum(0, 0, arr1, arr2, arr3, n, DP);    int val2 = FindMaximumSum(0, 1, arr1, arr2, arr3, n, DP);    int val3 = FindMaximumSum(0, 2, arr1, arr2, arr3, n, DP);    cout<<"The maximum sum from three arrays such that picking elements consecutively from same is not allowed is "<<findMaxVal(val1, findMaxVal(val2, val3));    return 0; }

आउटपुट

The maximum sum from three arrays such that picking elements consecutively from same is not allowed is 50