0
votes

Say there's a matrix with N rows and M columns.

You start the traversal at the bottom left, and your current points P is 0, and space S which is larger than 0. At each point in the matrix, the coordinate is either empty or contains points. If the points have size X and value V, you can choose to pick up the points or not when you reach a coordinate.

For traversing the matrix, we can only go up by one row and choose from one of the three columns (i.e. (i + 1, j − 1), (i + 1, j), or (i + 1, j + 1))

Picking up the points increases P by V and decreases S by X.


I'm trying to write a dynamic programming algorithm that would traverse this and return the best path resulting in the largest number of points.

I figure the subproblems are:

L(N, j) = Null
L(i, 0) = max(L(i + 1, 0), L(i + 1, 1))
L(i, j) = max(L(i + 1, j − 1), L(i + 1, j), L(i + 1, j + 1))
L(i, M) = max(L(i + 1, j - 1), L(i + 1, j))

Would that work? How would I go about introducing this to an algorithm?

1

1 Answers

0
votes

You can do it in two ways :

  1. Recursive call for function which should cover all boundary/edge conditions For example the function call would look like this :

    function L(i,j, p, s) :
    if(i<0 or j<0)    return -1 #edge case
    if(s<0)           return -1 #out of space
    if(p<0)           return 0  #no possible outcome
    if (s == 0)       return p  #the end
    else              return max{L(i + 1, j − 1, p+v, s-x), L(i + 1, j, p+v, s-x), L(i + 1, j + 1, p+v, s-x)}
    
  2. Iterative with tracking with (s<0) condition and you can maintain the matrix for max S and P values for each step.