How do I write pseudocode for the general case?
I'm about to start learning so I decided to work on some old problems from my algorithms class. The problem is this:
You sell newspapers and every day you start your route at one intersection and end your route = northeast of where you started. The city streets are on the grid as shown below and start at (0, 0) and end at (n, m).
Going north will take you from (x, y) to (x, y +1). Going east will take you from (x, y) to (x +1, y). At each intersection (x, y), you will stop selling newspapers and will receive income from r (x, y). Let OPT (n, m) denote the total income of the optimal transition from (0, 0) to (n, m).
My pseudocode using bottom-up dynamic programming for this problem looks like this:
Bottom-Up-Alg(n,m,s[][]) \\ n and m are coordinates and s holds the revenue at each coordinate (n,m)
opt = 0 \\ holds optimal revenue
opt += s[0][0] \\value at (0,0)
i = 0
j = 0
while (i <= n and j <= m)
if (s[i+1][j] > s[i][j+1])
opt += s[i+1][j] \\ Move east
i++
else
opt += s[i][j+1] \\ Move north
j++
return r
Strictly speaking, the running time of this algorithm would be O (n + m). But if n and m are proportional, then the running time can be called O (n) or O (m).
The problem is that I found that my algorithm is greedy and it won't work for every situation. I am having trouble writing pseudocode that will work in general.
source to share
You can list each node, starting from the top right node, with the maximum return you can get if you start from that node and which up to the node gives it that maximum. O (nm).
You do this by sweeping the diagonal from top right to left.
When this numbering reaches the bottom left corner, you have an answer. Just follow through.
22 19-17-15--9
|
27 26 17 16 14
|
35-32 22 22 20
ADDED: If you're wondering how to sweep a diagonal, it's easier to visualize than code.
But here's some C:
for (j = m-1; j >= -(n-1); j--){
for (ii = n-1; ii >= 0; ii--){
int jj = j + (n-1) - ii;
int rii = rjj = 0;
if (jj >= 0 && jj < m){
if (ii+1 < n && jj >= 0 && jj < m)
rii = r[ii+1][jj];
if (jj+1 < m && jj+1 >= 0)
rjj = r[ii][jj+1];
r[ii][jj] = s[ii][jj] + max( rii, rjj );
}
}
}
Basically, ii
and jj
are the indices of the cell you are working on, and if its right or top neighbor is outside the rectangle, you get its income as zero.
source to share
This is your TA. I couldn't help but notice that this question was posted before your homework deadline. Seeing that it passed that date, the answer you were looking for is the following
BOTTOM-UP-NEWSPAPER(n,m,r)
opt = array(n,m)
for i = 0 to n
for j = 0 to m
if i = 0 and j = 0 // In starting position
opt[i][j] = r(i,j)
else if i = 0 and j > 0 // On the south side of grid
opt[i][j] = r(i,j) + opt[i][j-1]
else if j = 0 and i > 0 // On the west side of grid
opt[i][j] = r(i,j) + opt[i-1][j]
else // Anywhere else
opt[i][j] = r(i,j) + max(opt[i-1][j], opt[i][j-1])
opt[n][m] holds the maximum revenue
source to share
Your algorithm works because it is similar to Dijkstra's algorithm, but to find the longest path on an acyclic graph with a forward acyclic, where each node has two directed edges. The algorithm calls the critical path in a greedy way.
The running time should be O (mn). It's like editing a distance tracking routine.
source to share