我将在PHP中制作一个自动换行算法。我想将小块文本（短短语）拆分为n行，最多m个字符（未给出n，因此将根据需要提供尽可能多的行）。特殊之处在于，行长度（以字符为单位）必须尽可能平衡。
输入文本示例：
How to do things
错误的输出（这是正常的自动换行行为），m=6：
How to
do
things
所需输出，始终 m=6：
How
to do
things
有没有人对如何实现此功能有建议或指导？基本上，我正在搜索两到三行（尽可能）等长行上的印刷短短语。
更新：似乎我正在搜索一个最小粗糙的自动换行算法。但是我找不到任何真正的编程语言的实现（任何人，然后我可以用PHP转换它）。
更新2：我为此开始了赏金。有没有可能在任何过程语言中都不存在最小粗糙度算法的任何公共实现？我需要以一种可以转化为程序指令的方式编写一些东西。我现在能找到的只是一个（通用）方程的反弹，但是需要一个最佳的搜索过程。我也会感谢一个只能近似于最佳搜索算法的实现。
我已经在Alex的相同行上实现了，编码了维基百科算法，但直接在PHP中（对我来说是一个有趣的练习）。了解如何使用最优成本函数 f（j），即“递归”部分，并不容易。感谢 Alex 的注释良好的代码。
/**
* minimumRaggedness
*
* @param string $input paragraph. Each word separed by 1 space.
* @param int $LineWidth the max chars per line.
* @param string $lineBreak wrapped lines separator.
*
* @return string $output the paragraph wrapped.
*/
function minimumRaggedness($input, $LineWidth, $lineBreak = "\n")
{
$words = explode(" ", $input);
$wsnum = count($words);
$wslen = array_map("strlen", $words);
$inf = 1000000; //PHP_INT_MAX;
// keep Costs
$C = array();
for ($i = 0; $i < $wsnum; ++$i)
{
$C[] = array();
for ($j = $i; $j < $wsnum; ++$j)
{
$l = 0;
for ($k = $i; $k <= $j; ++$k)
$l += $wslen[$k];
$c = $LineWidth - ($j - $i) - $l;
if ($c < 0)
$c = $inf;
else
$c = $c * $c;
$C[$i][$j] = $c;
}
}
// apply recurrence
$F = array();
$W = array();
for ($j = 0; $j < $wsnum; ++$j)
{
$F[$j] = $C[0][$j];
$W[$j] = 0;
if ($F[$j] == $inf)
{
for ($k = 0; $k < $j; ++$k)
{
$t = $F[$k] + $C[$k + 1][$j];
if ($t < $F[$j])
{
$F[$j] = $t;
$W[$j] = $k + 1;
}
}
}
}
// rebuild wrapped paragraph
$output = "";
if ($F[$wsnum - 1] < $inf)
{
$S = array();
$j = $wsnum - 1;
for ( ; ; )
{
$S[] = $j;
$S[] = $W[$j];
if ($W[$j] == 0)
break;
$j = $W[$j] - 1;
}
$pS = count($S) - 1;
do
{
$i = $S[$pS--];
$j = $S[$pS--];
for ($k = $i; $k < $j; $k++)
$output .= $words[$k] . " ";
$output .= $words[$k] . $lineBreak;
}
while ($j < $wsnum - 1);
}
else
$output = $input;
return $output;
}
?>
快速而肮脏，在c ++中
#include <sstream>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <memory.h>
using namespace std;
int cac[1000][1000];
string res[1000][1000];
vector<string> words;
int M;
int go(int a, int b){
if(cac[a][b]>= 0) return cac[a][b];
if(a == b) return 0;
int csum = -1;
for(int i=a; i<b; ++i){
csum += words[i].size() + 1;
}
if(csum <= M || a == b-1){
string sep = "";
for(int i=a; i<b; ++i){
res[a][b].append(sep);
res[a][b].append(words[i]);
sep = " ";
}
return cac[a][b] = (M-csum)*(M-csum);
}
int ret = 1000000000;
int best_sp = -1;
for(int sp=a+1; sp<b; ++sp){
int cur = go(a, sp) + go(sp,b);
if(cur <= ret){
ret = cur;
best_sp = sp;
}
}
res[a][b] = res[a][best_sp] + "\n" + res[best_sp][b];
return cac[a][b] = ret;
}
int main(int argc, char ** argv){
memset(cac, -1, sizeof(cac));
M = atoi(argv[1]);
string word;
while(cin >> word) words.push_back(word);
go(0, words.size());
cout << res[0][words.size()] << endl;
}
测试：
$ echo "The quick brown fox jumps over a lazy dog" |./a.out 10
The quick
brown fox
jumps over
a lazy dog
编辑：刚刚查看了维基百科页面，以尽量减少锯齿状换行。将算法更改为给定算法（带平方惩罚）
