arrays - 将数组放入等长的 'n' 组中

Question

创建 “n” 组数组并使所有数组的总长度尽可能接近相等的最佳方法是什么？

寻找可能输出如下内容的算法:

Data Set (L=array length): [L:3],[L:1],[L:7],[L:4],[L:2] 

n=2: 
[L:3],[L:4],[L:1] = 8 total
[L:7],[L:2] = 9 total

n=3
[L:7]
[L:4],[L:1]
[L:3],[L:2]

创建上面的示例后，我意识到“接近等于”这个短语可能有点含糊不清，具体取决于您如何定义“等于”。

我有一个 n 列的布局。每个数组都是项目的原子组，必须一起显示。我目前为列提供了相同数量的数组，我的结果通常看起来像这样:

7 total arrays: 3 columns

_ _ _
. . .
_ . .
. . .
. . .
  . _
  . .
  .
  _
  .
  .

我确定有一个术语可以用来做我想做的事，并在 google 上链接了很多很棒的资源，但我不确定它是什么。

Answer 1

您基本上面临着 Bin-packing 的变体和 Subset Sum问题，这是NP-Hard .

这是 partition problem 的缩减(子集总和的特例，也是 NP-Complete)你的问题:

分区问题:
给定一个输入集 S，找到两个不同子集 S1,S1 的划分，使得 S1 [union] S2 = S和 S1 [intersection] S2 = {}，以及 sum(S1)=sum(S2)。

现在，给定分区实例 S={s1,...,s_n} 创建数据集 [L:s1],...[L:s_n] 和 n=2。

现在，很容易看出问题的解决方案就是分区问题的解决方案，反之亦然 - 因此问题的解决方案有效地解决了分区问题。
由于分区问题是 NP-Hard - 这个问题也是如此 - 因此没有已知的有效(多项式)解决方案，而且大多数人认为不存在。

关于与 binpacking 的关系 - 请注意，您的问题基本上是 binpacking with size(bin) = sum(lengths)/n

---

注意:在这里，我假设您只处理长度，如果您处理的是实际元素，则这种减少不是输入大小的多项式，证明落空。