存在一个集合 S，其中包含 N 个整数，每个整数的值为 1fair还需要定义（例如，目标可能是最小化分区值与集合 S 平均值的标准偏差（即 sum(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
=================================================== =================================
基于其他相关的 SO 问题，有两个合理的函数来评估分布：
a) 最小化具有最大值的分区的值。
再想一想，这不是一个好的衡量标准。考虑将集合 {100, 40, 40} 划分为三个子集。该指标不区分以下两种分布，即使其中一种明显优于另一种。
分布 1：{100}、{40}、{40} 分布 2：{100}、{40、40}、{}
b) 最小化给定分区中任意两个值的差值的最大值，即最小化 max|A-B|对于任意A、B
我认为一个好的衡量标准是：
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！
缺点：如果没有完美的解决方案，最好的结果不会是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)
该解决方案将产生 f（上面定义的指标），使得f(sol) <= (k-1)*max{S}（这里是这个界限的证明）：
claim：对于每个子集 s，MAX- sum(s) <= max{S}
proof- 通过归纳法：在每一步中，临时解决方案的断言都是正确的。
在每个步骤中，在迭代开始时（相加之前）让 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}， 按照承诺。
EDIT :
I had some spare time, so I programmed both heuristics suggested by me and by @Akhil, and both metrics, first of all, both results are conclusive (according to Wilcoxon's pair-t test), but which is better is defined by which metric you choose, surprisingly, the algorithm which tried to minimize f() (@Akhil`s) scored lower for this same f, but higher for the second metric.
