如何将一组数字划分为两个元素数量和最接近的元素数量的子集

Question

给定一组n个数字，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!

编辑：如果我们希望这些集合同等规模，那么这可能会成为一个问题。使用Compinatorics将需要很长时间，但是我没有其他选择。再说一次，我的知识有限。所以来了：
给定22组，找到一组11，总计为22的一半，或者尽可能接近。如果尽可能接近，请查看切换元素是否会产生更好的结果。但这与组合学一样效率低下。

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

对不起，我不能提供更多的帮助。