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

Question

据我了解，它与 partition problem 有关.
但是我想问一个稍微不同的问题，我不在乎总和，而是在乎平均值。在这种情况下，它需要同时优化 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

在某些输入上，针对通常的分区问题修改动态程序将提供加速。我们必须通过它的计数和总和来对每个部分解决方案进行分类，而不仅仅是总和，这会减慢速度。下面的 Python 3(请注意，字典的使用隐式折叠了功能相同的部分解决方案):

def children(ab, x):
    a, b = ab
    yield a + [x], b
    yield a, b + [x]


def proper(ab):
    a, b = ab
    return a and b


def avg(lst):
    return sum(lst) / len(lst)


def abs_diff_avg(ab):
    a, b = ab
    return abs(avg(a) - avg(b))


def min_abs_diff_avg(lst):
    solutions = {(0, 0): ([], [])}
    for x in lst:
        solutions = {
            (sum(a), len(a)): (a, b)
            for ab in solutions.values()
            for (a, b) in children(ab, x)
        }
    return min(filter(proper, solutions.values()), key=abs_diff_avg)


print(min_abs_diff_avg([1, 1, 1, 1, 1, 6]))