找到最窄间隔的算法，其中 m 将覆盖一组数字

Question

假设您有一个包含 n 个数字的列表。您可以选择 m 个整数（我们称整数为 a）。对于每个整数 a，删除包含范围 [a - x, a + x] 内的每个数字，其中 x 是一个数字。 x的最小值是多少才能清除列表？

例如，如果您的号码列表是

1 3 8 10 18 20 25

且 m = 2，则答案为 x = 5。

您可以选择 5 和 20 这两个整数。这会清除列表，因为它会删除 [5-5, 5+5] 和 [20-5, 20+5] 之间的所有数字。

我该如何解决这个问题？我认为解决方案可能与动态规划有关。我不想要暴力方法解决方案。

代码会很有帮助，最好是 Java 或 C++ 或 C。

Answer 1

一个有效的算法可以是（假设列表已排序）->

我们可以将列表视为一组 'm' 个整数。
现在为每个组计算 'last_element - first_element+1'，并将该值的最大值存储在变量中，比如 'ans'。
现在'x'的值为'ans/2'。

我希望它很清楚这个算法是如何工作的。

Answer 2

我认为这是类似的聚类问题。例如，您可以使用 k-means 聚类算法：在 m 类上对初始列表进行分区，对于 x 得到最大大小除以获得的类.

的二分之一

Answer 3

提示

假设你有列表

1 3 8 10 18 20 25

想知道如果 x 等于 2 需要多少组来覆盖集合。

您可以通过选择第一个整数为 1+x（1 是列表中的最小数字）以贪婪的方式解决此问题。这将涵盖最多 1+x+x=5 的所有元素。然后简单地重复这个过程，直到所有的数字都被覆盖。

所以在这种情况下，下一个未覆盖的数字是 8，所以我们会选择 8+x=10 并覆盖第二组中直到 10+x=12 的所有数字。

同理，第三组覆盖[18,24]，第四组覆盖[25,29]。

这个x值需要4组。这太多了，所以我们需要增加 x 再试一次。

您可以使用二分法来确定确实涵盖 m 组中所有数字的 x 的最小值。

Answer 4

一个递归的解决方案：

首先，你需要一个估计，你可以分成m组，然后估计(x)必须是~(大-低元素)/2*m。 estimated(x) 可能是一个解决方案。如果有更好的解决方案，它在所有组中的 x 都低于 extimated(x) ！你可以用第一组检查它，然后递归重复。问题一直在减少，直到你只有一组：最后一个，你知道你的新解决方案是否更好，如果有更好的，你可以用它来丢弃另一个更差的解决方案。

private static int estimate(int[] n, int m, int begin, int end) {
    return (((n[end - 1] - n[begin]) / m) + 1 )/2;
}

private static int calculate(int[] n, int m, int begin, int end, int estimatedX){
    if (m == 1){
        return estimate(n, 1, begin, end);
    } else {
        int bestX = estimatedX;
        for (int i = begin + 1; i <= end + 1 - m; i++) {
            // It split the problem:
            int firstGroupX = estimate(n, 1, begin, i);
            if (firstGroupX < bestX){
                bestX = Math.min(bestX, Math.max(firstGroupX, calculate(n, m-1, i, end, bestX)));
            } else {
                i = end;
            }
        }
        return bestX;
    }
}

public static void main(String[] args) {
    int[] n = {1, 3, 8, 10, 18, 20, 25};
    int m = 2;
    Arrays.sort(n);
    System.out.println(calculate(n, m, 0, n.length, estimate(n, m, 0, n.length)));
}

编辑：

长数字版本：主要思想，它搜索 "islands" 的距离并将问题拆分为不同的岛。就像分而治之，它将 'm' 分配到岛屿。

private static long estimate(long[] n, long m, int begin, int end) {
    return (((n[end - 1] - n[begin]) / m) + 1) / 2;
}

private static long calculate(long[] n, long m, int begin, int end, long estimatedX) {
    if (m == 1) {
        return estimate(n, 1, begin, end);
    } else {
        long bestX = estimatedX;
        for (int i = begin + 1; i <= end + 1 - m; i++) {
            long firstGroupX = estimate(n, 1, begin, i);
            if (firstGroupX < bestX) {
                bestX = Math.min(bestX, Math.max(firstGroupX, calculate(n, m - 1, i, end, bestX)));
            } else {
                i = end;
            }
        }
        return bestX;
    }
}

private static long solver(long[] n, long m,  int begin, int end) {
    long estimate = estimate(n, m, begin, end);
    PriorityQueue<long[]> islands = new PriorityQueue<>((p0, p1) -> Long.compare(p1[0], p0[0]));
    int islandBegin = begin;
    for (int i = islandBegin; i < end -1; i++) {
        if (n[i + 1] - n[i] > estimate) {
            long estimatedIsland = estimate(n, 1, islandBegin, i+1);
            islands.add(new long[]{estimatedIsland, islandBegin, i, 1});
            islandBegin = i+1;
        }
    }
    long estimatedIsland = estimate(n, 1, islandBegin, end);
    islands.add(new long[]{estimatedIsland, islandBegin, end, 1});
    long result;
    if (islands.isEmpty() || m < islands.size()) {
        result = calculate(n, m, begin, end, estimate);
    } else {    
        long mFree = m - islands.size();
        while (mFree > 0) {
            long[] island = islands.poll();
            island[3]++;
            island[0] = solver(n, island[3], (int) island[1], (int) island[2]);
            islands.add(island);
            mFree--;
        }
        result = islands.poll()[0];
    }
    return result;
}

public static void main(String[] args) {
    long[] n = new long[63];
    for (int i = 1; i < n.length; i++) {
        n[i] = 2*n[i-1]+1;
    }
    long m = 32;
    Arrays.sort(n);
    System.out.println(solver(n, m, 0, n.length));
}

Answer 5

1) 您应该研究关于时间和 SPACE 算法复杂性的最佳情况、平均情况和最坏情况复杂性。

2) 我认为 David Pérez Cabrera 的想法是正确的。让我们假设平均情况（如下面的伪代码）

3) 令整数列表由 l

表示

    keepGoing = true
    min_x = ceiling(l[size-1]-l[0])/(2m)

    while(keepGoing)
    {
        l2 = l.copy
        min_x = min_x-1
        mcounter = 1

        while(mcounter <= m)
        {
            firstElement = l2[0]
//  This while condition will likely result in an ArrayOutOfBoundsException
//  It's easy to fix this.

            while(l2[0] <= firstElement+2*min_x)
            {   remove(l2[0])   }
            mcounter = mcounter+1
        }
        if(l2.size>0)
            keepGoing = false
    }
    return min_x+1

4) 考虑

l = {1, 2, 3, 4, 5, 6, 7}, m=2 (gives x=2)
l = {1, 10, 100, 1000, 10000, 100000, 1000000}, m=2
l = {1, 10, 100, 1000, 10000, 100000, 1000000}, m=3

找到最窄间隔的算法，其中 m 将覆盖一组数字

Algorithm to find the narrowest intervals, m of which will cover a set of numbers

c++

java

algorithm

knapsack-problem

dynamic-programming

提示