algorithm - 优化问题

Question

我太密集了，无法解决以下优化问题:

有一个二维数组，比方说符号与时间

A 1114334221111 
B 9952111111111
C 1113439111131
D 1255432245662

还有一个符号列表，例如:

CABDC

您必须按照符号的顺序从数组中选择值，但您可以根据需要多次重复一个符号。您必须为每个符号至少选择一个值，并且必须遍历整个列表。例如，一种可能是:

  CCCAAAAAABDDC
  1114334221661 = 35

是否有一种算法可以选择总和为最大值的符号列表？乍一看，它看起来像是某种回溯算法，但它可能退化为指数时间。

Answer 1

我可能采用的方法如下所示:

创建 X 的数组(“(N+1)xM ”)元素，其中 N = 二维数组的“宽度”和 M = 列表中的符号数。

设置X[0][i] = 0对于所有值 i (在 M 的范围内)。这是因为前0个选中项的最大可能和为0。我们也可以填写X[a][b]。对于任何 b>=a 为 0因为这些位置是我们不可能到达的位置(我们还没有选择足够的符号来位于该符号处)。类似地，我们也可以将数组尾部的值“三角形”设置为 0，因为为了位于这些索引之一，我们必须选择太多重复的早期符号才能选择至少一项用于以后的符号。

现在，设置X[1][i]如果当前选择的符号是符号 i，则等于前 1 个所选元素的最大可能总和在序列中。这计算起来相当简单 - 它只是数组中该符号的对应值。

现在，设置X[2][i]如果当前选择的符号是符号 i，则等于前 2 个所选元素的最大可能总和在序列中。这也是半平凡的，虽然不像 [1] 那样简单 - 毕竟，现在它是符号的相应值加上 X[1][i-1] 中的最大值。或 X[1][i] - 因为我们可以在这个位置开始当前交易品种，或者已经在更早的位置开始它。

对每个 X[k] 继续算法(设置 X[k][i] 等于 X[k-1][i-1] 或 X[k-1][i] 的最大值，加上当前 i 的相应符号值)直到 k达到 N . X[k] 中的最大值列是您的最大结果。

由于总体而言您只需要查看每个数组元素固定次数，因此总体算法在 O(MN) 中运行。时间。

(请注意，从技术上讲，您不需要一直在内存中存储完整的 NxM 数组，只需要前一列和当前列。用完整数组来解释它更容易。因此，此优化版本算法使用 O(M) 内存。)

示例结果数组:

       0  1  2  3  4  5  6  7  8  9  10 11 12 13
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
0 - C | 0| 1| 2| 3| 6|10|13|22|23|24| 0| 0| 0| 0|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1 - A | 0| 0| 2| 3| 7|10|13|17|24|26|27| 0| 0| 0|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
2 - B | 0| 0| 0| 7| 9|10|11|14|18|25|26|28| 0| 0|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
3 - D | 0| 0| 0| 0|12|16|19|21|23|27|32|38|44| 0|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
4 - C | 0| 0| 0| 0| 0|16|19|28|29|30|31|33|36|45|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+

如果您存储(在每个数组位置)哪个前一个符号被用作该位置总数的一部分，那么很容易通过从右下角到左上角的路径回读来找出最大序列是什么。或者，您可以简单地通过查看两个值中的哪一个(左值或左上值)从您当前的位置开始进行追溯。在这种情况下，最大序列是 CABDDDDDDDDDC。