如何使用动态规划求矩阵中的和

Question

拜托，我想找到每行只有一个值的最大总和。我已经通过蛮力做出了决议，它是O（N ^ 5）。现在我想找到一种动态规划的方法或其他降低复杂性的方法。

例如：

矩阵：

  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

5组的解法：

100 + 90 + 70 + 60 + 50 = 370
100 + 90 + 69 + 60 + 50 = 369
100 + 90 + 70 + 60 + 45 = 365
100 + 90 + 65 + 60 + 50 = 365
100 + 90 + 69 + 60 + 45 = 364

总数：1833

暴力求和示例：

  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);

谢谢！

Answer 1

如果您只想要最大总和，则对每行的最大值求和。也就是说，

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)

编辑

没有必要使用动态规划等。
有一个简单的规则：select 下一个数字，考虑数字与当前数字之间的差异。

这是使用 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

结果是 [370, 369, 365]。

Answer 2

您可以在 O(k*log k) 时间内用 Dijkstra's algorithm 解决它。图中的节点由一个列表表示，该列表具有矩阵相应行中数字的 5 个索引。

例如在矩阵中

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

节点[0, 0, 2, 0, 1]代表数字[100, 90, 65, 60, 45]

初始节点为[0, 0, 0, 0, 0]。每个节点最多有5条出边，5个索引中的1个增加1，节点之间的距离是索引数之和的绝对差。

因此对于该矩阵，节点 [0, 0, 2, 0, 1] 的边领先：

到 [1, 0, 2, 0, 1] 距离为 100 - 5 = 95
到 [0, 1, 2, 0, 1]，距离为 90 - 80 = 10
到 [0, 0, 3, 0, 1] 距离为 65 - 20 = 45
到 [0, 0, 2, 1, 1] 距离为 60 - 20 = 40
到 [0, 0, 2, 0, 2]，距离为 45 - 15 = 30

通过此设置，您可以使用 Dijkstra 算法找到离初始节点最近的 k - 1 个节点。

Answer 3

Update 我之前用的是贪心算法，这个问题不行。这是一个更通用的解决方案。

假设我们已经找到了总和最高 m 的组合。下一个最高组合（数字 m+1）必须与其中之一相距 1 步，其中一步定义为将焦点向右移动一列中的其中一行矩阵。（任何距离所有top m组合超过一步的组合都不可能是最高的m+1，因为你可以转换它通过撤消这些步骤之一，即返回现有组合之一，到不在顶部 m 中的更高组合。）

对于m = 1，我们知道“m最高组合”就是取第一个元素的组合矩阵的每一行（假设每一行从最高到最低排序）。那么我们可以从那里算出来：

创建一组候选组合以考虑下一个最高位置。这最初将只包含最高可能的组合（矩阵的第一列）。
确定总和最高的候选者并将其移至结果中。
找到与刚刚添加到结果中的组合相差 1 步的所有组合。将所有这些添加到候选组合集中。每轮只会添加其中的 n，其中 n 是矩阵中的行数。有些可能与之前确定的候选人重复，应忽略。
返回步骤 2。重复直到有 5 个结果。

下面是执行此操作的一些 Python 代码：

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], 
# ]

如何使用动态规划求矩阵中的和

How to find the sum in a matrix with dynamic programming

algorithm

dynamic-programming

time-complexity

编辑