Проблем умотавања речи


Ниво тешкоће Тежак
Често питани у Арцесиум Фацтсет ГреиОранге мицрософт Минтра Ола Цабс ПаиУ
Динамичко програмирање

Изјава о проблему

Проблем премотавања речи наводи да, дајући низ речи као улаз, морамо пронаћи број речи које се могу уклопити у један ред истовремено. Дакле, за ово стављамо преломе у датом низу тако да одштампани документ изгледа лепо. Уређивачи речи као што су Мицрософт Оффице, Либре Оффице и други алати за документе користе преломе редова како би документ изгледао лепо. Овде под лепим подразумевамо да просторе постављамо на равномерно распоређен начин. Не би требало да постоје линије са много додатних простора, а неке са малим количинама.

Овде такође претпостављамо да наша дужина речи не прелази величину реда. Само да учинимо ствари мало општијим, разматрамо функцију цонст у питању као (Број додатног простора) ^ 3, иначе би то било превише лако. Ова функција трошкова може се разликовати у зависности од постављеног питања.

Ворд Врап Дп приступ

Пример

Овде ћемо пружити број речи, величину речи и величину реда као улаз.

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

 

Ради једноставног разумевања, приказали смо унос као речи уместо вордСизе.

Објашњење: мачка је_

                        ан____

                        животиња

Овде су 4 додатна размака у другом реду и 1 у трећем реду.

Прорачун: 4 ^ 3 + 1 ^ 3 = 65

 

Постоји боље решење,

мачка___

је_

животиња

Дајући нам укупни трошак од 28 (3 ^ 3 + 1 ^ 3 + 0 ^ 3), што је боље од 65.

Сада ћемо решити проблем премотавања речи помоћу Динамичко програмирање. Знамо да нашем проблему треба глобално оптимално решење и наш претходни алгоритам је као резултат покушавао да нам да локални оптимум. Овде ћемо пронаћи додатни простор заузет у свакој линији, а самим тим ћемо пронаћи и трошкове за сваки ред. Одржаваћемо матрицу ектраСпаце која ће рећи ектраСпацеу остављеном у реду да су речи од и до ј повезане у једну линију. Затим ћемо даље користити ову екстраСпаце матрицу да бисмо пронашли минималне трошкове.

код

Ц ++ код за проблем са превлачењем речи

#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

Јава код за проблем са превлачењем речи

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

Анализа сложености

Сложеност времена: О (н ^ 2)

Овде, будући да наша спољна петља траје од 1 до н, а наша унутрашња од 1 до и, имамо полиномску временску сложеност О (н ^ 2).

Сложеност свемира: О (н ^ 2)

Овде је наш низ ектраСпаце 2Д низ који је величине Н * Н, што нам даје полиномску сложеност простора од О (Н ^ 2).