公平地将集合S划分为k个分区

Question

存在包含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

Answer 1

我认为一个好的指标是:

let the result set be s1,s2,...,sk
let MAX be max{sum(si) for each i}
f({s1,...,sk}) = Sigma(MAX-sum(si)) for each i)

好处:完美的分配总会产生0!
缺点:如果没有perferct解决方案,最好的结果将不会产生0.

这个问题的贪心启发式将是:

sorted<-sort(S) (let's say sorted[0] is the highest)
s1=s2=...=sk= {}
for each x in sorted:
   s <- find_min() (*)
   s.add(x)

其中find_min()产生s,使得每个si的sum(s)<= sum(si).

这个解决方案将产生f(上面定义的度量),这样f(sol) <= (k-1)*max{S}(从这里它是这个边界的证明):

声明:对于每个子集s,通过归纳MAX- sum(s) <= max{S}
证明:在每个步骤,声明对于临时解决方案都是正确的.
在每一步中,让MAX在迭代开始时(加法前)为max {sum(si)}!

base: the set of subsets at start is {},{},.. MAX=sum(si)=0 for each si. 
step: assume the assumption is true for iteration i, we'll show it is also true for iteration i+1:
let s be the set that x was added to, then MAX-sum(s) <= max{S} (induction assumption).
if sum(s) + x <= MAX: we are done, MAX was not changed.
else: we sorted the elements at start, so x <= max{S}, and thus if s was chosen
   (sum(si) >= sum(s) for each si) and sum(s) + x > MAX then: for each si, sum(si) + x >=
   sum(s) + x, so sum(s)+x - sum(si) <= x <= max{S}. since sum(s)+x will be the MAX next 
   iteration, we are done.

因为对于每一组MAX-sum(si) <= max{S}(显然,对于最大集合MAX-sum(si)=0),总体而言 Sigma(MAX-sum(si)) <= (k-1)*max{S},如所承诺的那样.

编辑:
我有一些业余时间,所以我编写了由我和@Akhil建议的两种启发式方法,并且两个指标,首先,两个结果都是结论性的(根据Wilcoxon的对t测试),但哪个更好是根据你选择的指标来定义,令人惊讶的是,试图最小化f()(@ Akhil`s)的算法对于同样的f得分较低,但对于第二个指标得分较高.