Please someone answer my question, I will give thumbs up for the answer to my question!

The program must be modified so it also prints the maximum profit path and prints the maximum profit and the rows and columns of that path from row 1 to row n which is described step by step in the last two pictures and the output on the screen should be this(tested on the command line):

The maximum profit is 42.

The maximum profit path is:

(1,5)

(2,4)

(3,5)

(4,5)

(5,4)

Please modify my code and just add what the assignment asks based on the class notes that I will provide below, Please let me know if something isn't clear.

This is the code (solution i had for assignment 4):

# To calculate max profit in table

def findMaxProfit(table):

# To find maximum value in first row result = -1 for i in range(M): result = max(result, table[0][i])

for i in range(1, N):

result = -1 for j in range(M):

# for normal case if (j > 0 and j

# When diagonal right is impossible elif (j > 0): table[i][j] += max(table[i - 1][j], table[i - 1][j - 1])

# When diagonal left is impossible elif (j

result = max(table[i][j], result) return result

N = 0 M = 0 table = [] with open("ptable.txt") as file: fp=file.readlines() for line in fp: line=line.strip() if len(line)==1: M=N=int(line) else: x = [int(i) for i in line.split()] table.append(x) print("The maximum profit that can be earned is ", findMaxProfit(table))

This is the question:

In assignment 4, you wrote a program to find the value of the maximum profit among all of the paths that could be followed from the top of the board to the bottom( i have my solution of assignment 4 below). But that value does not indicate what the sequence of steps in the path. We know that each step moves from one row to the next so all we need to know for each row the number of the column for that path. In other words, we need to create a list of n column numbers. This will require another table which we will call d (for direction).

Please see the accompanying notes( i have the notes below) to see how to find this path. In this assignment, I want you to write a program mppath.py or MPPath.java that extends the previous program in that it prints the maximum profit and the rows and columns of that path from row 1 to row n. Once again, write the program so that it takes as input a file called ptable.txt. The correct output and the format I want you to use is the following:

The maximum profit is 42. The maximum profit path is: (1,5) (2,4) (3,5) (4,5) (5,4) 

As before, the program must be written so that it can be run from the command line.

These are the notes for extra help if needed:

