इस समस्या में, हमें तीन सरणियाँ दी गई हैं arr1[], arr2[], और arr3[] सभी आकार N. हमारा काम तीन सरणियों से अधिकतम योग खोजने के लिए एक प्रोग्राम बनाना है जैसे कि तत्वों को लगातार चुनना नहीं है C++ में अनुमति है।
समस्या का विवरण
हम N तत्वों को चुनकर अधिकतम योग प्राप्त करेंगे। i=वें तत्व को सरणी के i-वें तत्व से योग में से चुना जा सकता है अर्थात ith योग 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-डी मैट्रिक्स बनाएंगे, 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