三栏新闻源（如 google+）的最小长度？

Question

我正在实施一个新闻源程序，类似于Google+。

该问题可以抽象如下：

给定一个块列表（高度不同但宽度与列的宽度相同），我们如何将文本排列在三列中以使页面的总长度最小？

请注意，块不能重叠，并且块不遵循任何顺序。

Answer 1

这个问题称为多路数字分区。

数字划分问题是将给定的整数集合划分为子集集合，使得每个子集中的数字之和尽可能接近相等。虽然存在一种非常有效的算法来实现最佳双向分区，但它对于多路分区来说并不那么有效。

虽然它是 NP 难的，但您可能会发现链接文章中的启发式方法和算法对于实际目的来说足够有效。