Dada una secuencia de palabras y un límite en el número de caracteres que se pueden poner en una línea (ancho de línea). Coloque saltos de línea en la secuencia dada de modo que las líneas se impriman con claridad. Suponga que la longitud de cada palabra es más pequeña que el ancho de la línea.
Los procesadores de texto como MS Word hacen la tarea de colocar saltos de línea. La idea es tener líneas equilibradas. En otras palabras, no tener pocas líneas con muchos espacios adicionales y algunas líneas con una pequeña cantidad de espacios adicionales.
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 lines
For 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 lines
Geeks for Geeks
presents word
wrap 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
Tenga en cuenta que la función de costo total no es la suma de los espacios adicionales, sino la suma de los cubos (o también se usa el cuadrado) de los espacios adicionales. La idea detrás de esta función de costo es equilibrar los espacios entre las líneas. Por ejemplo, considere las siguientes dos disposiciones del mismo conjunto de palabras:
1) Hay 3 líneas. Una línea tiene 3 espacios adicionales y todas las demás líneas tienen 0 espacios adicionales. Espacios adicionales totales = 3 + 0 + 0 = 3. Costo total = 3*3*3 + 0*0*0 + 0*0*0 = 27. 2)
Hay 3 líneas. Cada una de las 3 líneas tiene un espacio adicional. Espacios adicionales totales = 1 + 1 + 1 = 3. Costo total = 1*1*1 + 1*1*1 + 1*1*1 = 3.
Los espacios adicionales totales son 3 en ambos escenarios, pero se debe preferir el segundo arreglo porque los espacios adicionales están equilibrados en las tres líneas. La función de costo con suma cúbica sirve porque el valor del costo total en el segundo escenario es menor.
Método 1 (solución codiciosa)
La solución codiciosa es colocar tantas palabras como sea posible en la primera línea. Luego haz lo mismo para la segunda línea y así sucesivamente hasta colocar todas las palabras. Esta solución da una solución óptima para muchos casos, pero no da una solución óptima en todos los casos. Por ejemplo, considere la siguiente string «aaa bb cc ddddd» y el ancho de línea como 6. El método Greedy producirá el siguiente resultado.
aaa bb cc ddddd
Los espacios adicionales en las 3 líneas anteriores son 0, 4 y 1 respectivamente. Entonces el costo total es 0 + 64 + 1 = 65.
Pero la solución anterior no es la mejor solución. La siguiente disposición tiene espacios más equilibrados. Por lo tanto, menor valor de la función de costo total.
aaa bb cc ddddd
Los espacios adicionales en las 3 líneas anteriores son 3, 1 y 1 respectivamente. Por lo tanto, el costo total es 27 + 1 + 1 = 29.
A pesar de ser subóptimo en algunos casos, muchos procesadores de texto como MS Word y OpenOffice.org Writer utilizan el enfoque codicioso.
Método 2 (Enfoque recursivo con memorización)
El problema se puede resolver utilizando un enfoque de divide y vencerás (recursivo). El algoritmo para el mismo se menciona a continuación:
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 line
4. We use memoization table of size n (number of words) * k (line length), to keep track of already visited positions.
C++
#include <bits/stdc++.h>
using namespace std;
int solveWordWrapUsingMemo(int words[], int n, int length,
int wordIndex, int remLength,
vector<vector<int> > memo);
int square(int n) { return n * n; }
int solveWordWrapUtil(int words[], int n, int length,
int wordIndex, int remLength,
vector<vector<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 min(solveWordWrapUsingMemo(
words, n, length, wordIndex + 1,
remLength == length
? remLength - currWord
: remLength - currWord - 1,
memo),
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);
}
}
int solveWordWrapUsingMemo(int words[], int n, int length,
int wordIndex, int remLength,
vector<vector<int> > memo)
{
if (memo[wordIndex][remLength] != -1) {
return memo[wordIndex][remLength];
}
memo[wordIndex][remLength] = solveWordWrapUtil(
words, n, length, wordIndex, remLength, memo);
return memo[wordIndex][remLength];
}
int solveWordWrap(int words[], int n, int k)
{
vector<vector<int> > memo(n, vector<int>(k + 1, -1));
return solveWordWrapUsingMemo(words, n, k, 0, k, memo);
}
int main()
{
int words[] = { 3, 2, 2, 5 };
int n = sizeof(words) / sizeof(words[0]);
int k = 6;
cout << solveWordWrap(words, n, k);
return 0;
}
/* This Code is contributed by Tapesh (tapeshdua420) */
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));
}
}
Python3
# Python program for the above approach def square(n) : return n * n def solveWordWrapUtil(words, n, length, wordIndex, remLength, memo) : # base case for last word if (wordIndex == n - 1) : memo[wordIndex][remLength] = 0 if (words[wordIndex] < remLength) else square(remLength) return memo[wordIndex][remLength] currWord = words[wordIndex] # if word can fit in the remaining line if (currWord < remLength) : return min(solveWordWrapUsingMemo( words, n, length, wordIndex + 1, remLength - currWord if (remLength == length) else remLength - currWord - 1, memo), 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)) def solveWordWrapUsingMemo(words, n, length, wordIndex, remLength, memo) : if (memo[wordIndex][remLength] != -1) : return memo[wordIndex][remLength] memo[wordIndex][remLength] = (solveWordWrapUtil( words, n, length, wordIndex, remLength, memo)) return memo[wordIndex][remLength] def solveWordWrap(words, n, k) : memo = [[10]* (k + 1)]* n return solveWordWrapUsingMemo(words, n, k, 0, k, memo) # Driver Code if __name__ == "__main__": words = [ 3, 2, 2, 5 ] n = len(words) k = 6 print(solveWordWrap(words, n, k)) # This code is contributed by sanjoy_62.
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
Javascript
<script>
/*package whatever //do not write package name here */
function solveWordWrap(nums , k) {
var memo = Array(nums.length).fill().map(()=>Array(k + 1).fill(-1));
return solveWordWrapUsingMemo(nums, nums.length, k, 0, k, memo);
}
function solveWordWrap1(words , n , length , wordIndex , remLength, memo) {
// base case for last word
if (wordIndex == n - 1) {
memo[wordIndex][remLength] = words[wordIndex] < remLength ? 0 : square(remLength);
return memo[wordIndex][remLength];
}
var 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);
}
}
function solveWordWrapUsingMemo(words , n , length , wordIndex , remLength, memo) {
//if (memo[wordIndex][remLength] != -1) {
// return memo[wordIndex][remLength];
//}
memo[wordIndex][remLength] = solveWordWrap1(words, n, length, wordIndex, remLength, memo);
return memo[wordIndex][remLength];
}
function square(n) {
return n * n;
}
var arr = [ 3, 2, 2, 5 ];
document.write(solveWordWrap(arr, 6));
// This code is contributed by gauravrajput1
</script>
Producción
10
Método 3 (Programación dinámica)
El siguiente enfoque dinámico sigue estrictamente el algoritmo dado en la solución del libro de Cormen. Primero calculamos los costos de todas las líneas posibles en una tabla 2D lc[][]. El valor lc[i][j] indica el costo de poner palabras de i a j en una sola línea donde i y j son índices de palabras en las secuencias de entrada. Si una secuencia de palabras de i a j no cabe en una sola línea, entonces lc[i][j] se considera infinito (para evitar que sea parte de la solución). Una vez que tenemos la tabla lc[][] construida, podemos calcular el costo total usando la siguiente fórmula recursiva. En la siguiente fórmula, C[j] es el costo total optimizado para ordenar palabras de 1 a j.
La recursividad anterior tiene la propiedad de subproblema superpuesto . Por ejemplo, la solución del subproblema c(2) es utilizada por c(3), C(4) y así sucesivamente. Entonces, la programación dinámica se usa para almacenar los resultados de los subproblemas. La array c[] se puede calcular de izquierda a derecha, ya que cada valor depende solo de los valores anteriores.
Para imprimir la salida, hacemos un seguimiento de qué palabras van en qué líneas, podemos mantener una array p paralela que apunte de dónde proviene cada valor c. La última línea comienza en la palabra p[n] y pasa por la palabra n. La línea anterior comienza en la palabra p[p[n]] y pasa por la palabra p[n] – 1, etc. La función printSolution() usa p[] para imprimir la solución.
En el siguiente programa, la entrada es una array l[] que representa la longitud de las palabras en una secuencia. El valor l[i] indica la longitud de la i-ésima palabra (i comienza desde 1) en la secuencia de entrada.
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 \n", 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>
Producción
Line number 1: From word no. 1 to 1 Line number 2: From word no. 2 to 3 Line number 3: From word no. 4 to 4
Complejidad de tiempo: O (n ^ 2)
Espacio auxiliar: O (n ^ 2) El espacio auxiliar utilizado en el programa anterior puede optimizarse a O (n) (consulte la referencia 2 para obtener más detalles)
Método 4
El siguiente enfoque reduce aún más la complejidad espacial del algoritmo.
C++
#include <iostream>
using namespace std;
void solveWordWrap(int n , int arr[], int k){
//initialize total cost
int total_cost = 0;
for(int i = 0; i < n - 1; i++){
//size of window left after the current element
int size = k - 1 - arr[i];
//cost of current line
int sum = k - arr[i];
while(size >= 0){
size = size - arr[i+1] - 1;
// breaks immidiately
if(size < 0){break;}
sum = sum - arr[i] - 1;
i++;
}
//add current cost to total cost
total_cost = total_cost + (sum*sum);
}
//print the total cost
cout << total_cost;
}
int main(){
int n = 4;
int nums[n] = {3,2,2,5};
int k = 6;
solveWordWrap(n, nums, k);
}
// this code is contributed by Sanyam Jain
Producción
10
Complejidad de tiempo: O(n^2)
Espacio auxiliar: O(1)(constante)
Problema de ajuste de palabras (solución optimizada para el espacio)
Referencias:
http://en.wikipedia.org/wiki/Word_wrap
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA