单词包装问题| DP-19-yiteyi-C++库

给定一个单词序列，以及一行中可以输入的字符数限制（线宽）。在给定的顺序中放置换行符，以便打印整齐。假设每个单词的长度小于线宽。像MS word这样的文字处理程序负责放置换行符。这个想法是要有平衡的线条。换句话说，不是只有几行有很多额外空间，有些行有少量额外空间。

null

The extra spaces includes spaces put at the end of every line except the last one.  The problem is to minimize the following total cost. Cost of a line = (Number of extra spaces in the line)^3 Total Cost = Sum of costs for all linesFor example, consider the following string and line width M = 15 "Geeks for Geeks presents word wrap problem"      Following is the optimized arrangement of words in 3 linesGeeks for Geekspresents wordwrap problem The total extra spaces in line 1, line 2 and line 3 are 0, 2 and 3 respectively. So optimal value of total cost is 0 + 2*2*2 + 3*3*3 = 35

请注意，总成本函数不是额外空间之和，而是额外空间的立方体（或正方形）之和。成本函数背后的理念是平衡线条之间的空间。例如，考虑下面两组相同单词的排列： 1) 有三行。一行有3个额外的空格，所有其他行有0个额外的空格。总额外空间=3+0+0=3。总成本=3*3*3+0*0*0+0*0*0=27。 2) 有三行。这三行中的每一行都有一个额外的空间。总额外空间=1+1+1=3。总成本=1*1*1+1*1*1+1*1*1=3。在这两种情况下，总的额外空间都是3，但第二种安排应该是首选的，因为额外空间在所有三条线路中都是平衡的。三次和的成本函数可以达到这个目的，因为第二种情况下总成本的值较小。

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法1（贪婪解） 贪婪的解决方案是在第一行中放置尽可能多的单词。然后对第二行执行同样的操作，依此类推，直到所有单词都放好。这种解决方案在许多情况下都能给出最优解，但并非在所有情况下都能给出最优解。例如，考虑以下字符串“AAA BB CC DDDDD”和线宽为6。贪婪方法将产生以下输出。

aaa bb cc ddddd

以上三行中的额外空格分别为0、4和1。所以总成本是0+64+1=65。但上述解决方案并不是最好的解决方案。下面的布局有更平衡的空间。因此总成本函数的价值较小。

aaabb ccddddd

以上三行中的额外空格分别为3、1和1。所以总成本是27+1+1=29。尽管在某些情况下是次优的，但贪婪方法被许多字处理器使用，如MS word和OpenOffice。组织撰稿人。

方法2（带记忆的递归方法）

这个问题可以用分而治之（递归）的方法来解决。其算法如下所述：

1. We recur for each word starting with first word, and remaining length of the line (initially k).2. The last word would be the base case:    We check if we can put it on same line:        if yes, then we return cost as 0.        if no, we return cost of current line based on its remaining length.3. For non-last words, we have to check if it can fit in the current line:    if yes, then we have two choices i.e. whether to put it in same line or next line.        if we put it on next line: cost1 = square(remLength) + cost of putting word on next line.        if we put it on same line: cost2 = cost of putting word on same line.        return min(cost1, cost2)    if no, then we have to put it on next line:        return cost of putting word on next line4. We use memoization table of size n (number of words) * k (line length), to keep track of already visited positions.

