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


Ниво на трудност Трудно
Често задавани в Арцезиум FactSet GreyOrange Microsoft Myntra Ola Cabs 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.

 

Вижте също
Отпечатайте следващия по-голям брой Q заявки

Подход за проблем с опаковане на думи  

Първият подход, който идва на ум, е алчно решение, при което просто продължаваме да поставяме думите в един ред. Когато не можем да поставим дума на същия ред, ние се преместваме на втория ред. Това изглежда работи добре, но има уловка. Този алгоритъм няма да доведе до оптимален резултат, тъй като може да има такива случаи, че ако сменим допълнителните пространства, може да получим по-добро глобално решение.

Резултат, използвайки алчен подход

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

 

Само за просто разбиране, ние показахме въведеното като думи вместо wordSize.

Обяснение: котката е_

                        an____

                        животно

Тук има 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).

Вижте също
Пребройте начините за достигане до n-то стълбище, като използвате стъпки 1, 2 или 3

Сложност на пространството: O (n ^ 2)

Тук нашият масив extraSpace е двуизмерен масив, който е с размер N * N, което ни дава полиномиална пространствена сложност на O (N ^ 2).