python - 将 int 值平均分配到两个列表中，这两个列表的总和必须几乎相等

Question

我想将一个列表的 int 值平均分配到两个列表中，这两个列表的总和必须几乎相等。如果不完全相等，则返回差值。

li=[5,8,13,27,14]
first_list=[27,8)
second_list=[14,13,5]
return sum(first_list)-sum(second_list) #3

Answer 1

这是 Partition Problem 的优化问题，即 NP-Complete .

没有已知的多项式解，但有一些启发式和近似算法。

此外，对于相对较小的整数，有一个可能可行的动态规划解决方案，或者如果输入(元素数量)相对较小 - 指数 brute force可以使用解决方案。