--- Solving the maximum profit path problem --- *** Recursion with repetition *** This first algorithm uses recursion with a lot of) repetition! Analyzing its run time will yield a 0(3n) time, which is exponential in the size of the input p board and so is useless for larger values of n computeQ(i, , p) if - i then return p[i,j] else upperleft - computeQ(i-1, j-1) above - computeQ(i-1, j) upperight = computeQ(i-1, j+1) return p[i,j]+max (upperleft, above, upperright) *** Recursion without repetition! *** This is the dynamic programming solution based on computing the recurrence relation in the PDF document about this problem. computevig, p) for j = 1 ton 911, j] = pll, j] # Fill in the entries in the g table for i = 2 ton for j - 1 ton # Fill in a[i, j] upperright = qli-1, j+1] above - q[i-1, j) upperleft = q[i-1, j-1] q[i, j] = p[i, j] + max(upperleft, above, upperright) --- The method above is driven by this main method. --- main() Initialize the p table from input Declare the a table to be the same size as the p table but add a column indexed 0 with all zeroes and a column indexed n+1 with all zeroes compute(9. P) max = 0 for j = 1 ton if qin, il > max then max = qin, il end print max *** Printing the maximum profit path *** The above algorithm calculates the maximum profit that can be earned on some path but it doesn't print the path itself. This would be a sequence of (row,column) pairs showing which squares are in the maximum profit path. Some minor changes to the algorithm above will build the d (for direction) table. This will print the sequence of (row,column) pairs corresponding to the MPP. We Recall that the value a[i,j] is the maxium profit that can be earned on a path ending at the square i,j. To get to that square, the path had to come from one of the three squares above it: (i-1,j-1), (i-1,j), or (i-1,j+1). The value of d[i,j] is the index of the column of the square on row i-l that got us to square i,j. In other words, d[i,jis equal to one j-1, j, or j+1. Which one depends on which had the maximum value in q. need to modify the computeg method to keep track of that. computevig, P. d) for j = 1 to n 911, il = p[i, j] # Fill in the entries in the g table for i = 2 ton for i = 1 ton # Pill in q[i, j] upperright ali-1, j+1] above - q[i-1, j] upperleft = g(i-1, j-1] if upperright > above and upperright > upperleft then d[i, j] = 1+1 else if above > upperright and above > upperleft then d[i, j] = 1 else d[i, j] = 3-1 q[i, j] = pli, j] + max(upperleft, above, upperright) --- The method above is driven by this main method. --- main() Initialize the p table from input Declare the q table to be the same size as the p table but add a column indexed O with all zeroes and a column indexed n+1 with all zeroes Declare the d table to be the same size as the p table but add a column indexed with all zeroes and a column indexed 1+1 with all zeroes computevig, P, d) max = 0 maxrow = n maxcolumn = 0 for j = 1 ton if an, )) > max then max = a[n, il maxcolumn = j main() Initialize the p table from input Declare the q table to be the same size as the p table but add a column indexed 0 with all zeroes and a column indexed n+1 with all zeroes Declare the d table to be the same size as the p table but add a column indexed 0 with all zeroes and a column indexed n+1 with all zeroes computeQ(q, p, d) max = 0 maxrow = n maxcolumn = 0 for j = 1 ton if an, j] > max then max = a[n, j] maxcolumn = j print max printPath(d, maxcolumn) The method printPath has been added. Here it is in pseudocode. printPath(d, maxcolumn) s = new stack column = maxcolumn for row = n downto 1 push column onto stack column = d[row, column] for row = 1 ton column = pop from s print row, column --- Solving the maximum profit path problem --- *** Recursion with repetition *** This first algorithm uses recursion with a lot of) repetition! Analyzing its run time will yield a 0(3n) time, which is exponential in the size of the input p board and so is useless for larger values of n computeQ(i, , p) if - i then return p[i,j] else upperleft - computeQ(i-1, j-1) above - computeQ(i-1, j) upperight = computeQ(i-1, j+1) return p[i,j]+max (upperleft, above, upperright) *** Recursion without repetition! *** This is the dynamic programming solution based on computing the recurrence relation in the PDF document about this problem. computevig, p) for j = 1 ton 911, j] = pll, j] # Fill in the entries in the g table for i = 2 ton for j - 1 ton # Fill in a[i, j] upperright = qli-1, j+1] above - q[i-1, j) upperleft = q[i-1, j-1] q[i, j] = p[i, j] + max(upperleft, above, upperright) --- The method above is driven by this main method. --- main() Initialize the p table from input Declare the a table to be the same size as the p table but add a column indexed 0 with all zeroes and a column indexed n+1 with all zeroes compute(9. P) max = 0 for j = 1 ton if qin, il > max then max = qin, il end print max *** Printing the maximum profit path *** The above algorithm calculates the maximum profit that can be earned on some path but it doesn't print the path itself. This would be a sequence of (row,column) pairs showing which squares are in the maximum profit path. Some minor changes to the algorithm above will build the d (for direction) table. This will print the sequence of (row,column) pairs corresponding to the MPP. We Recall that the value a[i,j] is the maxium profit that can be earned on a path ending at the square i,j. To get to that square, the path had to come from one of the three squares above it: (i-1,j-1), (i-1,j), or (i-1,j+1). The value of d[i,j] is the index of the column of the square on row i-l that got us to square i,j. In other words, d[i,jis equal to one j-1, j, or j+1. Which one depends on which had the maximum value in q. need to modify the computeg method to keep track of that. computevig, P. d) for j = 1 to n 911, il = p[i, j] # Fill in the entries in the g table for i = 2 ton for i = 1 ton # Pill in q[i, j] upperright ali-1, j+1] above - q[i-1, j] upperleft = g(i-1, j-1] if upperright > above and upperright > upperleft then d[i, j] = 1+1 else if above > upperright and above > upperleft then d[i, j] = 1 else d[i, j] = 3-1 q[i, j] = pli, j] + max(upperleft, above, upperright) --- The method above is driven by this main method. --- main() Initialize the p table from input Declare the q table to be the same size as the p table but add a column indexed O with all zeroes and a column indexed n+1 with all zeroes Declare the d table to be the same size as the p table but add a column indexed with all zeroes and a column indexed 1+1 with all zeroes computevig, P, d) max = 0 maxrow = n maxcolumn = 0 for j = 1 ton if an, )) > max then max = a[n, il maxcolumn = j main() Initialize the p table from input Declare the q table to be the same size as the p table but add a column indexed 0 with all zeroes and a column indexed n+1 with all zeroes Declare the d table to be the same size as the p table but add a column indexed 0 with all zeroes and a column indexed n+1 with all zeroes computeQ(q, p, d) max = 0 maxrow = n maxcolumn = 0 for j = 1 ton if an, j] > max then max = a[n, j] maxcolumn = j print max printPath(d, maxcolumn) The method printPath has been added. Here it is in pseudocode. printPath(d, maxcolumn) s = new stack column = maxcolumn for row = n downto 1 push column onto stack column = d[row, column] for row = 1 ton column = pop from s print row, column