给定一个整数数组heights
我想把它们分成n
个集合,每个集合都有相等的totalHeight
(集合中的值之和),或者尽可能接近集合中的每个值之间必须有固定的距离gap
集合不必具有相同数量的值。
例如,假设:heights[0, 1, 2, 3, 4, 5] = [120, 78, 110, 95, 125, 95]
n
=3gaps
=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
等等。我想找到组合,使大小最均匀的集。因此在本例中,第一个组合更好,因为它给出的总体误差为:
max - min = 230 - 208 = 22
而第二个组合的误差是183。我试图用javascript来实现这一点,但我只是在寻找某种算法的大纲。伪代码之类的。任何帮助都将不胜感激。
我拙劣的尝试:很明显,解决这个问题的方法之一就是尝试所有可能的组合一旦
b = heights[1] + gap + heights[2] + gap + heights[3] = 303
变大,那就太可怕了。我尝试的另一种方法是获得集合的期望平均高度,计算为
c = heights[4] + gap + heights[5] = 125 + 10 + 95 = 230
/heights
中的值之和然后我试图通过尽可能接近这个平均值来单独填充每一组。它在某些情况下工作正常,但速度太慢。注意:如果有帮助的话,我很乐意使用对称集例如,对于集合(a,b c),a=b,或者对于五个集合(a,b,c,d,e),a=b,c=d,我认为这更难实现,但我可能是错的。
编辑:对于任何感兴趣的人,我能想到的最好的算法是:
按降序排序。
创建
height
集合。将
n
中的第一个heights
值放入每组的第一个槽中。也就是说,将n
最大值放在每组的开头。在添加值时将其从n
中移除。当
heights
>0找出每个
n
集合中最小的heights
(包括heights.count
)。将
totalHeight
中的下一个值添加到此集合(并从gap
中移除该值)。然后在最后有一些小算法,如果
n
接近平均值,那么每个集合可以与其他集合进行heights
数量的交换我一直保持小规模,因为这个过程可能会一直持续下去。这并不可怕,但显然并不完美。
最佳答案
它似乎是NP完全的,并且可以还原为Subset sum problem或更精确地还原为Partition problem。