Here is an instruction of this program: A board has n * m cells, and there is a

Question

Here is an instruction of this program: A board has n*m cells, and there is a gift with some value (value is greater than 0) in every cell. You can get gifts starting from the top-left cell, and move right or down or diagonal in each step, and finally reach the cell at the bottom-right cell. The objective is to find the maximum total gifts you may earn and to find a route that generates the maximum. Use the dynamic programming to model, program this problem, and compute its time complexity. Test your program using several data sets generated by a random number generator .

*** I have a function that does find the maximum total gifts but I don't know how to find a route that generates the maximum. Can anyone help me adding some code to this function??? Thanks in advance.

public static void getMaxValue(int[][] values) {

int rows = values.length;
int cols = values[0].length;
  
int[] maxValues = new int[cols];
for(int i = 0; i < rows; ++i) {
for(int j = 0; j < cols; ++j) {
int left = 0;
int up = 0;
  
if(i > 0) {
up = maxValues[j];
}
  
if(j > 0) {
left = maxValues[j - 1];
}
maxValues[j] = Math.max(left, up) + values[i][j];   
       System.out.println("Max Value is " + maxValues[cols - 1]);
   }
}

Explanation / Answer

int rows = values.length;
int cols = values[0].length;
int[][] maxValues = new int[rows][cols];

for(int i = 0; i < rows; ++i) {
for(int j = 0; j < cols; ++j) {
int left = 0;
int up = 0;

if(i > 0) {
up = maxValues[i - 1][j];
}

if(j > 0) {
left = maxValues[i][j - 1];
}

maxValues[i][j] = Math.max(left, up) + values[i][j];
}
}

return maxValues[rows - 1][cols - 1];
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.