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 .
假设我有一个包含n个整数的数组。如何找到k大小的子集，使子集内的所有整数对的最小距离最大化，我的意思是它们在最远的距离。
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
示例:数组a[]={1,2,6,7,10}和k=3，子集={1,6,10}，最小距离为4，在10到6之间。错误子集:{1,7,10}，最小距离为3{1,2,6}，最小距离为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]
1)排序数组2)选择a[0]，现在在数组中找到ceil(a[0]+ x) = Y然后是ceil(Y+ x)和k-1乘以，第k个元素也会是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
要找到x: dp[i,j]就是从第i个元素中选择j元素的x。最后我们想要dp[n][k]也就是x。
But i am facing problem in finding x .
但是我遇到了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 idp[i,j] = max(min, dp[k,j-1]， dp[i]-A[i] a [i] a [i] a [i] a [i]， i=2 to n,j =2 to i。
dp[i][1] = 0 over i = 1 to n
dp[i][1] = 0 / i = 1到n。
EDIT : I want to correct the dynamic programming solution , though i know x can be found out by binary searching over x .
编辑:我想更正动态规划的解决方案，虽然我知道x可以通过对x的二分查找找到。
UPDATE 2 : I have updated the code , but still not getting correct solution . Please point the error .
code : http://ideone.com/J5vvR9
更新2:我已经更新了代码，但是仍然没有得到正确的解决方案。请指出错误。代码:http://ideone.com/J5vvR9
UPDATE 3 : Thanks @Gassa , @Niklas B. and @Fallen for your answers !.
更新3:感谢@Gassa， @Niklas B.和@ drop for your answer !
3 个解决方案
#1
2
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.
实际上，任何大于最大可能a[i] - a[j]的整数都可以作为一个无穷常数。
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
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).
我认为，如果时间允许搜索x的可能值，那么就没有必要找到x。只需添加外部循环，它将是对答案的二分查找(即，最小距离，我们称它为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.
一旦x是固定的，您可以从[0]开始贪婪地选择值。下一个选择的值将是这样一个[i]， i是最小的，a[i] - a[0] >= x，第三个值是a[j]，这样j是最小的，a[j] - a[i] >= x，等等。如果你能以这种方式选择至少k值，那么实际的答案至少是当前的x;如果不是，答案是小于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.
总运行时间为O (n log (C))，其中C为数组中可能值的总数。如果数组中的整数从0到1000000,C将是1000001,log (C)(整数)将是20。首先，你尝试x = 500000;如果失败，则只剩下范围[0;500000)的答案;如果没有，范围为[500,000;1000000),等等。
#3
1
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.
对x的值进行二分查找，然后对每一个这样的x，编写一个DP/贪婪函数，检查是否有一个带有结果的数组(元素之间的最大距离)大于或等于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.
正确性:如果对于任何X，我们可以有M个元素，这样它们之间的最小距离大于或等于X，那么对于每一个X, X < X，至少这个数组将会是结果。对于任意X，如果没有M元素，那么元素之间的最小距离大于或等于X，那么对于X, X > X, M这些元素都是可用的。我们可以对X进行二分查找。
#1
2
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.
实际上，任何大于最大可能a[i] - a[j]的整数都可以作为一个无穷常数。
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
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).
我认为，如果时间允许搜索x的可能值，那么就没有必要找到x。只需添加外部循环，它将是对答案的二分查找(即，最小距离，我们称它为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.
一旦x是固定的，您可以从[0]开始贪婪地选择值。下一个选择的值将是这样一个[i]， i是最小的，a[i] - a[0] >= x，第三个值是a[j]，这样j是最小的，a[j] - a[i] >= x，等等。如果你能以这种方式选择至少k值，那么实际的答案至少是当前的x;如果不是，答案是小于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.
总运行时间为O (n log (C))，其中C为数组中可能值的总数。如果数组中的整数从0到1000000,C将是1000001,log (C)(整数)将是20。首先，你尝试x = 500000;如果失败，则只剩下范围[0;500000)的答案;如果没有，范围为[500,000;1000000),等等。
#3
1
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.
对x的值进行二分查找，然后对每一个这样的x，编写一个DP/贪婪函数，检查是否有一个带有结果的数组(元素之间的最大距离)大于或等于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.
正确性:如果对于任何X，我们可以有M个元素，这样它们之间的最小距离大于或等于X，那么对于每一个X, X < X，至少这个数组将会是结果。对于任意X，如果没有M元素，那么元素之间的最小距离大于或等于X，那么对于X, X > X, M这些元素都是可用的。我们可以对X进行二分查找。