将整数数组分成K组，使每组的范围最小

Question

所以，更正式地说，我得到了N个数字，需要把它们分成K个组，这些组中没有一个是空的。每组中的范围总和需要是最小的。例如：

N= 4，K=2，输入为{5,3,1,1}。

一种可能的解决方案是{5,3}，{1,1}。范围的和是2 ((5-3)+(1-1))。

另一种方法是{1,1,3}{5}，它也是2((3-1)+(单个数字的范围是0))。

范围始终是组中最大的数字和组中的最小数字之间的差。

当我在互联网上搜索时，很明显我需要使用动态编程，但我想到的都是K=2的解决方案。

有人能帮帮忙吗？

Answer 1

使用动态编程，您得到了k= 2的解决方案。现在考虑如何将其扩展到k= 3。

假设f2(n)返回k=2和前n个数的最优解，f3(n) = f2(n-m) + err(n-m，n)。这是扩展它的一种方式。

Answer 2

假设您的数据已经排序，您可以在线性时间内完成此操作。

您可以在min_value和max_value之间的轴上查看数据。简单地说，聪明的解决方案不使用不连续的组，因此任何聪明的解决方案都可以表示为轴上的一组K段，每个段[x1, x2]表示x1和x2之间的数据中的所有数字。

您的解决方案的总成本是所有数据段长度的总和，也是max_value - min_value - (space between all your segments)。段之间的空格本身是由K - 1“空段”组成的，也就是说，其中没有你的输入数字，即两个连续输入数字之间的段。你想要的是最大化K - 1这类段的长度总和。

所以你所要做的就是(简单版本)：

如果需要，对所有i的inputs

• compute Bi = Ai+1 - Ai进行排序(A是排序后的输入，B的K-1个最大值(仍然是线性时间，实际上可以与上一步同时完成)

• 这些是组的边界，因此您只需再次迭代A即可创建组本身(现在您有了边界)(此步骤也可以与前面的步骤一起完成)

如果不同值的数量大于K，则所有组都必须是非空的。如果不是这样，您可以轻松地拆分包含相同值的重复项的组，使所有组都不为空。

复杂度(如果已经排序)：O(n*k) (至多)，如果K是常数，则复杂度为O(n)。如果不是，只需改进对最佳K-1个段的搜索，以获得最多O(n log(n))

如上所述，额外的内存复杂度很容易达到O(K)

Answer 3

因此，在这个问题中，我们希望最小化组的范围。

因此，假设我们有数组A = {1,3,5,7,5,2}

每个阵列中的最大范围为max[a]-min[a]，最小范围为0

我们可以使用二进制搜索的变体来寻找最小范围，这个答案的约束是组必须包含概念数。

对于二进制搜索，我们需要选择由数组的最小和最大范围给出的边界。

这段psuedo/java代码看起来像这样。

main(){
  int upper = max(A)-min(A); 
  int lower = 0;  


  while (true) {
    int mid =  upper-lower;  
    int blocks = calculateBlockCount(A, mid); 
    if (blocks < K) {
      upper = mid - 1;
    } 
    else if (blocks > K) {
      lower = mid + 1;
    } 
    else {
      return upper;
      break;
    }
  }
 }

    private static int calculateBlockCount(int[] array, int range) {
      int count = 0;
      int[] dumie_array;
      int dumie_array[].add[array[0]];

      for (int i = 0; i < array.length; i++) {
        int dumie_array[].add[array[i]]
         if (Func_range(dumie_array) > range) {
           count++;
           dumie_array = array[i];
         } 
         else {
           dumie_array.add(array[i]);
         }
      }
      return count;
    }

    private static int Func_range(int[] input) {
       int range = 0;
       range= max(input)-min(input)
       return sum;
     }

希望仍然有帮助

我认为大部分功能都可以在C++中使用，只有java没有提供add功能。(我不想通过创建数组列表来编写这么多内容。)但我认为这个计划的想法应该是明确的。

这都是基于这篇文章的Need explanation for algorithm searching minimal large sum。这是一个非常相似的问题。

干杯，Gijs