最小化段落中的总空 space - 算法
Minimizing total empty space in a paragraph - algorithm
对于一个应用程序，我想找到一种方法来通过惩罚来最小化段落每一行末尾的总空白 space。我有一组单词 W = [w1, w2, w3, ..., wn] 构成了我希望该段落包含的文本，每个单词 wi 我都有相应的长度 li。我还知道一行可以容纳的最大字符数，包括 spaces：m。我不会说话。
在这种情况下，我定义了一个关系来描述以单词 i 开头并以单词 j 结尾的行的空 space 的成本由下式给出c(i, j) = (m - (j - i) - sum_{k=i}^{k = j}lk)^3。所以c(i, j)必须是正数，否则我需要断行如果j = n，我不惩罚最后一行的空space：c(i, n) = 0.
有了这个参数，我找到了一种算法，可以在传递到下一行之前最小化每行的成本并计算总成本。然而，最小化每条线的成本并不一定意味着总成本也最小化。
我能想到的任何可以最小化总成本的过程都需要对每行中的单词数进行大量排列，因此无法实现。任何计算最小成本的可行算法的想法？
设G为一个图，其中每个顶点V_x_y表示由组成的部分段落y 行，总共使用 x 个单词。如果 z > x 和单词 w_(x+1) 到 w_z 适合在一条线上。每条这样的边都有成本 c(x+1,z)，即它代表的附加线的成本。
现在，您的问题是找到从 V_0_0 到顶点 V_n_y 的最小成本路径消耗所有单词。
您可以使用 Dijkstra 算法在 O(n^2 log n) 时间或更短的时间内找到此路径，或者如果您制定了一个像样的算法，则 A* 可以更快地找到它可接受的启发式。
对于一个应用程序，我想找到一种方法来通过惩罚来最小化段落每一行末尾的总空白 space。我有一组单词 W = [w1, w2, w3, ..., wn] 构成了我希望该段落包含的文本，每个单词 wi 我都有相应的长度 li。我还知道一行可以容纳的最大字符数，包括 spaces：m。我不会说话。
在这种情况下，我定义了一个关系来描述以单词 i 开头并以单词 j 结尾的行的空 space 的成本由下式给出c(i, j) = (m - (j - i) - sum_{k=i}^{k = j}lk)^3。所以c(i, j)必须是正数，否则我需要断行如果j = n，我不惩罚最后一行的空space：c(i, n) = 0.
有了这个参数，我找到了一种算法，可以在传递到下一行之前最小化每行的成本并计算总成本。然而，最小化每条线的成本并不一定意味着总成本也最小化。
我能想到的任何可以最小化总成本的过程都需要对每行中的单词数进行大量排列，因此无法实现。任何计算最小成本的可行算法的想法？
设G为一个图，其中每个顶点V_x_y表示由组成的部分段落y 行，总共使用 x 个单词。如果 z > x 和单词 w_(x+1) 到 w_z 适合在一条线上。每条这样的边都有成本 c(x+1,z)，即它代表的附加线的成本。
现在，您的问题是找到从 V_0_0 到顶点 V_n_y 的最小成本路径消耗所有单词。
您可以使用 Dijkstra 算法在 O(n^2 log n) 时间或更短的时间内找到此路径，或者如果您制定了一个像样的算法，则 A* 可以更快地找到它可接受的启发式。