如何将一组分为两组，使平均值的差异最小？

Question

据我了解，这与分区问题有关。

但是我想问一个稍微不同的问题，我不在乎总和，而是在乎平均值。在这种情况下，它需要同时优化 2 个约束（总和和项目数）。这似乎是一个更难的问题，我在网上看不到任何解决方案。

是否有针对此变体的任何解决方案？或者它与分区问题有什么关系？

---

例子：

input X = [1,1,1,1,1,6]
output based on sum: A = [1,1,1,1,1], B=[6]
output based on average: A = [1], B=[1,1,1,1,6]

Answer 1

设sizeS_i的子集之和vi

设S为 的总和v，n长度v

最小化的错误是

err_i = |avg(S_i) - avg(S-S_i)|
err_i = |S_i/i - (S-S_i)/(n-i)|
err_i = |(nS_i - iS)/(i(n-i))|

下面的算法的作用是：

for all tuple sizes (1,...,n/2) as i
  - for all tuples of size i-1 as t_{i-1}
  - generate all possible tuple of size i from t_{i-1} by adjoining one elem from v
  - track best tuple in regard of err_i

我发现的唯一削减是：

对于两个大小i具有相同总和的元组，保留最后一个元素索引最小的元组

例如给定元组A，B（其中X一些元素来自v）

A: [X,....,X....]
B: [.,X,.....,X..]

保留A，因为它最右边的元素具有最小索引

（想法是，在规模 3 时，A将提供相同的候选人以及B更多的候选人）

err_i = |avg(S_i) - avg(S-S_i)|
err_i = |S_i/i - (S-S_i)/(n-i)|
err_i = |(nS_i - iS)/(i(n-i))|