算法找到最窄的间隔，其中m将覆盖一组数字 [英] Algorithm to find the narrowest intervals, m of which will cover a set of numbers

问题描述

假设您有一个 n 号码的列表。您可以选择 m 个整数（可调用整数 a ）。对于每个整数 a ，请删除包含区间[ a - x，a + x ]中的每个数字，其中 x 。

例如，如果您的数字列表

$

b
$ b

1 3 8 10 18 20 25

和m = 2，答案是x = 5。

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

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

代码将是真正有用的，最好是在Java或C ++或C。

解决方案

递归解决方案：

首先，你需要一个估计，你可以分成m组，然后估计x）必须是〜（较大 - 较低元素）/ 2 * m。估计（x）可以是解。如果有一个更好的解决方案，它具有比所有组中的extimated（x）更低的x！您可以使用第一个组检查它，然后递归重复。问题是减少，直到你只有一个组：最后一个，你知道如果你的新解决方案是更好或不，如果有更好，你可以使用它丢弃另一个更糟糕的解决方案。

 私人静态int估计（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 ++）{
 //分割问题：
 int firstGroupX = estimate（n， begin，i）; 
 if（firstGroupX  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）））; 
} 
  

EDIT： b

长数字版本：主要想法，它搜索距离的岛屿，并将问题分为不同的岛屿。

 私有静态长估计（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 = Math.min（bestX，Math.max（firstGroupX，calculate（n，m-1，i，end，bestX））） 
} else {
 i = end; 
} 
} 
 return bestX; 
} 
} 
 
私有静态长解算器（long [] n，long m，int begin，int end）{
长估计=估计，begin，end）; 
 PriorityQueue< long []> islands = new PriorityQueue<>（（p0，p1） - > Long.compare（p1 [0]，p0 [0]）） 
 int islandBegin = begin; 
 for（int i = islandBegin; i  if（n [i + 1] -n [i]> estimate）{
 long estimatedIsland =估计（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 [i] = 2 * n [i-1] +1; 
} 
 long m = 32; 
 Arrays.sort（n）; 
 System.out.println（solver（n，m，0，n.length））; 
} 
  

Let's say you have a list of n numbers. You are allowed to choose m integers (lets call the integer a). For each integer a, delete every number that is within the inclusive range [a - x, a + x], where x is a number. What is the minimum value of x that can get the list cleared?

For example, if your list of numbers was

1 3 8 10 18 20 25

and m = 2, the answer would be x = 5.

You could pick the two integers 5 and 20. This would clear the list because it deletes every number in between [5-5, 5+5] and [20-5, 20+5].

How would I solve this? I think the solution may be related to dynamic programming. I do not want a brute force method solution.

Code would be really helpful, preferably in Java or C++ or C.

解决方案

A recursive solution:

First, you need an estimation, you can split in m groups, then estimated(x) must be ~ (greather - lower element) / 2*m. the estimated(x) could be a solution. If there is a better solution, It has lower x than extimated(x) in all groups! and You can check it with the first group and then repeat recursively. The problem is decreasing until you have only a group: the last one, You know if your new solution is better or not, If there'is better, you can use it to discard another worse solution.

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)));
}

EDIT:

Long numbers version: Main idea, It search for "islands" of distances and split the problem into different islands. like divide and conquer, It distribute 'm' into islands.

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));
}

这篇关于算法找到最窄的间隔，其中m将覆盖一组数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！