समस्या कथन
एक एन * एन मैट्रिक्स पर विचार करें। मान लीजिए कि मैट्रिक्स में प्रत्येक सेल का मान असाइन किया गया है। हम पंक्ति i में प्रत्येक सेल से केवल i+1 पंक्ति में एक तिरछे उच्च सेल में जा सकते हैं [यानी सेल (i, j) tocell(i+1, j-1) और सेल (i+1, j+1) से केवल]। उपरोक्त शर्त का पालन करते हुए शीर्ष पंक्ति से नीचे की पंक्ति तक का पथ खोजें जैसे कि अधिकतम योग प्राप्त हो
उदाहरण
If given input is:
{
{5, 6, 1, 17},
{-2, 10, 8, -1},
{ 3, -7, -9, 4},
{12, -4, 2, 2}
} अधिकतम योग है (17 + 8 + 4 + 2) =31
एल्गोरिदम
-
विचार यह है कि पहली पंक्ति के प्रत्येक सेल से शुरू होने वाले अधिकतम योग, या सभी पथ खोजें और अंत में पहली पंक्ति में अधिकतम सभी मान लौटाएं।
-
हम डायनामिक प्रोग्रामिंग का उपयोग करते हैं क्योंकि कई उप समस्याओं के परिणामों की बार-बार आवश्यकता होती है
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int getMaxMatrixSum(int mat[SIZE][SIZE], int n){
if (n == 1) {
return mat[0][0];
}
int dp[n][n];
int maxSum = INT_MIN, max;
for (int j = 0; j < n; j++) {
dp[n - 1][j] = mat[n - 1][j];
}
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
max = INT_MIN;
if (((j - 1) >= 0) && (max < dp[i + 1][j - 1])) {
max = dp[i + 1][j - 1];
}
if (((j + 1) < n) && (max < dp[i + 1][j + 1])) {
max = dp[i + 1][j + 1];
}
dp[i][j] = mat[i][j] + max;
}
}
for (int j = 0; j < n; j++) {
if (maxSum < dp[0][j]) {
maxSum = dp[0][j];
}
}
return maxSum;
}
int main(){
int mat[SIZE][SIZE] = {
{5, 6, 1, 17},
{-2, 10, 8, -1},
{3, -7, -9, 4},
{12, -4, 2, 2}
};
int n = 4;
cout << "Maximum Sum = " << getMaxMatrixSum(mat, n) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है-
Maximum Sum = 31