python - 如何选择线段上的点对以最大化每个点对的值的总和？

Question

这是一个可以通过具有O(n^3)复杂性的动态编程来解决的问题，但我想知道是否有更有效的方法来做到这一点。

假设我们在长度为 10 的线段上有以下点

要点：[1, 3, 5, 9]

线段：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

每对点都有一个值，例如：

[1, 3]: 2; [1, 5]: 4; [1, 9]: 3; [3, 5]: 1; [3, 9]: 5; [5, 9]: 3

我们想弄清楚所选点对的最大总和是多少，这样每对点的距离应该小于 5 个点。

在我上面的例子中，（[1, 5]很好但[3, 9]不是）并且不同的对不能相互重叠（[[1, 5], [5, 9]]很好但[[1, 5], [3, 5]]不是）。

这个问题的答案是[[1, 5], [5, 9]]sum 7。

我可以使用动态规划来解决这个问题。我首先选择相对最近的点对和距离最近的点对，直到最远的点对。在进行时，我使用一个n*n矩阵来根据以前的结果保存当前结果。这种动态规划具有时间复杂度O(n^3)。

我想知道是否有更有效的方法可以做到这一点。

标签： pythonalgorithmtime-complexitydynamic-programming

Answer 1

有一个O(R^2)动态编程解决方案（R=坐标范围）。通过进行坐标压缩，可以进一步降低到O(N^2)（N= 对数）。

让我们称L[i][j]具有最大权重的对的权重开始于k >= i并恰好结束于j。L[i][j]可以O(R^2)通过使用递归来计算L[i][j] = max(W[i][j], L[i+1][j])。

现在让我们M[j]用最后一对（我们称之为Q）恰好结束于的附加限制来调用您的问题的答案j。请注意，如果答案由不止一对组成，则答案中必须有另一对以 结尾k < j-1。如果是这样，那么它的解决方案一定是与 forM[j]相同的解决方案M[k]，Q最后附加（否则我们可以M[j]通过使用M[k]来变大）。此外，Q必须从一个坐标开始i > k（因为对是不重叠的），并且它必须是最大的，即它的权重是L[k+1][j]（否则我们可以M[j]通过使用L[k+1][j]而不是变大Q）。还有一种特殊情况M[j]由一对组成，在这种情况下没有这样的k.

有了这一切，我们就可以进行递归了M[j] = max(L[0][j], max(M[k] + L[k+1][j], for k in [1, j-2]))。您可以使用上面M[j]的O(R^2)递归进行计算。

您的问题的解决方案将是max(M[j], for j in [0, R))。要将其归结为O(N^2)，只需对所有坐标（in O(N log N)）进行排序，然后将它们映射到坐标 in [0, 2*N)（O(N)使用散列图），因为唯一对问题重要的是它们的顺序。