Find subset of size k such that the minimum distan

问题:

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 .

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) 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]

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

But i am facing problem in finding x .

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 over i = 1 to n

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

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

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

回答1:

The base should be:

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

The reason being that minimum of an empty set is positive 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]))

回答2:

I think there is no need in finding x if time allows to search for possible values of x. Just add the outer loop which will be a binary search on the answer (that is, the minimum distance, let us call it x).

Once x is fixed, you can greedily pick values starting from a[0]. The next selected value will be such a[i] that i is minimal and a[i] - a[0] >= x. The third one will be a[j] such that j is minimal and a[j] - a[i] >= x, and so on. If you are able to pick at least k values in this fashion, the actual answer is at least the current x; if not, the answer is less than x.

The total running time will be O (n log (C)) where C is the total number of possible values in the array. Say, if the integers in the array are from 0 to 1000000, C will be 1000001 and log (C) (rounded up) will be 20. First, you try x = 500000; if it fails, you are left with the range [0; 500000) for the answer; if not, with the range [500000; 1000000], etc.

回答3:

Do a binary search over value of X. Then for each such x, write a DP/Greedy function that checks if there's an array with result(maximal distance between elements) more than or equal to X.

Correctness: If for any X, we can have M elements, such that minimum distance between them is greater than or equal to X, then for every x, x < X, at least this same array will server as result. And for any X, if there's no M elements, such that the minimum distance between the elements is greater than or equal to X, then for no x, x > X, M such elements are available. So we can binary search on X.