algorithm - 优化加权区间的总和

Question

我在实线上有 M 个区间，每个区间的权重都是正的。我需要在其中选择 N 以便它们不重叠并给出最大总和。我怎样才能有效地做到这一点？

如果不存在N个非重叠区间的子集，则无解。

没有非重叠约束，问题很简单:选择 N 个最大的权重。由于约束，这不再有效。在我的例子中，N 和 M 很小 (<20)，但我希望有比穷尽所有子集更有效的解决方案。

Answer 1

可以用动态规划来解决。设 C(k, i) 是(最多)k 加权区间的最大总和，其中没有一个的左端小于 i.

您可以将 i 限制在所有区间的(真实)起点集合中，并且 k 的范围从 0 到N.

• 首先将 C(k, max(start for start, end in interval)) 初始化为 0，并将所有其他条目初始化为 -infinity。
• 按起点对间隔进行排序，并向后迭代它们。

• 对于权重为w的每个区间(start, end)，以及对于每个k :

  C(start, k) = max(C(start, k), C(next(start), k), w + C(next'(end), k-1))

这里next(x)返回大于x的最小起点，next'(x)返回大于等于的最小起点x。两者都可以通过二进制搜索(如果 M 较小，则为线性扫描)实现。

总的来说，这将花费 O(M*N*logM) 时间和 O(M*N) 空间。

(假设两端的间隔都没有闭合，因此 (0, 100) 和 (100, 200) 不重叠——如果要将它们视为重叠，则需要进行小幅调整)。