CSC349-Project 3: Dynamic Programming Solved

Implement a class named GameProblem.    //DON’T change the name
Problem description (adapted from Theresa Migler; original is by Glencora Borradaile)    You will design a dynamic programming algorithm for the following game that is played on an n×m grid A (the grid is not necessarily square). You start on any square of the grid. Then on each turn, you move either one square to the right or one square down. The game ends when you move off the edge of the board (either the bottom side or the right side). Each square of the grid has a numerical value. Your score is given by the sum of the values of the grid squares that you visit. The object is to maximize your score. For example, in the grid below, the player can score 8 - 6 + 7 - 3 + 4 = 10 by following the highlighted route. (This is not the best solution. The best solution has value 15 – can you find it?)                                                                                                                                                                                                   

Write a program to implement a dynamic programming algorithm for solving the above described problem (see details of implementation on the next page, in game method’s description). You are required to use the BOTTOM-UP method (i.e. iterative approach) for your algorithm.

Attention:  you are NOT allowed to use naïve recursion or memoized top-down approach.   There should NOT be any recursion in your program – not in computing/finding the optimal value, and not in constructing/printing of the actual optimal solution.

The GameProblem class should have two public methods: main and game – both void methods. You may have private methods that support public methods (you can define them as appropriate).  

- main method: in this method you need to do the following. 

Prompt the user to enter the name of the file containing the data for your problem, input the file-name and set up a scanner to read from that file. 
Read values from the file: these are the data you will pass to game method as parameter-values. Your file content will be as follows (values on the same line will be separated by ≥1 spaces):the first line contains two integers: values of n and m (i.e. number of rows and columns of A)
then n lines will follow, each line containing m integers (a line represents one row of A)
 

Note: Assume the file has a correct content (don’t worry about checking validity or format).

Example: for the data used in the above picture, your input file content will be this:

 

 5  5 

-1  7 -8  10 -5  

-4 -9  8  -6  0  5 -2 -6  -6  7 -7  4  7  -3 -3 

 7  1 -6   4 -9 

 

Invoke the below-described game method passing values for n, m, and A
    The game method will do all the work (it will output the max score and the optimal route).

- game method: this method should have the following signature.  

 

          public static void game(int n, int m, int[][] A)   

                          //The parameters represent:  number of rows, number of columns, and the A grid

 

Your game method should implement a dynamic programming algorithm (bottom-up method) to find and output (i) the maximum score that can be obtained for an instance of the problem, and (ii) a route that leads to that maximum score.

 

Details of the implementation: You are going to define a table S[1..n,1..m] to hold max scores; value of each S[i, j] will be the max score for a path starting at [i,j] square. Your goal is to find a square in S (i.e. a pair of index-values x and y) that has the max score, and then track the route that starts at [x,y] square. So, for the x,y index-values S[x,y] =      max     {  𝑆𝑆[𝑖𝑖, 𝑗𝑗]  } . 

1≤𝑖𝑖≤𝑛𝑛,1≤𝑗𝑗≤𝑚𝑚

 

First, let’s see how to compute the S-values: here is a definition that will help you:

 

𝐴𝐴[𝑛𝑛,𝑚𝑚]                                                  𝑓𝑓𝑓𝑓𝑓𝑓 𝑖𝑖=𝑛𝑛,𝑗𝑗=𝑚𝑚 (𝑡𝑡ℎ𝑖𝑖𝑖𝑖 𝑖𝑖𝑖𝑖 𝑡𝑡ℎ𝑒𝑒 𝑏𝑏𝑓𝑓𝑡𝑡𝑡𝑡𝑓𝑓𝑚𝑚−𝑓𝑓𝑖𝑖𝑟𝑟ℎ𝑡𝑡 𝑖𝑖𝑠𝑠𝑠𝑠𝑠𝑠𝑓𝑓𝑒𝑒: 𝑦𝑦𝑓𝑓𝑠𝑠 𝑐𝑐𝑠𝑠𝑛𝑛 𝑓𝑓𝑛𝑛𝑜𝑜𝑦𝑦 𝑒𝑒𝑥𝑥𝑖𝑖𝑡𝑡) max{𝑆𝑆[𝑖𝑖+1, 𝑚𝑚],0}+𝐴𝐴[𝑖𝑖,𝑚𝑚]              𝑓𝑓𝑓𝑓𝑓𝑓 𝑖𝑖≠𝑛𝑛,𝑗𝑗=𝑚𝑚 (𝑡𝑡ℎ𝑖𝑖𝑖𝑖 𝑖𝑖𝑖𝑖 𝑡𝑡ℎ𝑒𝑒 𝑜𝑜𝑠𝑠𝑖𝑖𝑡𝑡 𝑐𝑐𝑓𝑓𝑜𝑜𝑠𝑠𝑚𝑚𝑛𝑛: 𝑚𝑚𝑓𝑓𝑚𝑚𝑒𝑒 𝑑𝑑𝑓𝑓𝑑𝑑𝑛𝑛 𝑓𝑓𝑓𝑓 𝑒𝑒𝑥𝑥𝑖𝑖𝑡𝑡)                    

