The algorithm utilized in this program was written to solve the problem described below:
In this problem, you are given a matrix of positive integers, and your goal is to maximize a sum by selecting one element from every column in the matrix, moving left-to-right. As you move through the matrix column-by-column, though, there may be a penalty to your sum depending on how you move relative to your previous two positions. If the next row you select is between the previous two selected rows, there is no penalty; however, there is a penalty of 2 to your sum for every row above the maximum of the previous two or below the minimum of the previous two. You always start in the first column of the matrix and your previous two rows are considered to be the top row.
If you start with row 3 in column 1 of the matrix, there will be a penalty of 4, because 3 is two more than max(1, 1). If you then move to row 2 in column 2, there would be no penalty becuase 2 is between 1 and 3. If you then moved to row 7, there would be a penalty of 8 because 7 is 4 more than max(2, 3).
The total "score" of the elements you select from the matrix will be the sum of the elements you selected, minus any penalties you accrued, and your algorithm should find the maximum possible score for the given matrix.
Consider the 3 x 4 matrix below:
The best score we can make for this matrix is 13 by choosing rows 2, 3, 3, 3 (3 + 3 + 3 + 4) from left-to-right.
This problem / project was given at the University of South Florida College of Engineering COT4400 Analysis of Algorithms course. It is an exercise in the use of dynamic programming. For a matrix with
rows and
columns, where your previously selected rows are
and
, you can break down a problem instance recursively by finding the maximum traversal of sub matrices with fewer columns. For every column, consider the maximum sums you can accumulate for a matrix only consisting of the next
columns, based on all the possible row choices for the current column, and the previous column. Continue this process until there is simply one column remaining, at which point you can simply find how much score each row choice will contribute based on the penalties, and for each
and
permutation, choose the row which will contribute the most and store that result, because that choice will always be the best choice for the prior
and
. Then, work backwards for each column choosing the best possible row choice for every column, back to the original matrix, at which that point the best choice in this final column will be the maximum score possible. This process can be described mathematically in the recurrence below, where
is a function to calculate the penalty for each row choice:
The program contains code for both a memoized solution and an iterative solution, and randomly calls one to find the maximum sum. The program will output both the maximum score as well as the rows chosen to reach the necessary maximum sum to an "output.txt" file. The input format is simply a text document ("input.txt") containing a line of two integers n and m, representing the number of rows and columns, respectively. Then, the following n lines contain m integers, representing the matrix as you would expect to see in the typical representation. Feel free to create your own input.txt files to test out the program. It should be noted however that input validation was not considered for this program, as it was to simply develop a dynamic programming algorithm.
The original recursion without the use of dynamic program results in an algorithm, however saving sub results actually reduces the algorithm to a poly-time complexity of
. Feel free to message me on how these complexities are derived.