在平衡重量的块中拆分列表

Question

我需要一个算法将一个值列表拆分成这样的块,每个块中的值总和是(近似)等于(它假设背包问题的一些变化)

所以,例如[1,2,1,4,10,3,8] => [[8,2],[10],[1,3,1,4]]

相同长度的块是首选,但它不是约束.

Python是首选语言,但也欢迎其他语言

编辑:定义了块数

Answer 1

贪心:
1.订购下降的可用物品.
2.创建N个空组
3.开始将项目一次添加到其中总和最小的组中.

我认为在大多数现实生活中,这应该足够了.

O(NlogN).排序是瓶颈,这个解决方案将确保两组之间的差异最多为{S} (3认同)
在一个不同的线程中,类似于这个,我已经证明了**最大{S} -min {S}是这个算法的最大差异.看看:http://stackoverflow.com/questions/6455703/fair-partitioning-of-set-s-into-k-partitions/6486812#6486812 (2认同)