DP19 自动换行问题 Word Wrap Problem @geeksforgeeks - c++编程基础

ng is used to store the results of subproblems. The array c[] can be computed from left to right, since each value depends only on earlier values.
To print the output, we keep track of what words go on what lines, we can keep a parallel p array that points to where each c value came from. The last line starts at word p[n] and goes through word n. The previous line starts at word p[p[n]] and goes through word p[n ] 1, etc. The function printSolution() uses p[] to print the solution.
In the below program, input is an array l[] that represents lengths of words in a sequence. The value l[i] indicates length of the ith word (i starts from 1) in theinput sequence.

http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/

另外可以参考wiki的这篇：https://zh.wikipedia.org/wiki/%E8%87%AA%E5%8A%A8%E6%8D%A2%E8%A1%8C

在TeX中使用的，则是另一个算法，旨在将行尾空格数的平方最小化，以产生一个更加美观的结果。以上的算法不能完成这一目标，例如：

aaa bb cc ddddd

如果惩罚函数定义为行尾剩余空格数的平方，则贪婪算法会得到一个次优解（为了简化起见，不妨假设采用定宽字体）：

------ 一行的宽度为6
aaa bb 剩余的空格数：0，平方=0
cc     剩余的空格数：4，平方=16
ddddd  剩余的空格数：1，平方=1

总计代价17，而最佳的解决方案是这样的：

------ 一行的宽度为6
aaa    剩余空格数：3 平方=9
bb cc  剩余空格数：1 平方=1
ddddd  剩余空格数：1 平方=1

请注意，第一行在bb前断开了，相对于在bb后断开的解法，可以得到更好的右边界和更低的代价11。

为了解决这个问题，我们需要定义一个惩罚函数 $c(i, j)$ ，用于计算包含单词 $\text{Word}[i]$ 到单词 $\text{Word}[j]$ 的一行的代价：

$c(i, j) = \left(\text{LineWidth}-(j-i)\cdot\text{OneSpaceWidth}-\sum_{k=i}^j \text{WidthOf}(\text{Word}[k])\right)^P.$

其中 $P$ 通常为 $2$ 或 $3$ 。另外，有一些特殊的情况值得考虑：如果结果为负（即单词串不能全部放在一行里），惩罚函数需要反映跟踪或压缩文本以适应一行的代价；如果这是不可能的，则返回 $\infty$

最优解的代价可以用以下的递归式定义：

$f(j) = \begin{cases} c(1, j) & \text{if } c(1, j) < \infty, \\ \displaystyle \min_{1 \leq k < j} \big(f(k) + c(k + 1, j)\big) & \text{if } c(1, j) = \infty.\end{cases}$

这可以利用动态规划来高效地实现，时间和空间复杂度均为 $O(j^2)$

package DP;

import java.util.Arrays;

public class WordWrap {

	public static void main(String[] args) {
		int[] l = {3, 2, 2, 5};
		int n = l.length;
		int M = 6;
		solveWordWrap(l, n, M);
	}

	// l[] represents lengths of different words in input sequence. For example, 
	// l[] = {3, 2, 2, 5} is for a sentence like "aaa bb cc ddddd".  n is size of 
	// l[] and M is line width (maximum no. of characters that can fit in a line)
	// Time Complexity: O(n^2) Auxiliary Space: O(n^2)
	public static void solveWordWrap(int[] l, int n, int M){
		// For simplicity, 1 extra space is used in all below arrays 
		 
	    // extras[i][j] will have number of extra spaces if words from i 
	    // to j are put in a single line
		// extras[i][j]记录把单词序号i到j放在一行后剩余的空格数目
		int[][] extras = new int[n+1][n+1];
		
		// lc[i][j] will have cost of a line which has words from i to j
		// lc[i][j]记录把单词序号i到j放在一行后导致的花费cost
		int[][] lc = new int[n+1][n+1];
		
		// c[i] will have total cost of optimal arrangement of words from 1 to i
		// c[i]记录了把单词序号从1到i放在多行后导致的总的最小花费
		int[] c = new int[n+1];
		
		// p[] is used to print the solution. 
		// p[n]记录了单词编号p[n]到n被放在了同一行
		int[] p = new int[n+1];
		
		// calculate extra spaces in a single line.  The value extra[i][j]
	    // indicates extra spaces if words from word number i to j are
	    // placed in a single line
		for(int i=1; i<=n; i++){
			extras[i][i] = M-l[i-1];	// 如果只有一个单词，则剩余空格数为M扣除这个单词的长度
			for(int j=i+1; j<=n; j++){	// 否则剩余空格数为上一次剩余空格数扣除接下来用的单词长度
				extras[i][j] = extras[i][j-1]-l[j-1]-1;	// 因为单词之间要有空格隔开，所以多扣除一个1
			}
		}
		
//		print(extras);
		
		// Calculate line cost corresponding to the above calculated extra
	    // spaces. The value lc[i][j] indicates cost of putting words from
	    // word number i to j in a single line
		for(int i=1; i<=n; i++){			// 起始单词序号
			for(int j=i; j<=n; j++){		// j:结尾单词序号，j肯定大于i，因为j指向的单词在i之后
				if(extras[i][j] < 0){		// 空格数为负说明，放不下所以设为最大值
					lc[i][j] = Integer.MAX_VALUE;
				}else if(j==n && extras[i][j]>=0){	// 最后一个单词，后面有空格也无所谓
					lc[i][j] = 0;
				}else{	// 其余情况cost为空格数的平方
					lc[i][j] = extras[i][j]*extras[i][j];
				}
			}
		}
		
		// Calculate minimum cost and find minimum cost arrangement.
	    //  The value c[j] indicates optimized cost to arrange words
	    // from word number 1 to j.
		c[0] = 0;
		for(int j=1; j<=n; j++){	// 依次计算单词数目为j时的最小cost
			c[j] = Integer.MAX_VALUE;
			for(int i=1; i<=j; i++){	// i: 把i...j放在一行，然后计算剩下1...i的放法
				if(c[i-1]!=Integer.MAX_VALUE && lc[i][j]!=Integer.MAX_VALUE		// 防止溢出
						&& c[i-1]+lc[i][j]

点击复制链接与好友分享! 回本站首页

DP19 自动换行问题 Word Wrap Problem @geeksforgeeks(二)