algorithm - 获得具有一定最小距离/差异的最大整数子集

Question

我有一组整数或示例：{1,3,4,5,10} 现在我想要最大（最大 = 大多数元素）子集，其中每个元素与其他元素的距离/差异最小。

例如，使用 Set {1,3,4,5,10} 和最小距离 2，结果可能是：

{1,3,5,10}

或距离 3：

{1,5,10}

是否存在（良好/有效）算法来解决该问题？

Answer 1

这绝对不是一个 NP 完全问题。

实际上它是经典的Interval Scheduling问题的一个特例，而在普通的Interval Scheduling问题中，长度是不固定的

在您的问题中，您可以查看每个数字是间隔的开始时间，并且每个间隔都有您的“最小距离”作为间隔长度。

每个区间都有一个结束时间，即开始时间+区间长度

所以解决方案是

1 按完成时间对所有区间进行排序。

2 按排序顺序逐一遍历它们，将区间添加到与结果集中所有现有区间兼容的结果集中。

该解决方案是最优的，并且具有 O(nlogn) 时间复杂度。

您可以在上面的链接中找到有关其他贪心算法的证明和信息。

Answer 2

这些方面的东西：

1）对输入进行排序。

2）遍历输入并用如果选择它们将从集合中排除的元素数量标记每个元素。

3) 从可用元素中按顺序选择得分最低的元素。

4) 删除排除的元素。

5) 重复 3) 和 4)

所以，在你的例子中：

1  3  4  5  10     - difference 3

第 1 步已经完成，进入第 2 步，我们得到：

1  3  4  5  10
1  3  2  2  0

说明 - 如果我们选择1，我们排除 1 个数字 -3；如果我们选择3，我们会排除 3 个数字 -1,4 和 5，依此类推...

下一步：

• 选择 10，不删除任何内容。-1 3 4 5 (10)
• 选择 1，删除 3。 -(1) 4 5 (10)
• 选择 4（或 5），删除 5（或 4） -1 4 10

我不保证这行得通，但这是一个开始......

Answer 3

是的，下面的贪心算法给出了最优解。按排序顺序扫描整数，如果前一个整数足够远，则取每个整数。正确性来自一个归纳证明，即对于每个解 S 和每个整数 u，贪心解至少选择与 S 一样多的整数 ≤ u。