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

Question

有一个包含 N 个整数的集合 S，每个整数的值为 1<=X<=10^6。问题是将集合 S 划分为 k 个分区。分区的值是其中存在的元素的总和。分区将以集合 S 的总值在 k 个分区之间公平分配的方式进行。 fair 的数学含义也需要定义(例如，目标可能是最小化分区值与集合 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 <= (k*logX)^2 并且 K 在 2 到 7 之间变化。

============================================= ===================================

根据其他相关的 SO 问题，有两个合理的函数来评估分布:

a) 最小化具有最大值的分区的值。

再想想，这不是一个好的指标。考虑将一组 {100, 40, 40} 划分为三个子集。该指标不区分以下两种分布，即使其中一种明显优于另一种。

分布 1:{100}、{40}、{40} 和分布 2:{100}、{40、40}、{}

b) 最小化给定分区中任意两个值之差的最大值，即最小化 max|A-B|对于任何 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!
缺点:如果没有完美的解决方案，最好的结果不会产生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} (从这里开始，它是这个界限的证明):

声明:对于每个子集，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} , 正如所 promise 的那样。

编辑:
我有一些空闲时间，所以我编写了我和@Akhil 建议的启发式方法和两个指标，首先，两个结果都是决定性的(根据 Wilcoxon 的 pair-t 测试)，但是哪个更好是由您选择的指标定义的，令人惊讶的是，试图最小化 f() (@Akhil`s) 的算法对于相同的 f 得分较低，但对于第二个指标得分较高。