Проблема з обгортанням слів


Рівень складності Жорсткий
Часто запитують у Арцезіум Факти GreyOrange Microsoft Мінтра Ола Кабіни PayU
Динамічне програмування

Постановка проблеми

Проблема переносу слів говорить, що, задаючи послідовність слів як вхідні дані, нам потрібно знайти кількість слів, які одночасно можна помістити в один рядок. Отже, для цього ми ставимо перерви в заданій послідовності так, щоб надрукований документ виглядав красиво. Редактори слів, такі як Microsoft Office, Libre Office та інші інструменти для документів, використовують розриви рядків, щоб зробити документ приємним. Тут, мило кажучи, ми маємо на увазі, що ми розміщуємо простори рівномірно. Не повинно бути рядків із великою кількістю зайвих пробілів, а деяких із невеликими сумами.

Тут ми також припускаємо, що довжина нашого слова не перевищує розміру рядка. Просто для того, щоб зробити речі трохи загальнішими, ми розглядаємо функцію const у питанні як (Кількість зайвого місця) ^ 3, інакше це було б надто просто. Ця функція вартості може змінюватися відповідно до заданого питання.

Word Wrap Dp підхід

Приклад

Тут ми введемо кількість слів, розмір слова та розмір рядка як вхідні дані.

number of words = 4

wordSize = { 3, 2, 2, 5}

lineSize = 6
28

Пояснення: Ми можемо розмістити 1-е слово на 1-му рядку з 3 додатковими пробілами, 2-е та 3-е слова на 2-му рядку з 1 додатковим пробілом, а останнє слово на 3-му рядку без зайвого пробілу (ми не будемо розглядати пробіли після останнього слова як додаткові пробіли). Таким чином, використовуючи нашу функцію витрат, ми знаходимо вартість як 28.

number of words = 3

wordSize = { 1, 1, 1}

lineSize = 10
00

Пояснення: Тут ми можемо розмістити всі слова в одному рядку, тобто 1-му рядку, а отже, вартість = 0.

 

Підхід до проблеми перенесення слів

Перший підхід, який спадає на думку, - це жадібне рішення, коли ми просто продовжуємо розміщувати слова в один рядок. Коли ми не можемо розмістити слово в одному рядку, ми переходимо до другого рядка. Здається, це працює чудово, але є кришка. Цей алгоритм не дасть оптимального результату, оскільки можуть бути такі випадки, що, якщо ми змінимо зайві пробіли, ми можемо отримати найкраще глобальне рішення.

Вихід із використанням Жадібного підходу

”cat is an animal”, line size = 6
65

 

Просто для простого розуміння, ми показали введення у вигляді слів замість wordSize.

Пояснення: cat is_

                        ан____

                        тварина

Тут є 4 додаткові пробіли на другому рядку і 1 на третьому рядку.

Розрахунок: 4 ^ 3 + 1 ^ 3 = 65

 

Існує краще рішення,

кішка___

є_

тварина

Даючи нам загальну вартість 28 (3 ^ 3 + 1 ^ 3 + 0 ^ 3), що краще, ніж 65.

Тепер ми вирішимо проблему переносу слів із використанням Динамічне програмування. Ми знаємо, що наша проблема потребує глобального оптимального рішення, і наш попередній алгоритм намагався дати нам локальний оптимум в результаті. Тут ми знайдемо зайвий простір у кожному рядку і, таким чином, знайдемо вартість кожного рядка відповідно. Ми підтримуватимемо матрицю extraSpace, яка буде повідомляти extraSpace, що залишився у рядку, зі слів від i до j, розташованих в одному рядку. Далі ми будемо використовувати цю матрицю extraSpace, щоб знайти мінімальну вартість.

код

Код C ++ для проблеми переносу слів

#include <bits/stdc++.h>
using namespace std;

