算法:使用空格将字符串分成 N 个部分，使所有部分的长度几乎相同

Question

我正在寻找一种算法，将一个字符串拆分成一定数量的部分。这些部分应包含完整的单词(因此使用空格分隔字符串)并且各部分的长度应几乎相同，或者包含尽可能长的部分。

我知道编写一个可以做我想做的事情的函数并不难，但我想知道是否有一个经过充分验证的快速算法来实现这个目的？

编辑: 为了澄清我的问题，我将向您描述我要解决的问题。

我生成具有固定宽度的图像。在这些图像中，我在 PHP 中使用 GD 和 Freetype 写入用户名。因为我有一个固定的宽度，所以我想把名字分成 2 或 3 行，如果它们不适合一行的话。

为了尽可能多地填充空间，我想以每行包含尽可能多的单词的方式拆分名称。我的意思是，在一行中应该有尽可能多的单词，以使每行的长度接近整个文本 block 的平均行长度。因此，如果有一个长词和两个短词，如果使所有行的长度大致相等，则两个短词应该站在一行上。

(然后我使用 1、2 或 3 行计算文本 block 宽度，如果它适合我​​的图像，我会渲染它。如果有 3 行并且它不适合我减小字体大小直到一切正常.)

例子: 这是一个长文本 应该显示类似的东西:

This is a
long text

或:

This is
a long
text

但不是:

This
is a long
text

也不是:

This is a long
text

希望我能更清楚地解释我在寻找什么。

Answer 1

如果你在谈论换行，看看Dynamic Line Breaking , 这给出了 Dynamic Programming将单词分成行的解决方案。