寻找大小为k的子集，使得其中任意两个值之间的最小距离最大化。

Question

假设我有一个包含n个整数的数组。
如何找到大小为k的子集，使得子集中所有整数对之间的最小距离最大化，也就是它们之间的距离最远。

例如：数组a[]={1,2,6,7,10}，k=3， 子集={1,6,10}，最小距离为10和6之间的4。 错误的子集： {1,7,10}，最小距离为3 {1,2,6}，最小距离为1

我想出了一个解决方案：

1）对数组进行排序 2）选择a[0]，现在在数组中查找ceil(a[0]+x)=Y....然后再查找ceil(Y+x)等等，重复k-1次，第k个元素将是a[n-1]。

为了找到 x：
设dp [i，j]为从前i个元素中选择j个元素的x.
最后我们要找到的是dp [n，k]，它就是x。

但是我在寻找x时遇到了问题。

当i = 2至n，j = 2至i时，等式如下：
dp [i，j] = max（min（dp [k，j-1]，dp [i] - A [k]））
其中k = 1到i-1。

i = 1到n时，等式为：
dp [i，1] = 0

编辑：我想纠正这个动态规划解决方案，尽管我知道可以通过对x进行二进制搜索来找到它。

更新2：我已经更新了代码，但仍然没有得到正确的解决方案。请指出错误。
代码 ：http://ideone.com/J5vvR9

更新3： 感谢@Gassa，@Niklas B.和@Fallen的回答！

- Aseem Goyal

---

如果您只想使用动态编程完成此操作，则需要另一个参数x。因为状态将是当前索引（i）、迄今选取的元素数量（j）和迄今为止的最小距离（x）。 - Fallen

是的，这看起来是可行的（但与二分搜索相比效率不高，但这取决于您的判断）。将抽象DP状态定义为（i、j、k、x）：排序后，我们查看了前i个值，选择了其中j个值，最后一个选择的是k，到目前为止最小距离为x。这些状态对应于布尔值（状态是否可达）。从这里，我们可以注意到某些单调性：例如，如果（i、j、k、x）是可达的，则（i、j、k、x + 1）也是可达的，（i、j-1、j、x）也是如此。因此，您可以进行DP（i、j、k）-> min x或另一个（i、k、x）-> max k等。 - Gassa

@Gassa 我们可以定义状态 (i, j)，使得 i 被确定选择。这将产生一个 O(nk) 的算法（我想这就是 OP 尝试的算法）。 - Niklas B.

@Niklas B.：不是最大值，而是最小值。因此，在初始化中存在错误（请参见我的其他答案）。 - Gassa

@Gassa，dp(i, j) 是在选择 i 和 j 之前的 j-1 个元素时最大化的距离。这就是我的意思 :) - Niklas B.

Answer 1

基础应该是：

必须是：

dp[i][1] = INFINITY for i = 1 to n

这是因为一个空集的最小值为正无穷（extended real numbers）。

实际上，对于一些i和，任何大于可能的最大a[i] - a[j]的整数都足以作为无穷常量INFINITY。

另外，正确的转换应该是：

dp[i,j] = max{for k=1 to i-1} (min(dp[k,j-1], a[i]-a[k]))

- Gassa

---

抱歉，但我仍然无法得到正确的答案，我的代码在这里http://ideone.com/J5vvR9。 - Aseem Goyal

@aseem：对于“不可能”的情况，您必须使用负无穷大。例如，在您的程序中，dp [1,2] = infinity，您将其用作子结果。 - Niklas B.

1. 你的 o = -1; 初始化代码应该在两个循环内部。
2. 你的 i 和 j 循环边界不正确。也许将上三角形设为 -1 是 DP 基础的一部分，正如 @Niklas B. 所述。
3. 这里 是一个已经修正的版本。

- Gassa

Answer 2

我认为如果时间允许搜索x的可能值，就没有必要寻找 x 。只需添加外部循环，它将是答案（即最小距离，我们称其为x）的二进制搜索。

一旦确定了x，您可以贪心地选择从a [0]开始的值。下一个选择的值将是这样的a [i]，即i最小且a [i] - a [0]> = x 。第三个将是a [j]，使得j最小且a [j] - a [i]> = x 等等。如果您能以这种方式至少选择k个值，则实际答案至少为当前的x；否则，答案小于x。

总运行时间将为O（n log（C）），其中C是数组中可能值的总数。例如，如果数组中的整数是从0到1000000，那么C将是1000001，log（C）（向上取整）将是20。首先，您尝试x = 500000；如果失败，则剩下的范围为[0; 500000）作为答案；如果不是，则为[500000; 1000000]等。

- Gassa

---

请解释如何改进 DP 解决方案。 - Aseem Goyal

@NiklasB.：请仔细观察，因为就逻辑而言它是正确的，我无法找到基本情况。 - Aseem Goyal

@aseem 那么这个数组是已经排序好的吗？请在问题中包含这种信息。 - Niklas B.

@NiklasB：是的，数组已经排序。 - Aseem Goyal

Answer 3

进行 X 值的二分查找。然后，针对每个 x，编写一个 DP/Greedy 函数来检查是否存在一个数组，其结果（元素之间的最大距离）大于或等于 X。

正确性：如果存在任何 X，我们可以有 M 个元素，它们之间的最小距离大于或等于 X，则对于每个 x，x < X，至少该相同的数组将作为结果。对于任何 X，如果没有 M 个元素，这些元素之间的最小距离大于或等于 X，则对于任何 x，x > X，都不可能有这样的 M 个元素可用。因此，我们可以在 X 上进行二分查找。

- Fallen

---

请解释如何改进 DP 解决方案。 - Aseem Goyal

@aseem：对于这个问题，最好、最直接的解决方案是由Gassa提供的。至少我不知道有更有效的 DP 解决方案。 - Fallen