有一个包含 N 个整数的集合 S,每个整数的值 1<=X<=10^6。问题是将集合 S 划分为 k 个分区。分区的值是其中存在的元素的总和。分区是以这样的方式完成的,集合 S 的总值在 k 个分区中公平分布。还需要定义公平的数学含义(例如,目标可以是最小化分区值与集合 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|AB| 对于任何 A、B