How to find the sum in a matrix with dynamic programming

Question

Please, I would like to find the maximum sum with only one value per row. I already made the resolution by brute force and it is O (N^5). Now I would like to find a way with dynamic programming or another way to reduce the complexity.

For example:

Matrix:

  100   5   4   3  1

  90   80  70  60  50

  70   69  65  20  10

  60   20  10   5   1

  50   45  15   6   1

Solution for 5 sets:

1. 100 + 90 + 70 + 60 + 50 = 370

2. 100 + 90 + 69 + 60 + 50 = 369

3. 100 + 90 + 70 + 60 + 45 = 365

4. 100 + 90 + 65 + 60 + 50 = 365

5. 100 + 90 + 69 + 60 + 45 = 364

Sum: 1833

example for the sum with brute force:

  for(int i=0; i<matrix[0].size(); i++) {
    for(int j=0; j<matrix[1].size(); j++) {
      for(int k=0; k<matrix[2].size(); k++) {
        for(int l=0; l<matrix[3].size(); l++) {
          for(int x=0; x<matrix[4].size(); x++) {
            sum.push_back(matrix[0][i] + matrix[1][j] + matrix[2][k] + matrix[3][l] + matrix[4][x]);
          }
        }
      }
    }
  }
  
sort(sum.begin(), sum.end(), mySort);

Thanks!

Answer 1

You can solve it in O(k*log k) time with Dijkstra's algorithm. A node in a graph is represented by a list with 5 indexes of the numbers in the corresponding rows of the matrix.

For example in the matrix

100 5  4  3  1
90  80 70 60 50
70  69 65 20 10
60  20 10 5  1
50  45 15 6  1

the node [0, 0, 2, 0, 1] represents the numbers [100, 90, 65, 60, 45]

The initial node is [0, 0, 0, 0, 0]. Every node has up to 5 outgoing edges increasing 1 of the 5 indexes by 1, and the distance between nodes is the absolute difference in the sums of the indexed numbers.

So for that matrix the edges from the node [0, 0, 2, 0, 1] lead:

• to [1, 0, 2, 0, 1] with distance 100 - 5 = 95
• to [0, 1, 2, 0, 1] with distance 90 - 80 = 10
• to [0, 0, 3, 0, 1] with distance 65 - 20 = 45
• to [0, 0, 2, 1, 1] with distance 60 - 20 = 40
• to [0, 0, 2, 0, 2] with distance 45 - 15 = 30

With this setup you can use Dijkstra's algorithm to find k - 1 closest nodes to the initial node.

Answer 2

If you want just maximum sum, then sum maximum value at each row. That is,

M = [[100, 5, 4, 3, 1],
 [90, 80, 70, 60, 50],
 [70, 69, 65, 20, 10],
 [60, 20, 10, 5, 1],
 [50, 45, 15, 6, 1]]

sum(max(row) for row in M)

Edit

It is not necessary to use dynamic programming, etc.
There is simple rule: select next number considering difference between the number and current number.

Here is a code using numpy.

import numpy as np
M = np.array(M)
M = -np.sort(-M, axis = 1)
k = 3

answer = []
ind = np.zeros(M.shape[0], dtype = int)
for _ in range(k):
    answer.append(sum(M[list(range(M.shape[0])), ind]))
    min_ind = np.argmin(M[list(range(len(ind))), ind] - M[list(range(len(ind))), ind+1])
    ind[min_ind] += 1

Result is [370, 369, 365].

Answer 3

Update I previously used a greedy algorithm, which doesn't work for this problem. Here is a more general solution.

Suppose we've already found the combinations with the top m highest sums. The next highest combination (number m+1) must be 1 step away from one of these, where a step is defined as shifting focus one column to the right in one of the rows of the matrix. (Any combination that is more than one step away from all of the top m combinations cannot be the m+1 highest, because you can convert it to a higher one that is not in the top m by undoing one of those steps, i.e., moving back toward one of the existing combinations.)

For m = 1, we know that the "m highest combinations" just means the combination made by taking the first element of each row of the matrix (assuming each row is sorted from highest to lowest). So then we can work out from there:

1. Create a set of candidate combinations to consider for the next highest position. This will initially hold only the highest possible combination (first column of the matrix).

2. Identify the candidate with the highest sum and move that to the results.

3. Find all the combinations that are 1 step away from the one that was just added to the results. Add all of these to the set of candidate combinations. Only n of these will be added each round, where n is the number of rows in the matrix. Some may be duplicates of previously identified candidates, which should be ignored.

4. Go back to step 2. Repeat until there are 5 results.

Here is some Python code that does this:

m = [
    [100, 5, 4, 3, 1],
    [90, 80, 70, 60, 50],
    [70, 69, 65, 20, 10],
    [60, 20, 10, 5, 1],
    [50, 45, 15, 6, 1]
]
n_cols = len(m[0]) # matrix width

# helper function to calculate the sum for any combination,
# where a "combination" is a list of column indexes for each row
score = lambda combo: sum(m[r][c] for r, c in enumerate(combo))

# define candidate set, initially with single highest combination
# (this set could also store the score for each combination
# to avoid calculating it repeatedly)
candidates = {tuple(0 for row in m)}
results = set()

# get 5 highest-scoring combinations
for i in range(5):
    result = max(candidates, key=score)
    results.add(result)
    candidates.remove(result)  # don't test it again
    # find combinations one step away from latest result
    # and add them to the candidates set
    for j, c in enumerate(result):
        if c+1 >= n_cols:
            continue  # don't step past edge of matrix
        combo = result[:j] + (c+1,) + result[j+1:]
        if combo not in results:
            candidates.add(combo)  # drops dups

# convert from column indexes to actual values
final = [
    [m[r][c] for r, c in enumerate(combo)]
    for combo in results
]
final.sort(key=sum, reverse=True)
print(final)
# [
#     [100, 90, 70, 60, 50]
#     [100, 90, 69, 60, 50], 
#     [100, 90, 70, 60, 45], 
#     [100, 90, 65, 60, 50], 
#     [100, 90, 69, 60, 45], 
# ]