JAVA

                         /*package whatever //do not write package name here */                       
           
                         import                                     java.io.*;                       
                         import                                     java.util.Arrays;                       
           
                         public                                     class                                     WordWrapDpMemo {                       
           
                                                 private                                     int                                     solveWordWrap(                                     int                                     [] nums,                                     int                                     k) {                       
                                                 int                                     [][] memo =                                     new                                     int                                     [nums.length][k +                                     1                                     ];                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < nums.length; i++) {                       
                                                 Arrays.fill(memo[i], -                                     1                                     );                       
                                                 }                       
                                                 return                                     solveWordWrapUsingMemo(nums, nums.length, k,                                     0                                     , k, memo);                       
                                                 }                       
           
                                                 private                                     int                                     solveWordWrap(                                     int                                     [] words,                                     int                                     n,                                     int                                     length,                                     int                                     wordIndex,                                     int                                     remLength,                                     int                                     [][] memo) {                       
           
                                                 //base case for last word                       
                                                 if                                     (wordIndex == n -                                     1                                     ) {                       
                                                 memo[wordIndex][remLength] = words[wordIndex] < remLength ?                                     0                                     : square(remLength);                       
                                                 return                                     memo[wordIndex][remLength];                       
                                                 }                       
           
                                                 int                                     currWord = words[wordIndex];                       
                                                 //if word can fit in the remaining line                       
                                                 if                                     (currWord < remLength) {                       
                                                 return                                     Math.min(                       
                                                 //if word is kept on same line                       
                                                 solveWordWrapUsingMemo(words, n, length, wordIndex +                                     1                                     , remLength == length ? remLength - currWord : remLength - currWord -                                     1                                     , memo),                       
                                                 //if word is kept on next line                       
                                                 square(remLength) + solveWordWrapUsingMemo(words, n, length, wordIndex +                                     1                                     , length - currWord, memo)                       
                                                 );                       
                                                 }                                     else                                     {                       
                                                 //if word is kept on next line                       
                                                 return                                     square(remLength) + solveWordWrapUsingMemo(words, n, length, wordIndex +                                     1                                     , length - currWord, memo);                       
                                                 }                       
                                                 }                       
           
                                                 private                                     int                                     solveWordWrapUsingMemo(                                     int                                     [] words,                                     int                                     n,                                     int                                     length,                                     int                                     wordIndex,                                     int                                     remLength,                                     int                                     [][] memo) {                       
                                                 if                                     (memo[wordIndex][remLength] != -                                     1                                     ) {                       
                                                 return                                     memo[wordIndex][remLength];                       
                                                 }                       
           
                                                 memo[wordIndex][remLength] = solveWordWrap(words, n, length, wordIndex, remLength, memo);                       
                                                 return                                     memo[wordIndex][remLength];                       
                                                 }                       
           
                                                 private                                     int                                     square(                                     int                                     n) {                       
                                                 return                                     n * n;                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args) {                       
                                                 System.out.println(                                     new                                     WordWrapDpMemo().solveWordWrap(                                     new                                     int                                     []{                                     3                                     ,                                     2                                     ,                                     2                                     ,                                     5                                     },                                     6                                     ));                       
                                                 }                       
                         }                       

