时间戳

首页 > 解决方案 > 如何使用动态规划在矩阵中求和

algorithm - 如何使用动态规划在矩阵中求和

问题描述

请，我想找到每行只有一个值的最大总和。我已经通过蛮力做出了决议，它是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套解决方案：

  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

总和：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);

谢谢！

标签： algorithmtime-complexitydynamic-programming

解决方案

你可以O(k*log k)用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, 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离初始节点最近的节点。

推荐阅读