代码之家 › 专栏 › 技术社区 › sehugg

优化问题

algorithm

sehugg · 技术社区 · 17 年前

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

有一个二维数组,比如说符号与时间的关系

A 1114334221111 
B 9952111111111
C 1113439111131
D 1255432245662

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

CABDC

  CCCAAAAAABDDC
  1114334221661 = 35

是否有一个算法来选择符号列表中的最大值?乍一看,它看起来像某种回溯算法,但这可能退化为指数时间。

5 回复 | 直到 17 年前

Amber 17 年前

我可能会采取这样的方法:

X )的 (N+1)xM N =二维数组的“宽度”,以及 M =列表中的符号数。

设置 X[0][i] = 0 对于所有值i(在 )。这是因为前0个选定项目的最大可能总和为0。我们也可以填写 X[a][b] 任何情况下都为0 b>=a 因为这些位置是我们不可能到达的(我们还没有选择足够的符号到达那个符号)。类似地,我们也可以将数组末尾的“三角形”值设置为0,因为为了达到其中一个索引,我们必须选择太多重复的早期符号,以便能够为后续符号选择至少一项。

现在,开始 X[1][i] 如果当前所选符号为symbol,则等于前1个所选元素的最大可能总和 i

现在,开始 X[2][i] 如果当前所选符号为symbol,则等于前2个所选元素的最大可能总和 我 按顺序。这也很简单,虽然不像[1]那样简单——毕竟,现在它是符号加的对应值 X[1][i-1] 或 X[1][i] -因为我们可以从这个位置开始当前符号,或者已经从更早的位置开始。

对每个问题继续执行算法 X[k] (背景) X[k][i] X[k-1][i-1] 或 X[k-1][i] ,加上当前的相应符号值 我 )直到 k N . 您的应用程序中的最大值 X[k] 列是您的最大结果。

O(MN) 时间

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|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+

如果(在每个数组位置)存储前一个符号作为该位置总数的一部分,则很容易通过从右下角到左上角的轨迹读回,以确定最大序列是什么。或者,您可以通过查看两个值中的哪个值(左或左上)比您当前的位置大来简单地追溯。在这种情况下,最大序列是CABDDDDC。

Fragsworth 17 年前

在我看来,这似乎是一个轻微的变化 shortest path

Nimantha Thatkookooguy 6 年前

你可以把它变成一个最短路径问题,但与Fragsworth所说的不同,你不需要改变算法,只需要改变数据的呈现方式。

您不会连接不遵循规则的节点(您不会将b[4]连接到a[5],因为它不在列表“顺序”中)。

例子 :

c[0]连接到权重为9的c[1](10-c[1]值为1)=>这是选择“C”的选项

c[0]连接到权重为9的[1](10-a[1]值为1)=>这

b[2]连接到b[3],权重为8(10-b[3]值为2)=>这是选择“B”的选项

b[2]连接到权重为5的d[3](10-d[3]值为5)=>这

您遇到的唯一问题是,您一直选择“CCCCC…”这个选项,而在您的示例中,通过将“CABDC”列表中的第二个“C”称为(C2)并仅将其从D节点(或其他C2节点)连接来抵消。

现在运行一个任意标准最短路径算法(无需更改),从c[0]开始,到c2[n]结束,因为权重与值相反,所以得到的最短路径将是最大值之和。

Samuel Carrijo 17 年前

你可以选择贪婪算法,但有一些限制。您必须始终在当前符号或下一个符号之间进行选择。如果当前符号的等效值大于下一个符号(并且您可以稍后放置所有剩余符号),则使用当前符号。如果下一个符号号更大,则选择下一个。如果它们相同,则需要一些额外的逻辑来决定。

Unknown 17 年前

是否有一个算法来选择符号列表中的最大值?

您对符号的数量或每个符号的使用都没有限制。

( )

for i through the length of array in time
    symbol, value = get_max_value(array[i]) # iterates through every symbol to find max at the given time
    print symbol, value