C#

                         /*package whatever //do not write package name here */                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         public                                     class                                     WordWrapDpMemo {                       
           
                                                 private                                     int                                     solveWordWrap(                                     int                                     [] nums,                                     int                                     k)                       
                                                 {                       
                                                 int                                     [,] memo =                                     new                                     int                                     [nums.Length ,k + 1];                       
                                                 for                                     (                                     int                                     i = 0; i < memo.GetLength(0); i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 0; j < memo.GetLength(1); j++)                       
                                                 memo[i, j] = -1;                       
                                                 }                       
                                                 return                                     solveWordWrapUsingMemo(nums, nums.Length,                       
                                                 k, 0, k, memo);                       
                                                 }                       
           
                                                 private                                     int                                     solveWordWrap(                                     int                                     [] words,                                     int                                     n,                       
                                                 int                                     length,                                     int                                     wordIndex,                       
                                                 int                                     remLength,                                     int                                     [,] memo)                       
                                                 {                       
           
                                                 // base case for last word                       
                                                 if                                     (wordIndex == n - 1) {                       
                                                 memo[wordIndex, remLength] = words[wordIndex] <                       
                                                 remLength ? 0 : square(remLength);                       
                                                 return                                     memo[wordIndex, remLength];                       
                                                 }                       
           
                                                 int                                     currWord = words[wordIndex];                       
                                   
                                                 // if word can fit in the remaining line                       
                                                 if                                     (currWord < remLength) {                       
                                                 return                                     Math.Min(                       
                                   
                                                 // if word is kept on same line                       
                                                 solveWordWrapUsingMemo(words, n, length, wordIndex + 1,                       
                                                 remLength == length ? remLength -                       
                                                 currWord : remLength -                       
                                                 currWord - 1, memo),                       
                                   
                                                 // if word is kept on next line                       
                                                 square(remLength)                       
                                                 + solveWordWrapUsingMemo(words, n,                       
                                                 length,                       
                                                 wordIndex + 1,                       
                                                 length - currWord,                       
                                                 memo));                       
                                                 }                                     else                                     {                       
                                                 // if word is kept on next line                       
                                                 return                                     square(remLength) +                       
                                                 solveWordWrapUsingMemo(words, n, length,                       
                                                 wordIndex + 1,                       
                                                 length - currWord, memo);                       
                                                 }                       
                                                 }                       
           
                                                 private                                     int                                     solveWordWrapUsingMemo(                                     int                                     [] words,                                     int                                     n,                       
                                                 int                                     length,                                     int                                     wordIndex,                       
                                                 int                                     remLength,                                     int                                     [,] memo)                       
                                                 {                       
                                                 if                                     (memo[wordIndex,remLength] != -1)                       
                                                 {                       
                                                 return                                     memo[wordIndex,remLength];                       
                                                 }                       
           
                                                 memo[wordIndex,remLength] = solveWordWrap(words,                       
                                                 n, length,                       
                                                 wordIndex,                       
                                                 remLength, memo);                       
                                                 return                                     memo[wordIndex, remLength];                       
                                                 }                       
           
                                                 private                                     int                                     square(                                     int                                     n) {                       
                                                 return                                     n * n;                       
                                                 }                       
           
                                                 public                                     static                                     void                                     Main(String[] args) {                       
                                                 Console.WriteLine(                                     new                                     WordWrapDpMemo().                       
                                                 solveWordWrap(                                     new                                     int                                     [] { 3, 2, 2, 5 }, 6));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by gauravrajput1                       

输出

方法3（动态规划） 下面的动态方法严格遵循Cormen书中给出的算法。首先，我们计算2D表格lc[]中所有可能行的成本。值lc[i][j]表示将i到j的单词放在一行中的成本，其中i和j是输入序列中单词的索引。如果从i到j的一系列单词不能放在一行中，那么lc[i][j]被认为是无限的（以避免它成为解决方案的一部分）。一旦我们构造了lc[]表，我们就可以使用下面的递归公式计算总成本。在下面的公式中，C[j]是从1到j排列单词的最佳总成本。

图片[1]-单词包装问题| DP-19-yiteyi-C++库

上面的递归已经实现重叠子问题性质例如，子问题c（2）的解被c（3）、c（4）等使用。所以动态规划被用来存储子问题的结果。数组c[]可以从左到右计算，因为每个值只取决于之前的值。为了打印输出，我们跟踪哪些字在哪些行上，我们可以保持一个平行的p数组，指向每个c值的来源。最后一行从单词p[n]开始，经过单词n。前一行从单词p[p[n]]开始，经过单词p[n]-1，等等。函数printSolution（）使用p[]打印解决方案。在下面的程序中，输入是一个数组l[]，表示序列中的单词长度。值l[i]表示输入序列中第i个字的长度（i从1开始）。

C++

                         // A Dynamic programming solution for Word Wrap Problem                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         #define INF INT_MAX                       
           
                         // A utility function to print the solution                       
                         int                                     printSolution (                                     int                                     p[],                                     int                                     n);                       
           
                         // 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)                       
                         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                       
                                                 int                                     extras[n+1][n+1];                       
           
                                                 // lc[i][j] will have cost of a line which has words from                       
                                                 // i to j                       
                                                 int                                     lc[n+1][n+1];                       
           
                                                 // c[i] will have total cost of optimal arrangement of words                       
                                                 // from 1 to i                       
                                                 int                                     c[n+1];                       
           
                                                 // p[] is used to print the solution.                       
                                                 int                                     p[n+1];                       
           
                                                 int                                     i, j;                       
           
                                                 // 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                                     (i = 1; i <= n; i++)                       
                                                 {                       
                                                 extras[i][i] = M - l[i-1];                       
                                                 for                                     (j = i+1; j <= n; j++)                       
                                                 extras[i][j] = extras[i][j-1] - l[j-1] - 1;                       
                                                 }                       
           
                                                 // 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                                     (i = 1; i <= n; i++)                       
                                                 {                       
                                                 for                                     (j = i; j <= n; j++)                       
                                                 {                       
                                                 if                                     (extras[i][j] < 0)                       
                                                 lc[i][j] = INF;                       
                                                 else                                     if                                     (j == n && extras[i][j] >= 0)                       
                                                 lc[i][j] = 0;                       
                                                 else                       
                                                 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                                     (j = 1; j <= n; j++)                       
                                                 {                       
                                                 c[j] = INF;                       
                                                 for                                     (i = 1; i <= j; i++)                       
                                                 {                       
                                                 if                                     (c[i-1] != INF && lc[i][j] != INF &&                       
                                                 (c[i-1] + lc[i][j] < c[j]))                       
                                                 {                       
                                                 c[j] = c[i-1] + lc[i][j];                       
                                                 p[j] = i;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 printSolution(p, n);                       
                         }                       
           
                         int                                     printSolution (                                     int                                     p[],                                     int                                     n)                       
                         {                       
                                                 int                                     k;                       
                                                 if                                     (p[n] == 1)                       
                                                 k = 1;                       
                                                 else                       
                                                 k = printSolution (p, p[n]-1) + 1;                       
                                                 cout<<                                     "Line number "                                     <<k<<                                     ": From word no. "                                     <<p[n]<<                                     " to "                                     <<n<<endl;                       
                                                 return                                     k;                       
                         }                       
           
                         // Driver program to test above functions                       
                         int                                     main()                       
                         {                       
                                                 int                                     l[] = {3, 2, 2, 5};                       
                                                 int                                     n =                                     sizeof                                     (l)/                                     sizeof                                     (l[0]);                       
                                                 int                                     M = 6;                       
                                                 solveWordWrap (l, n, M);                       
                                                 return                                     0;                       
                         }                       
           
           
                         //This is code is contributed by rathbhupendra                       

C

                         // A Dynamic programming solution for Word Wrap Problem                       
                         #include <limits.h>                       
                         #include <stdio.h>                       
                         #define INF INT_MAX                       
           
                         // A utility function to print the solution                       
                         int                                     printSolution (                                     int                                     p[],                                     int                                     n);                       
           
                         // 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)                       
                         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                       
                                                 int                                     extras[n+1][n+1];                       
           
                                                 // lc[i][j] will have cost of a line which has words from                       
                                                 // i to j                       
                                                 int                                     lc[n+1][n+1];                       
                                   
                                                 // c[i] will have total cost of optimal arrangement of words                       
                                                 // from 1 to i                       
                                                 int                                     c[n+1];                       
           
                                                 // p[] is used to print the solution.                       
                                                 int                                     p[n+1];                       
           
                                                 int                                     i, j;                       
           
                                                 // 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                                     (i = 1; i <= n; i++)                       
                                                 {                       
                                                 extras[i][i] = M - l[i-1];                       
                                                 for                                     (j = i+1; j <= n; j++)                       
                                                 extras[i][j] = extras[i][j-1] - l[j-1] - 1;                       
                                                 }                       
           
                                                 // 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                                     (i = 1; i <= n; i++)                       
                                                 {                       
                                                 for                                     (j = i; j <= n; j++)                       
                                                 {                       
                                                 if                                     (extras[i][j] < 0)                       
                                                 lc[i][j] = INF;                       
                                                 else                                     if                                     (j == n && extras[i][j] >= 0)                       
                                                 lc[i][j] = 0;                       
                                                 else                       
                                                 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                                     (j = 1; j <= n; j++)                       
                                                 {                       
                                                 c[j] = INF;                       
                                                 for                                     (i = 1; i <= j; i++)                       
                                                 {                       
                                                 if                                     (c[i-1] != INF && lc[i][j] != INF &&                       
                                                 (c[i-1] + lc[i][j] < c[j]))                       
                                                 {                       
                                                 c[j] = c[i-1] + lc[i][j];                       
                                                 p[j] = i;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 printSolution(p, n);                       
                         }                       
           
                         int                                     printSolution (                                     int                                     p[],                                     int                                     n)                       
                         {                       
                                                 int                                     k;                       
                                                 if                                     (p[n] == 1)                       
                                                 k = 1;                       
                                                 else                       
                                                 k = printSolution (p, p[n]-1) + 1;                       
                                                 printf                                     (                                     "Line number %d: From word no. %d to %d "                                     , k, p[n], n);                       
                                                 return                                     k;                       
                         }                       
           
                         // Driver program to test above functions                       
                         int                                     main()                       
                         {                       
                                                 int                                     l[] = {3, 2, 2, 5};                       
                                                 int                                     n =                                     sizeof                                     (l)/                                     sizeof                                     (l[0]);                       
                                                 int                                     M = 6;                       
                                                 solveWordWrap (l, n, M);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // A Dynamic programming solution for                       
                         // Word Wrap Problem in Java                       
                         public                                     class                                     WordWrap                       
                         {                       
           
                                                 final                                     int                                     MAX = Integer.MAX_VALUE;                       
                                   
                                                 // A utility function to print the solution                       
                                                 int                                     printSolution (                                     int                                     p[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     k;                       
                                                 if                                     (p[n] ==                                     1                                     )                       
                                                 k =                                     1                                     ;                       
                                                 else                       
                                                 k = printSolution (p, p[n]-                                     1                                     ) +                                     1                                     ;                       
                                                 System.out.println(                                     "Line number"                                     +                                     " "                                     + k +                                     ": "                                     +                       
                                                 "From word no."                                     +                                     " "                                     + p[n] +                                     " "                                     +                                     "to"                                     +                                     " "                                     + n);                       
                                                 return                                     k;                       
                                                 }                       
           
                         // 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)                       
                                                 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                       
                                                 int                                     extras[][] =                                     new                                     int                                     [n+                                     1                                     ][n+                                     1                                     ];                       
                                   
                                                 // lc[i][j] will have cost of a line which has words from                       
                                                 // i to j                       
                                                 int                                     lc[][]=                                     new                                     int                                     [n+                                     1                                     ][n+                                     1                                     ];                       
                                   
                                                 // c[i] will have total cost of optimal arrangement of words                       
                                                 // from 1 to i                       
                                                 int                                     c[] =                                     new                                     int                                     [n+                                     1                                     ];                       
                                   
                                                 // p[] is used to print the solution.                       
                                                 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                                     ];                       
                                                 for                                     (                                     int                                     j = i+                                     1                                     ; j <= n; j++)                       
                                                 extras[i][j] = extras[i][j-                                     1                                     ] - l[j-                                     1                                     ] -                                     1                                     ;                       
                                                 }                       
                                   
                                                 // 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++)                       
                                                 {                       
                                                 if                                     (extras[i][j] <                                     0                                     )                       
                                                 lc[i][j] = MAX;                       
                                                 else                                     if                                     (j == n && extras[i][j] >=                                     0                                     )                       
                                                 lc[i][j] =                                     0                                     ;                       
                                                 else                       
                                                 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++)                       
                                                 {                       
                                                 c[j] = MAX;                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= j; i++)                       
                                                 {                       
                                                 if                                     (c[i-                                     1                                     ] != MAX && lc[i][j] != MAX &&                       
                                                 (c[i-                                     1                                     ] + lc[i][j] < c[j]))                       
                                                 {                       
                                                 c[j] = c[i-                                     1                                     ] + lc[i][j];                       
                                                 p[j] = i;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 printSolution(p, n);                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 WordWrap w =                                     new                                     WordWrap();                       
                                                 int                                     l[] = {                                     3                                     ,                                     2                                     ,                                     2                                     ,                                     5                                     };                       
                                                 int                                     n = l.length;                       
                                                 int                                     M =                                     6                                     ;                       
                                                 w.solveWordWrap (l, n, M);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Saket Kumar                       

Python3

                         # A Dynamic programming solution                       
                         # for Word Wrap Problem                       
           
                         # A utility function to print                       
                         # the solution                       
                         # 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)                       
                         INF                                     =                                     2147483647                       
                         def                                     printSolution(p, n):                       
                                                 k                                     =                                     0                       
                                                 if                                     p[n]                                     =                                     =                                     1                                     :                       
                                                 k                                     =                                     1                       
                                                 else                                     :                       
                                                 k                                     =                                     printSolution(p, p[n]                                     -                                     1                                     )                                     +                                     1                       
                                                 print                                     (                                     'Line number '                                     , k,                                     ': From word no. '                                     ,                       
                                                 p[n],                                     'to '                                     , n)                       
                                                 return                                     k                       
           
                         def                                     solveWordWrap (l, n, 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                                     =                                     [[                                     0                                     for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                                 for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                   
                                                 # lc[i][j] will have cost of a line                       
                                                 # which has words from i to j                       
                                                 lc                                     =                                     [[                                     0                                     for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                                 for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                   
                                                 # c[i] will have total cost of                       
                                                 # optimal arrangement of words                       
                                                 # from 1 to i                       
                                                 c                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                   
                                                 # p[] is used to print the solution.                       
                                                 p                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (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                                     i                                     in                                     range                                     (n                                     +                                     1                                     ):                       
                                                 extras[i][i]                                     =                                     M                                     -                                     l[i                                     -                                     1                                     ]                       
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     , n                                     +                                     1                                     ):                       
                                                 extras[i][j]                                     =                                     (extras[i][j                                     -                                     1                                     ]                                     -                       
                                                 l[j                                     -                                     1                                     ]                                     -                                     1                                     )                       
                                   
                                                 # 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                                     i                                     in                                     range                                     (n                                     +                                     1                                     ):                       
                                                 for                                     j                                     in                                     range                                     (i, n                                     +                                     1                                     ):                       
                                                 if                                     extras[i][j] <                                     0                                     :                       
                                                 lc[i][j]                                     =                                     INF;                       
                                                 elif                                     j                                     =                                     =                                     n                                     and                                     extras[i][j] >                                     =                                     0                                     :                       
                                                 lc[i][j]                                     =                                     0                       
                                                 else                                     :                       
                                                 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                                     j                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                                 c[j]                                     =                                     INF                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , j                                     +                                     1                                     ):                       
                                                 if                                     (c[i                                     -                                     1                                     ] !                                     =                                     INF                                     and                       
                                                 lc[i][j] !                                     =                                     INF                                     and                       
                                                 ((c[i                                     -                                     1                                     ]                                     +                                     lc[i][j]) < c[j])):                       
                                                 c[j]                                     =                                     c[i                                     -                                     1                                     ]                                     +                                     lc[i][j]                       
                                                 p[j]                                     =                                     i                       
                                                 printSolution(p, n)                       
                                   
                         # Driver Code                       
                         l                                     =                                     [                                     3                                     ,                                     2                                     ,                                     2                                     ,                                     5                                     ]                       
                         n                                     =                                     len                                     (l)                       
                         M                                     =                                     6                       
                         solveWordWrap(l, n, M)                       
           
                         # This code is contributed by sahil shelangia                       

C#

                         // A Dynamic programming solution for Word Wrap                       
                         // Problem in Java                       
                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
           
                                                 static                                     int                                     MAX =                                     int                                     .MaxValue;                       
                                   
                                                 // A utility function to print the solution                       
                                                 static                                     int                                     printSolution (                                     int                                     []p,                                     int                                     n)                       
                                                 {                       
                                                 int                                     k;                       
                                   
                                                 if                                     (p[n] == 1)                       
                                                 k = 1;                       
                                                 else                       
                                                 k = printSolution (p, p[n]-1) + 1;                       
                                   
                                                 Console.WriteLine(                                     "Line number"                                     +                                     " "                       
                                                 + k +                                     ": From word no."                                     +                                     " "                       
                                                 + p[n] +                                     " "                                     +                                     "to"                                     +                                     " "                                     + n);                       
                                                 return                                     k;                       
                                                 }                       
           
                                                 // 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)                       
                                                 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                       
                                                 int                                     [,]extras =                                     new                                     int                                     [n+1,n+1];                       
                                   
                                                 // lc[i][j] will have cost of a line                       
                                                 // which has words from i to j                       
                                                 int                                     [,]lc =                                     new                                     int                                     [n+1,n+1];                       
                                   
                                                 // c[i] will have total cost of                       
                                                 // optimal arrangement of words                       
                                                 // from 1 to i                       
                                                 int                                     []c =                                     new                                     int                                     [n+1];                       
                                   
                                                 // p[] is used to print the solution.                       
                                                 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];                       
                                   
                                                 for                                     (                                     int                                     j = i+1; j <= n; j++)                       
                                                 extras[i,j] = extras[i,j-1]                       
                                                 - l[j-1] - 1;                       
                                                 }                       
                                   
                                                 // 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++)                       
                                                 {                       
                                                 if                                     (extras[i,j] < 0)                       
                                                 lc[i,j] = MAX;                       
                                                 else                                     if                                     (j == n &&                       
                                                 extras[i,j] >= 0)                       
                                                 lc[i,j] = 0;                       
                                                 else                       
                                                 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++)                       
                                                 {                       
                                                 c[j] = MAX;                       
                                                 for                                     (                                     int                                     i = 1; i <= j; i++)                       
                                                 {                       
                                                 if                                     (c[i-1] != MAX && lc[i,j]                       
                                                 != MAX && (c[i-1] + lc[i,j]                       
                                                 < c[j]))                       
                                                 {                       
                                                 c[j] = c[i-1] + lc[i,j];                       
                                                 p[j] = i;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 printSolution(p, n);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []l = {3, 2, 2, 5};                       
                                                 int                                     n = l.Length;                       
                                                 int                                     M = 6;                       
                                                 solveWordWrap (l, n, M);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal.                       

Javascript

                         <script>                       
                                                 // A Dynamic programming solution for                       
                                                 // Word Wrap Problem in Javascript                       
                                   
                                                 let MAX = Number.MAX_VALUE;                       
                                   
                                                 // A utility function to print the solution                       
                                                 function                                     printSolution (p, n)                       
                                                 {                       
                                                 let k;                       
                                                 if                                     (p[n] == 1)                       
                                                 k = 1;                       
                                                 else                       
                                                 k = printSolution (p, p[n]-1) + 1;                       
                                                 document.write(                                     "Line number"                                     +                                     " "                                     + k +                                     ": "                                     +                       
                                                 "From word no."                                     +                                     " "                                     + p[n] +                                     " "                                     +                                     "to"                                     +                                     " "                                     + n +                                     "</br>"                                     );                       
                                                 return                                     k;                       
                                                 }                       
                                   
                                                 // 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)                       
                                                 function                                     solveWordWrap (l, n, 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                       
                                                 let extras =                                     new                                     Array(n+1);                       
                                   
                                                 // lc[i][j] will have cost of a line which has words from                       
                                                 // i to j                       
                                                 let lc =                                     new                                     Array(n+1);                       
                                   
                                                 for                                     (let i = 0; i < n + 1; i++)                       
                                                 {                       
                                                 extras[i] =                                     new                                     Array(n + 1);                       
                                                 lc[i] =                                     new                                     Array(n + 1);                       
                                                 for                                     (let j = 0; j < n + 1; j++)                       
                                                 {                       
                                                 extras[i][j] = 0;                       
                                                 lc[i][j] = 0;                       
                                                 }                       
                                                 }                       
                                   
                                                 // c[i] will have total cost of optimal arrangement of words                       
                                                 // from 1 to i                       
                                                 let c =                                     new                                     Array(n+1);                       
                                   
                                                 // p[] is used to print the solution.                       
                                                 let p =                                     new                                     Array(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                                     (let i = 1; i <= n; i++)                       
                                                 {                       
                                                 extras[i][i] = M - l[i-1];                       
                                                 for                                     (let j = i+1; j <= n; j++)                       
                                                 extras[i][j] = extras[i][j-1] - l[j-1] - 1;                       
                                                 }                       
                                   
                                                 // 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                                     (let i = 1; i <= n; i++)                       
                                                 {                       
                                                 for                                     (let j = i; j <= n; j++)                       
                                                 {                       
                                                 if                                     (extras[i][j] < 0)                       
                                                 lc[i][j] = MAX;                       
                                                 else                                     if                                     (j == n && extras[i][j] >= 0)                       
                                                 lc[i][j] = 0;                       
                                                 else                       
                                                 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                                     (let j = 1; j <= n; j++)                       
                                                 {                       
                                                 c[j] = MAX;                       
                                                 for                                     (let i = 1; i <= j; i++)                       
                                                 {                       
                                                 if                                     (c[i-1] != MAX && lc[i][j] != MAX &&                       
                                                 (c[i-1] + lc[i][j] < c[j]))                       
                                                 {                       
                                                 c[j] = c[i-1] + lc[i][j];                       
                                                 p[j] = i;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 printSolution(p, n);                       
                                                 }                       
                                   
                                                 let l = [3, 2, 2, 5];                       
                                                 let n = l.length;                       
                                                 let M = 6;                       
                                                 solveWordWrap (l, n, M);                       
                                   
                                                 // This code is contributed by mukesh07.                       
                         </script>                       

输出

Line number 1: From word no. 1 to 1Line number 2: From word no. 2 to 3Line number 3: From word no. 4 to 4

时间复杂度：O（n^2）辅助空间：O（n^2）上述程序中使用的辅助空间可以优化为O（n）（详情见参考文献2） 换行字问题（空间优化解决方案） 参考资料： http://en.wikipedia.org/wiki/Word_wrap 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章