प्रत्येक सेल में बिंदुओं के साथ एक मैट्रिक्स है, दो ट्रैवर्सल का उपयोग करके उस ग्रिड से अधिकतम अंक कैसे प्राप्त करें।
संतुष्ट करने के लिए कुछ शर्त है -
- पहला ट्रैवर्सल ग्रिड में ऊपरी बाएँ सेल से शुरू होता है और निचले बाएँ कोने में जाना चाहिए। और दूसरे ट्रैवर्सल में ऊपरी दाएं कोने से शुरू होकर नीचे दाएं कोने तक
- एक सेल से हम केवल वर्तमान सेल के नीचे, नीचे बाईं ओर और केवल वर्तमान सेल के नीचे दाईं ओर जा सकते हैं।
- अगर एक ट्रैवर्सल को पहले से ही सेल से कुछ पॉइंट मिलते हैं, तो अगले ट्रैवर्सल में उस सेल से कोई पॉइंट नहीं मिलेगा।
इनपुट और आउटपुट
Input: A grid with points. 3 6 8 2 5 2 4 3 1 1 20 10 1 1 20 10 1 1 20 10 Output: Maximum points collected by two traversals is 73. From the first traversal, it gains: 3 + 2 + 20 + 1 + 1 = 27 From the second traversal, it gains: 2 + 4 + 10 + 20 + 10 = 46
एल्गोरिदम
findMaxVal(mTable, x, y1, y2)
इनपुट - याद रखने की तालिका, x मान और y1, y2 के रूप में एक 3D सरणी।
आउटपुट - अधिकतम मूल्य।
Begin if x, y1 and y2 is not valid, then return - ∞ if both traversal is complete, then if y1 = y2, then return grid[x, y1] else return grid[x, y1] + grid[x, y2] if both traversal are at last row, then return - ∞ if subProblem is solved, then return mTable[x, y1, y2] set res := - ∞ if y1 = y2, then temp := grid[x, y1] else temp := grid[x, y1] + grid[x, y2] res := max of res and (temp + findMaxVal(mTable, x+1, y1, y2-1)) res := max of res and (temp + findMaxVal(mTable, x+1, y1, y2+1)) res := max of res and (temp + findMaxVal(mTable, x+1, y1, y2)) res := max of res and (temp + findMaxVal(mTable, x+1, y1-1, y2)) res := max of res and (temp + findMaxVal(mTable, x+1, y1-1, y2-1)) res := max of res and (temp + findMaxVal(mTable, x+1, y1-1, y2+1)) res := max of res and (temp + findMaxVal(mTable, x+1, y1+1, y2)) res := max of res and (temp + findMaxVal(mTable, x+1, y1+1, y2-1)) res := max of res and (temp + findMaxVal(mTable, x+1, y1+1, y2+1)) return true if mTable[x, y1, y2] = res End
उदाहरण
#include<iostream>
#define ROW 5
#define COL 4
using namespace std;
int grid[ROW][COL] = {
{3, 6, 8, 2},
{5, 2, 4, 3},
{1, 1, 20, 10},
{1, 1, 20, 10},
{1, 1, 20, 10},
};
bool isValidInput(int x, int y1, int y2) {
return (x >= 0 && x < ROW && y1 >=0 && y1 < COL && y2 >=0 && y2 < COL);
}
int max(int a, int b) {
return (a>b)?a:b;
}
int findMaxVal(int mTable[ROW][COL][COL], int x, int y1, int y2) {
if (!isValidInput(x, y1, y2)) //when in invalid cell, return -ve infinity
return INT_MIN;
if (x == ROW-1 && y1 == 0 && y2 == COL-1) //when both traversal is complete
return (y1 == y2)? grid[x][y1]: grid[x][y1] + grid[x][y2];
if (x == ROW-1) //both traversal are at last row but not completed
return INT_MIN;
if (mTable[x][y1][y2] != -1) //when subproblem is solved
return mTable[x][y1][y2];
int answer = INT_MIN; //initially the answer is -ve infinity
int temp = (y1 == y2)? grid[x][y1]: grid[x][y1] + grid[x][y2]; //store gain of the current room
//find answer for all possible value and use maximum of them
answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2-1));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2+1));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2-1));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2+1));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2-1));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2+1));
return (mTable[x][y1][y2] = answer); //store the answer in the mTable and return.
}
int findMaxCollection() {
// Create a memoization table and set all values as -1
int mTable[ROW][COL][COL];
for(int i = 0; i<ROW; i++)
for(int j = 0; j<COL; j++)
for(int k = 0; k<COL; k++)
mTable[i][j][k] = -1;
return findMaxVal(mTable, 0, 0, COL-1);
}
int main() {
cout << "Maximum collection is " << findMaxCollection();
return 0;
} आउटपुट
Maximum collection is 73