Có một ma trận với các điểm trong mỗi ô, làm cách nào để có được điểm tối đa từ lưới đó bằng cách sử dụng hai đường truyền.
Có một số điều kiện để đáp ứng -
- Đường truyền đầu tiên bắt đầu từ ô trên cùng bên trái trong lưới và sẽ chuyển đến góc dưới cùng bên trái. Và trong đường truyền thứ hai bắt đầu từ góc trên cùng bên phải đến góc dưới cùng bên phải
- Từ một ô, chúng tôi chỉ có thể di chuyển xuống dưới cùng, dưới cùng bên trái của ô hiện tại và chỉ dưới cùng bên phải của các ô hiện tại.
- Nếu một lượt truyền tải đã nhận được một số điểm từ một ô, thì trong lần truyền tải tiếp theo sẽ không có điểm nào được nhận từ ô đó.
Đầu vào và Đầu ra
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
Thuật toán
findMaxVal(mTable, x, y1, y2)
Đầu vào - một mảng 3D dưới dạng bảng ghi nhớ, giá trị x và y1, y2.
Đầu ra - giá trị lớn nhất.
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
Ví dụ
#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;
} Đầu ra
Maximum collection is 73