S[i,j] =max{𝑆𝑆[𝑛𝑛,𝑗𝑗+1],0}+𝐴𝐴[𝑛𝑛,𝑗𝑗]                 𝑓𝑓𝑓𝑓𝑓𝑓 𝑖𝑖=𝑛𝑛,𝑗𝑗≠𝑚𝑚 (𝑡𝑡ℎ𝑖𝑖𝑖𝑖 𝑖𝑖𝑖𝑖 𝑡𝑡ℎ𝑒𝑒 𝑜𝑜𝑠𝑠𝑖𝑖𝑡𝑡 𝑓𝑓𝑓𝑓𝑑𝑑: 𝑚𝑚𝑓𝑓𝑚𝑚𝑒𝑒 𝑓𝑓𝑖𝑖𝑟𝑟ℎ𝑡𝑡 𝑓𝑓𝑓𝑓 𝑒𝑒𝑥𝑥𝑖𝑖𝑡𝑡)                               max{𝑆𝑆[𝑖𝑖+1, 𝑗𝑗],𝑆𝑆[𝑖𝑖,𝑗𝑗+1]}+𝐴𝐴[𝑖𝑖,𝑗𝑗]     𝑓𝑓𝑓𝑓𝑓𝑓 𝑖𝑖≠𝑛𝑛,𝑗𝑗≠𝑚𝑚 (𝑐𝑐ℎ𝑒𝑒𝑐𝑐𝑒𝑒 𝑡𝑡ℎ𝑒𝑒 𝑏𝑏𝑒𝑒𝑡𝑡𝑡𝑡𝑒𝑒𝑓𝑓: 𝑚𝑚𝑓𝑓𝑚𝑚𝑒𝑒 𝑑𝑑𝑓𝑓𝑑𝑑𝑛𝑛 𝑓𝑓𝑓𝑓 𝑚𝑚𝑓𝑓𝑚𝑚𝑒𝑒 𝑓𝑓𝑖𝑖𝑟𝑟ℎ𝑡𝑡)                 

 

Attention: 1. the order in which you fill the values in the S-table is important: think about it. 2. be mindful of the efficiency of the algorithm – do NOT include unnecessary checks that will slow down the algorithm (particularly, inside any of i- or j- loops do NOT check if i==n or j==m). 

Hint: do NOT implement all 4 lines of the formula in one nested loop. Implement each line of the formula separately/individually (in an independent segment).

 

To be able to track the rout, you need to define an auxiliary table R which is fill parallel to S: in each R[i,j] cell you will save info about the choice made in computing the value of respective S[i,j] – e.g. you can save “d” if the choice is to move down, “r” if the choice is to move right, and “e” if you have to exit. 

 

Note: When you find an x,y pair of indexes that represent the max score (i.e. the max S-value), you can then create the output of the optimal route: start with the [x,y] cell in the R-table and follow the “directions” registered in the R-table – move right, down, or exit (this is similar to what we did in class when producing the output of LCS problem’s optimal solution). 

 

ATTENTION: in your output the indexing should be natural (indexing must start with 1).

 

Example: for the above example, on the screen your output should look like this: