时间戳

首页 > 解决方案 > 如何将一组分成两组以使平均值的差异最小？

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

问题描述

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

但我想问一个稍微不同的问题，我不关心总和，而是关心平均值。在这种情况下，它需要同时优化 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]

标签： algorithmcomplexity-theorytheorynp-complete

解决方案

在某些输入上，针对通常的分区问题对动态程序进行修改会加快速度。我们必须通过计数和总和对每个部分解决方案进行分类，而不仅仅是总和，这会稍微减慢速度。下面的 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]))

推荐阅读