偶数整数集

Even sets of integers

本文关键字：整数      更新时间：2023-09-26

给定一个整数数组heights，我想将它们拆分为n集合，每个集合的totalHeight（集合中值的总和）相等，或者尽可能接近。集合中的每个值之间必须有一个固定的距离gap。集合不必具有相同数量的值。

例如，假设：

  • heights[0, 1, 2, 3, 4, 5] = [120, 78, 110, 95, 125, 95]

  • n=3

  • gaps=10

可能的安排是：

  • a[0, 1], b[2, 3], c[4, 5]给出的totalHeight值

    • a = heights[0] + gap + heights[1] = 120 + 10 + 78 = 208

    • b = heights[2] + gap + heights[3] = 110 + 10 + 95 = 215

    • c = heights[4] + gap + heights[5] = 125 + 10 + 95 = 230

  • a[0], b[1, 2, 3], c[4, 5]给出的totalHeight值

    • a = heights[0] = 120

    • b = heights[1] + gap + heights[2] + gap + heights[3] = 303

    • c = heights[4] + gap + heights[5] = 125 + 10 + 95 = 230

等等。我想找到一个组合，它能给出大小最均匀的集合。因此，在这个例子中，第一个组合更好，因为它给出的总体误差为：

max - min = 230 - 208 = 22

而第二种组合给出了183的误差。我试图用JavaScript来做这件事，但我只是在寻找某种算法的轮廓。伪代码或其他什么都很棒。如有任何帮助，我们将不胜感激。

我糟糕的尝试：显然，解决这个问题的一种方法是尝试所有可能的组合。一旦heights变大，那就太可怕了。

我尝试的另一种方法是获得集合的预期平均高度，计算为height/n中值的总和。然后我试着通过尽可能接近这个平均值来分别填满每一盘。它在某些情况下可以正常工作，但速度太慢了。

注意：如果有帮助的话，我很乐意拥有对称集。例如，对于集合（a，bc），a=b。或者对于五个集合（a、b、c、d、e），a=b和c=d。我认为这将更难实现，但我可能错了。

编辑：对于任何可能感兴趣的人，我能想到的最好的算法是以下算法：

  • 按降序对heights进行排序
  • 创建n集合
  • 将heights中的第一个n值放入每组的第一个插槽中。即将CCD_ 25的最大值放在每组的开始处。在添加值时从heights中删除这些值
  • 而heights.count>0
    • 在每个n集合中查找最小的totalHeight（包括gap）
    • 将heights中的下一个值添加到此集合（并从heights中删除该值）
  • 最后有一些小算法，如果totalHeight越来越接近平均值，每个集合可以与其他集合进行x次交换。我保持x的小规模，因为这个过程可能会永远持续下去

这并不可怕，但显然并不完美。

看起来它是NP完全的，并且可以简化为子集和问题，或者更准确地说，可以简化为分区问题。

您的第二种方法-找到平均值（height/n），然后尝试用尽可能接近的平均值填充集合似乎是一种很好的实用方法。你说这太慢了。。。下面的实现是O（n*m-logn），其中m是集合中允许的元素的最大数量。如果m可以非常大，那么这可能非常慢，但是如果m被限制在某个范围内，那么它可以接近O（n-logn），这大约和你要得到的一样快。

   Find the mean height of all values. h_mean = Sum(h) / n; O(n).
   Sort all heights. O(n log n).
   Examine the highest and lowest height. 
   Add the value which is furthest from the mean to a new set.
   Remove this value from the sorted heights.
   Repeat for max_number allowed in set = 1 .. m (m < n / 2)
   {
      Repeat:
      {
         If the set mean is higher than the mean.
            Add the lowest value from the sorted heights.
            Remove this value from the sorted heights.
         If the set mean is lower than the mean
            Add the highest value from the sorted heights.
            Remove this value from the sorted heights.
         Recalculate the set mean (taking account of the gap).
         If the new set mean is further from the h_mean than the last OR
            If the set has too many elements
           break
      }
      Until all numbers are used.
      Keep track of the standard deviations for this assignment. 
      If this assignment is the best so far, keep it.
   }

这不会给出一个可证明的最佳解决方案，但它很简单，而且有很多优点…

注意，在这个算法中，所有集合都有相同数量的元素m。你可以对m的不同值重复迭代，比如2、3、4（注意m应该是N的因子）。每组的总高度约为m*mean_height。

你可能会问，如果N是素数呢

然后很明显，一套价值会低于总价值。

这是否意味着这个算法毫无用处

一点也不。它很简单，应该会产生一个很好的解决方案的第一次尝试。您可能希望首先使用此算法，然后使用优化技术（例如选择性交换要设置的高度）来细化第一个结果。

相关文章：