int wordWrap (int wordSize[], int n, int lineSize) 
{ 
  int extraSpace[n+1][n+1];
  int minCost[n+1];

  for (int i=1;i<=n;i++) 
  { 
    extraSpace[i][i] = lineSize - wordSize[i-1];
    for (int j=i+1;j<=n;j++) 
        extraSpace[i][j] = extraSpace[i][j-1] - wordSize[j-1] - 1; 
  }
  
  minCost[0] = 0; 
  for (int i = 1; i <= n; i++) 
  { 
    minCost[i] = INT_MAX;
    for (int j = 1; j <= i; j++) 
    { 
        int cost; // stores cost of storing words[i,j] in single line
        
        //if extraSpace required is negative, then we can't place
        //words[i,j] in a single line, else if we placed our last
        //word, then we don't consider extraSpace, else calculate
        //cost as per given cost function.
        if(extraSpace[j][i]<0)cost = INT_MAX;
        else if(i==n && extraSpace[j][i]>=0)cost = 0;
        else cost = extraSpace[j][i]*extraSpace[j][i]*extraSpace[j][i];
        
      if (minCost[j-1] != INT_MAX && cost != INT_MAX
      && (minCost[j-1] + cost < minCost[i])) 
        minCost[i] = minCost[j-1] + cost;
    }
  }
  
  return minCost[n];
} 

int main() 
{
    int t;cin>>t;
    while(t--) {
       int n;cin>>n;
       int wordSize[n];
       for(int i=0;i<n;i++)
            cin>>wordSize[i];
       int lineSize;cin>>lineSize;
       int ans = wordWrap(wordSize, n, lineSize);
       cout<<ans<<endl;
    }
}
3
4
3 2 2 6
6
3
1 1 1
10
4
1 1 1 1
5
28
0
0

Код Java для проблеми переносу слів

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{ 
  static int wordWrap (int wordSize[], int n, int lineSize) 
  { 
    int extraSpace[][] = new int[n+1][n+1]; 
    int minCost[] = new int[n+1];
  
    for (int i=1;i<=n;i++) 
    { 
      extraSpace[i][i] = lineSize - wordSize[i-1];
      for (int j=i+1;j<=n;j++) 
          extraSpace[i][j] = extraSpace[i][j-1] - wordSize[j-1] - 1; 
    } 
    
    	minCost[0] = 0; 
    	for (int i = 1; i <= n; i++) 
    	{ 
    		minCost[i] = Integer.MAX_VALUE;
    		for (int j = 1; j <= i; j++) 
    		{ 
    		    int cost; // stores cost of storing words[i,j] in single line
    		    
    		    //if extraSpace required is negative, then we can't place
    		    //words[i,j] in a single line, else if we placed our last
    		    //word, then we don't consider extraSpace, else calculate
    		    //cost as per given cost function.
    		    if(extraSpace[j][i]<0)cost = Integer.MAX_VALUE;
    		    else if(i==n && extraSpace[j][i]>=0)cost = 0;
    		    else cost = extraSpace[j][i]*extraSpace[j][i]*extraSpace[j][i];
    		    
    			if (minCost[j-1] != Integer.MAX_VALUE && cost != Integer.MAX_VALUE
    			&& (minCost[j-1] + cost < minCost[i])) 
    				minCost[i] = minCost[j-1] + cost;
    		}
    	}
  
    return minCost[n];
  } 

  public static void main(String args[]) 
  {
      Scanner sc = new Scanner(System.in);
      
      int t = sc.nextInt();
      while(t-- > 0) {
         int n = sc.nextInt();
         int wordSize[] = new int[n];
         for(int i=0;i<n;i++)
              wordSize[i] = sc.nextInt();
         
         int lineSize = sc.nextInt();
         int ans = wordWrap(wordSize, n, lineSize);
         System.out.println(ans);
      }
  }
} 

 

3 
4 
3 2 2 6
6 
3 
1 1 1 
10 
4 
1 1 1 1 
5 
28 
0 
0

Аналіз складності

Складність часу: O (n ^ 2)

Тут, оскільки наш зовнішній цикл проходить від 1 до n, а наш внутрішній від 1 до i, ми маємо поліноміальну часову складність O (n ^ 2).

Складність простору: O (n ^ 2)

Тут наш масив extraSpace - це двовимірний масив розміром N * N, що надає нам поліноміальну просторову складність O (N ^ 2).