算法：字符串分割成N个部分使用空格让所有部件都几乎相同的长度 [英] Algorithm: Split a string into N parts using whitespaces so all parts have nearly the same length

问题描述

我要寻找一个算法，将一个字符串分割成若干部分。这些部分应包含完整的单词（以便空格被用于分割字符串）和部分应几乎相同的长度，或包含尽可能最长的部分。

I am looking for a algorithm that takes a string and splits it into a certain number of parts. These parts shall contain complete words (so whitespaces are used to split the string) and the parts shall be of nearly the same length, or contain the longest possible parts.

我知道这是不是很难codeA功能，可以做什么，我想，但我不知道是否有一个良好的成熟和快速算法的目的是什么？

I know it is not that hard to code a function that can do what I want but I wonder whether there is a well-proven and fast algorithm for that purpose?

编辑： 为了澄清我的问题，我将描述你的问题，我试图解决的问题。

edit: To clarify my question I'll describe you the problem I am trying to solve.

我产生具有固定宽度的图像。到这些图片我写在PHP使用GD和FreeType的用户名。因为我有一个固定的宽度我想的名字拆分成2个或3行，如果他们不适合的。

I generate images with a fixed width. Into these images I write user names using GD and Freetype in PHP. Since I have a fixed width I want to split the names into 2 or 3 lines if they don't fit into one.

为了填补尽可能多的空间可能欲的方式，每行包含尽可能多的话尽量分割的名字。有了这个，我的意思是，在一个行应该是为了保持各行的长度接近整个文本块的平均线路长度尽可能多的单词作为neccessary。因此，如果有一个长单词和两个短词的两个短话应该站在一条线，如果它使约等于长都行。

In order to fill as much space as possible I want to split the names in a way that each line contains as much words as possible. With this I mean that in one line should be as much words as neccessary in order to keep each line's length near to an average line length of the whole text block. So if there are one long word and two short words the two short words should stand on one line if it makes all lines about equal long.

（然后我计算文本块宽度采用1，2或3行，如果它适合我​​的形象我呈现它。只是，如果有3条线，它不适合我减小字体大小，直到一切都很好。）

(Then I compute the text block width using 1, 2 or 3 lines and if it fits into my image I render it. Just if there are 3 lines and it won't fit I decrease the font size until everything is fine.)

例： 这是一个长的文本 要显示这样的事情：

Example: This is a long text should be display something like that:

This is a
long text

或

This is
a long
text

而不是

This
is a long
text

和也没有：

This is a long
text

希望我能更清楚地解释我所期待的。

Hope I could explain clearer what I am looking for.

推荐答案

如果你在谈论断行，看一看的动态断行，这给动态规划解决方案分词成线。

If you're talking about line-breaking, take a look at Dynamic Line Breaking, which gives a Dynamic Programming solution to divide words into lines.

这篇关于算法：字符串分割成N个部分使用空格让所有部件都几乎相同的长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！