找到大小为k的子集，使得值之间的最小距离最大 [英] Find subset of size k such that the minimum distance between values is maximum

问题描述

假设我有包含 N 整数数组。结果
如何找到大小 K 使得最小所有成对子集中整数之间的距离为<$ C子集$ C>最大化，我的意思是他们是在最远的距离。

Suppose i have an array which contain n integers .
How to find subset of size k such that the minimum distance between all pairs of integers in the subset is maximized , i mean they are at farthest distance .

例如：阵列 A [] = {1,2,6,7,10} 和 K = 3 ，结果
子= {-1,6,10} ，最小距离为 4 10和6之间。结果
错误的子集：结果
{1,7,10} ，最小距离为 3 结果
{1,2,6} ，最小距离为 1

example : array a[]={1,2,6,7,10} and k=3 ,
subset = {1,6,10} , the minimum distance is 4 between 10 and 6 .
Wrong subsets :
{1,7,10} , minimum distance is 3
{1,2,6} , minimum distance is 1

我想出了一个解决方案：

I came up with a solution :

1）排序数组结果
2）选择[0]，现在发现CEIL（A [0] + X ）= Y阵....然后CEIL（Y + X ）等 K-1 倍，也第k个元素将是 A [N-1]

1) sort array
2) select a[0] , now find ceil(a[0]+ x) = Y in array ....and then ceil(Y+ x) and so on k-1 times , also kth element will be a[n-1]

要找到 X ：结果
DP [I，J] 是 X 从第i个元素的选择Ĵ元素。结果
最后，我们希望 DP [N] [K] 是 X

To find x :
dp[i,j] be the x for selecting j elements from first i elements .
Finally we want dp[n][k] which is x

但我在寻找面临的问题 X 。

But i am facing problem in finding x .

DP [I，J] =最大值（分钟（DP [K，J-1]，DP [I] -A [k]的））结果
                  用K = 1到i-1，i = 2到N，J = 2至i

dp[i,j] = max( min( dp[k,j-1], dp[i]-A[k] ) )
over k=1 to i-1 , i=2 to n , j=2 to i

DP [I] [1] = 0比I = 1到n

dp[i][1] = 0 over i = 1 to n

修改：我要纠正在动态规划解决方案，但我知道x可以通过X上的二进制搜索来发现。

EDIT : I want to correct the dynamic programming solution , though i know x can be found out by binary searching over x .

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

UPDATE 2 : I have updated the code , but still not getting correct solution . Please point the error .
code : http://ideone.com/J5vvR9

更新3 ：谢谢@Gassa，@Niklas B.和@Fallen你的答案

UPDATE 3 : Thanks @Gassa , @Niklas B. and @Fallen for your answers !.

推荐答案

基础应该是：

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

原因是，的rel=\"nofollow\">是正无穷大。

The reason being that minimum of an empty set is positive infinity.

在实践中，任何整数大于最大可能较大 A [I] - 一个[J] 一些 I 和Ĵ将足以为 INFINITY 不变。

In practice, any integer larger than the maximum possible a[i] - a[j] for some i and j will suffice as an INFINITY constant.

此外，正确的转型将是：

Additionally, the correct transition would be:

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

这篇关于找到大小为k的子集，使得值之间的最小距离最大的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！