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。

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

此外，对于相对较小的整数，有一个可能可行的动态编程解决方案，或者如果输入（元素数量）相对较小 - 可以使用指数蛮力解决方案。