我有一个任意长度(比如 30-45)的字符串数组，我想重新格式化以适应一定数量的页面(比如 15)。
我想尽可能均匀地在页面之间分配字符串，以便所有页面尽可能接近彼此的总字符长度，而不管每页的字符串总数。我还需要保留字符串顺序(因此我无法重新排列数组)。
您是否推荐任何特定的算法来解决这个问题？或者你会采取模糊的方法？谢谢!
最佳答案
一种方法是使用 http://en.wikipedia.org/wiki/TeX 格式化您的文本- 它的换行算法是最优的，并且基于动态规划。不幸的是，它的分页算法不是最佳的，尽管我希望它和您很容易发现的一样好。
如果您可以将每个页面建模为具有固定数量字符的空间，那么确实存在动态规划解决方案。您需要找到一种方法将 14 个分页符放在最佳位置。从左到右工作，在每个可能的分页符位置，计算出在前一个文本中插入 k-1 个分页符的最佳可能方式的总不均匀性惩罚，以第 k 个分页符的可能位置结束.对 k = 1..14 执行此操作。您可以使用您之前计算的左侧信息来计算新地点的总罚款。
当您读到文本末尾时，您可以使用目前为止的计算来计算在左侧插入 14 个分页符的最佳方式的不均匀度惩罚。如果您将计算记录保存在左侧，您还可以计算出 14 个分页符中最右侧的位置。你可以回到那里找出第 13 个分页符的位置，依此类推，直到找到所有分页符的位置。
关于以最平衡的方式分解字符串数组的算法建议，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7637855/