You are to develop a dynamic programming solution to the following problem
presented on p. 368 of the text but modified here:
You are given an n-by-n checkerboard where each square has a profit p[i,,j].
Unlike the problem in the text, you may assume that the profits are all
positive integers. The task is to place a checker on a square in the first row and advance it
row-by-row to the top. The checker may only move up each time and it
may only move to one of three squares in the next row: the square that is
one up and to the left, the square immediately above, or the square that
is one up and to the right. Note that if the checker is in the first column or the last column it only
has two squares it can move to.
Each time it moves to a new square,
the checker adds to its winnings the profit for that square. The goal
of the game is maximize the checker's winnings.
Let w[i, ,j] be the maximum winnings a checker can earn by going to square i,j.
Begin thinking about this problem by deriving a recurrence relation for
computing w[i,j]. The base case defines what the winnings are for
squares in row 1. For such a square j in row 1, the maximum winnings
there is simply the square's profit: p[1,,j]. What is the maximum winnings for a square in
row 2? For square j in row 2, the maximum winnings will be the maximum
winnings of any square that reach the square at (2, j). In other
words, the recurrence relation must consider the winnings at squares (1,
j-1), (1, j), and (1, j+1).
Once you have the recurrence relation, convince yourself that computing it
top-down results in an algorithm that is at least exponential time.
Your next task is to write a bottom-up dynamic programming pseudocode
algorithm that uses a table to compute the values w[i, j] and, from that,
the maximum possible winnings.
Your solution should also keep track of the route
followed by the checker to achieve the maximum. This can be done
by defining an n-by-n table r where r[i, j] is the column in row i-1 from
which the check got to square (i, j) for the maximum winnings solution for
square (i, j). Note that the first row of the r table will not be
used. In the example below, some of the entries for r are the
following: r[2, 5] is 2 because, to get to the optimal solution for square
(5, 2), the checker had to come from square (4, 2). The variable rstar
is the column in row n where the checker must go for the maximal solution
for the whole problem.
Your last step is to implement your algorithm in a programming
language. I have provided a test program in C++
and a test data file for this.
Figure 1 illustrates an example of the problem. Each square (i, j) contains a
number that is the profit p[i, j]. Note that the rows are numbered
from the bottom and columns are numbered from the left. The maximum
profit for a checker piece for this problem is 176, which it attains by
starting in column 5 of row 1 (profit = 31), moving to column 4 in row 2
(38), then to column 3
in row 3 (42), column 2 in row 4 (4), and, finally, column 2 in row 5 (21)
The route taken by the checker is marked in yellow.
Column
| Row |
| |
1 |
2 |
3 |
4 |
5 |
| 5 |
13 |
21 |
13 |
14 |
25 |
| 4 |
51 |
44 |
25 |
23 |
22 |
| 3 |
18 |
16 |
42 |
24 |
49 |
| 2 |
46 |
21 |
22 |
38 |
16 |
| 1 |
15 |
24 |
13 |
22 |
31 |
Figure 1
|
