algorithm - 如何将一组数字分成两个子集，这些子集的元素数量相等，并且总和尽可能接近？

Question

给定一组 n 个数字，其中 n 为偶数，我如何得到两个子集，每个子​​集包含 n/2 个数字，并且每个子集中的数字之和尽可能接近？

例子: Set={1.6, 4.0, 0.7, 2.9, 5.0, 3.1, 5.0, 1.0, 0.6, 5.0} 总和为 28.9

子集可以是: {5.0, 5.0, 2.9, 1.0, 0.6} 和 14.5 和 {5.0, 4.0, 3.1, 1.6, 0.7} 总和为 14.4

我需要一个算法，伪代码就可以了。

谢谢!

Answer 1

我的看法是:有两个列表，空的。 a=[ ], b=[ ] 对于 x(数字列表)中的每个元素，将其附加到最需要它的元素，即其总和小于另一个的元素。

x=[1.6, 4.0, 0.7, 2.9, 5.0, 3.1, 5.0, 1.0, 0.6, 5.0]
x.sort()
x.reverse()
print(x)
#[5.0, 5.0, 5.0, 4.0, 3.1, 2.9, 1.6, 1.0, 0.7, 0.6]
b=[];c=[]
for i in a:
    if sum(b) <= sum(c):
        b.append(i)
    else:
        c.append(i)
print(sum(b))
print(sum(c))

#Hope this helps!

编辑: 如果我们希望集合的大小相同，那么这可能会成为一个问题。使用组合数学会花费很长时间，但我看不到其他选择。话又说回来，我的知识有限。所以这里是:
给定一组 22，找到一组 11，其总和为 22 的一半，或尽可能接近。如果它尽可能接近，看看切换元件是否会产生更好的结果。但这和组合数学一样低效。

这是一个非常困难的问题。甚至维基百科也承认这一点。 :-D :-(

抱歉，我无法提供更多帮助。