将数字公平分配为两组的算法

Question

给定一组n个数(1 <= n <= 100),其中每个数是1到450之间的整数,我们需要将这些数字集分配到两个集A和B中,以便以下两种情况成立:

1. 每组中的总数最多相差1.
2. A中所有数字的总和尽可能与B中所有数字的总和几乎相等,即分布应该是公平的.

有人可以建议一个有效的算法来解决上述问题吗？

谢谢.

Answer 1

由于数字很小,因此不是NP完全的.

要解决它,您可以使用动态编程:

制作一个布尔的三维表,其中t [s,n,i]为真表示可以使用索引i下面的n个元素的子集来达到和s.要计算t [s,n,i]的值,请检查t [s,n,i-1]和t [s - a [i],n-1,i-1].然后在第二个索引n/2处查看表格以找到最佳解决方案.

编辑:您实际上不需要一次完整的表.您可以为每个索引i创建一个二维表t_i [s,n],并从表中为i-1计算i的表,因此您只需要这些二维表中的两个,这样可以节省大量内存.(感谢Martin Hock.)