A. the maximum profit path problem (MPPP) is presented below. That's where you are given an nxn board with each square having a positive integer profit. Please implement the algorithm described below.

Please see the documents "Dynamic program max profit path problem (MPPP)", a PDF document, and "Dynamic programming MPPP algorithms", a text file(that will be in screenshots below).

Read the values for the p table from a file called ptable.txt. They will be in a file where the first value will be the size of the board and the remaining values will be the valus of p row by row. All values are separated by whitespace. For example, with the data presented in the above PDF document, the file will look like:

5 4 8 2 3 5 2 7 5 10 2 3 2 7 7 9 6 5 7 7 9 8 7 5 9 8 

The program should print the maximum profit, which is the largest value on the last row of the q table. Call the program mppp.py or MPPP.java. Write the program so that it can be run from the command line as below. The example here assume that the input file contains the data above.

C:\>java MPPP The maximum profit that can be earned is 42 

or

C:\>python mppp.py The maximum profit that can be earned is 42 

the program will print that maximum profit.

Here are the documents "Dynamic program max profit path problem (MPPP)", a PDF document, and "Dynamic programming MPPP algorithms":

First problem to solve with dynamic programming A maximum-profit path problem Given a 5x5 table where each square has a profit. The problem is to move from the top row down to the bottom row. You can start at any top square. On each move, you can step down to the next row but only to a square that is diagonally to the left, immediately below, or diagonally to the right. You can't step off the board. As you move to each square, you get the profit stored there added to your total. The path ends when you reach a square on the bottom row. The question is: Which of the many paths from a top square to a bottom square will get you the maximum profit? The description above completes step 1(a) from section 3.4. We have described the problem in enough detail to proceed. How do we solve this? We could try every path and record each one's total profit in a list and then search that list for the highest profit. How any paths are there? At each square along a path, there are 2 or 3 squares that could be the next step. Overestimating slightly, let's say that there are 3 choices for every square. On an n x n board, a path contains n squares. Only the last square has no choices because the path stops there. So a path contains n 1 squares at which 3 choices may be made. This means there are 0(3n-1) paths. An efficient algorithm cannot try all paths and find the best! To get a better understanding of the problem, here is an example of a 5 x 5 profit board p and a filled-out table q where q[i,j] is maximum profit that can be earned on a path ending at that square. Profit (p table) 1 3 5 p 1 2 4 2 4 3 10 7 8 7 2 5 7 3 2 5 7 7 5 5 2 9 3 4 6 7 9 5 8 9 8 Maximum profit from the top to that square (q table) 2 4 5 9 1 8 3 5 2 15 15 7 14915 13 22 3 22 24 17 27 4 31 29 36 33 41 5 BE 42 So the sub-problem to be solved for each square is to compute the maximum profit one can earn ending at that square. The formula for finding that is given by this recurrence relation. The values in q table were computed using it. p[i,j] if i = 1 q[i,j] = (q[i 1,j 1)) max q[i 1,j] + p[i,j] otherwise (q[i 1,j + 1]) So the square at i,j has a value computed by adding p[i,j] to the maximum value among: the square one above and to the left (q[i 1,j 1]) the square directly above (q[i 1,j]) the square one above and to the right (9[i 1,j + 1]) If there is no square because one of the indices is less than 1 or greater than 5, the value used is 0. This completes step 1(b) from section 3.4 in that we now have a formula for filling the q table. Once filled, we scan the bottom row (row 5 in this case) for the largest value. That is the maximum profit one can earn. So now we know where the path must end up. But we don't know what the rest of the path is. We'll take a look at finding that later. Dynamic programming MPPP algorithms max then max = a[n, il end print max