将整数数组划分为 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

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

所以假设我们有数组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;
     }

希望stil能帮上忙

我认为这大部分在java中是可行的，只有C语言中的add功能是不存在的。(不想通过创建数组列表来写这么多。)但是我觉得节目的思路应该是清晰的。< br >这都是基于这个帖子需要算法搜索最小大和的解释。这是一个非常相似的问题。

干杯，吉斯

Answer 2

通过动态编程，你想出了k = 2的解决方案。现在想想怎么把它推广到k = 3。

假设f2（n）返回k=2和前n个数字的最优解，f3（n）=f2（n-m）err（n-m， n）。这是扩展它的一种方法。

Answer 3

1. 对数组排序
2. 设a_m为数组的m^th元素；然后，设a_m=a_{m∀米∈ [1；N）。减法循环必须向后运行，以避免改变am–1.a0≡ 0。}
3. 对结果数组进行排序，保持元素的初始索引与元素本身的排序顺序相同
4. 以最后的K–1索引为例：这些索引加上0，是搜索组的第一个元素的索引