如何用动态规划求矩阵和

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)

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

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

更新我之前使用了贪婪算法，它不适用于这个问题。这是一个更通用的解决方案。

假设我们已经找到了具有前m个最高和的组合。下一个最高组合（数字m 1）必须距离其中一个1步，其中一个步骤被定义为将焦点在矩阵的一行中向右移动一列。（任何距离所有前m个组合超过一步的组合都不能是最高的m 1，因为您可以通过撤消其中一个步骤将其转换为不在前m的更高的组合，即向后移动到现有组合之一。）

对于m=1，我们知道“m个最高组合”只是指通过取矩阵每行的第一个元素进行的组合（假设每行从最高到最低排序）。然后我们可以从那里得出：

>

创建一组候选组合以考虑下一个最高职位。这将最初仅包含可能的最高组合（矩阵的第一列）。

确定总和最高的候选人，并将其移至结果。

找到与刚刚添加到结果中的组合相差一步的所有组合。将所有这些添加到候选组合集中。每轮只添加其中的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], 
# ]

Answer 3

你可以用Dijkstra算法在时间上求解它。图中的节点由一个列表表示，该列表在矩阵的相应行中包含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, 0, 0, 0]。每个节点最多有5条传出边，将5个索引中的1个增加1，节点之间的距离是索引数和的绝对差。

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

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

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