資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究使用兩種遍歷收集網格中的最大點數
有一個矩陣，每個單元中都有點，如何使用兩次遍歷從該網格中獲得最大點數。
有一些條件滿足-
- 第一次遍歷從網格中的左上角單元格開始，並應該到達左下角。而第二次遍歷從右上角到達右下角
- 從一個單元格，我們只能移動到當前單元格的底部、左下角或右下角。
- 如果一次遍歷已經從一個單元格獲取了一些點，在接下來的遍歷中將不會從該單元格獲取任何點。
輸入和輸出
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。
輸出 − 最大值。
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
更新於:2020 年 6 月 16 日
263 次瀏覽
廣告