存在包含N个整数的集合S,每个整数具有值1 <= X <= 10 ^ 6.问题是将集合S划分为k个分区.分区的值是其中存在的元素的总和.分区将以这样的方式完成,集合S的总值在k个分区之间公平分配.公平的数学意义也需要定义(例如,目标可以是最小化分区值与集合S的平均值的标准偏差(即,和(S)/ k))
例如,S = {10,15,12,13,30,5},k = 3
一个好的分区是{30},{10,15},{12,13,5}
错误的分区是{30,5},{10,15},{12,13}
第一个问题是在数学上表达一个分区的条件要好于另一个分区.第二个问题是如何解决问题.问题是NP-Hard.有任何启发式吗？
在我试图解决N <=(k*logX)^ 2和K从2到7变化的问题.
================================================== ================================
根据其他相关的SO问题,评估分布有两个合理的功能:
a)使用最大值最小化分区的值.
再想一想,这不是一个好的指标.考虑一组{100,40,40}被分成三个子集.该度量标准不区分以下两个分布,即使一个明显优于另一个.
分配1:{100},{40},{40}和分配2:{100},{40,40},{}
b)最小化给定分区中任何两个值的差异的最大值,即最小化max | AB | 任何A,B