我太密集了,无法解决以下优化问题:
例如,有一个2D数组,比如符号与时间
A 1114334221111
B 9952111111111
C 1113439111131
D 1255432245662
还有一个符号列表,例如:
CABDC
您必须按符号的顺序从数组中选择值,但您可以根据需要重复一次符号.您必须为每个符号选择至少一个值,并且您必须完成整个列表.例如,一种可能性是:
CCCAAAAAABDDC
1114334221661 = 35
是否有算法选择总和为最大值的符号列表？在第一次脸红时它看起来像某种回溯算法,但这可能会退化到指数时间.
我可能会采取的方法如下:
创建一个元素数组(" X")(N+1)xM,其中N= 2D数组的"宽度"和M=列表中的符号数.
设置X[0][i] = 0所有值i(在范围内M).这是因为前0个所选项目的最大可能总和为0.我们也可以填写X[a][b]为0,b>=a因为那些位置是我们无法达到的位置(我们不会选择足够的符号来处理那个符号).类似地,我们可以将数组尾端的值的"三角形"设置为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.