รวบรวมคะแนนสูงสุดในตารางโดยใช้การข้ามสองครั้ง

มีเมทริกซ์ที่มีจุดในแต่ละเซลล์ วิธีรับคะแนนสูงสุดจากกริดนั้นโดยใช้สองเส้นทาง

มีเงื่อนไขบางประการที่ต้องปฏิบัติตาม -

• การข้ามผ่านครั้งแรกเริ่มจากเซลล์ด้านซ้ายบนในตาราง และควรไปที่มุมล่างซ้าย และในเส้นทางที่สองเริ่มจากมุมบนขวาไปมุมล่างขวา
• จากเซลล์เดียว เราสามารถย้ายไปที่ด้านล่างสุด ด้านซ้ายล่างของเซลล์ปัจจุบัน และด้านล่างขวาของเซลล์ปัจจุบันเท่านั้น
• หากการข้ามผ่านได้บางจุดจากเซลล์แล้ว การข้ามผ่านครั้งถัดไปจะไม่ได้รับคะแนนจากเซลล์นั้น

อินพุตและเอาต์พุต

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)

ป้อนข้อมูล - อาร์เรย์ 3 มิติเป็นตารางการท่องจำ ค่า x และ y1, y2

ผลลัพธ์ − ค่าสูงสุด

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