Проблем со завиткување зборови


Ниво на тешкотија Тешко
Често прашувано во Арцесиум Факти GreyOrange Мајкрософт Минтра Кабини Ола PayU
Динамичко програмирање

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

Проблемот со завиткување на зборовите наведува дека со оглед на низа зборови како влез, треба да најдеме број на зборови што можат да се вметнат во една линија истовремено. Значи, за да го направите ова, ставаме паузи во дадената низа, така што печатениот документ изгледа убаво. Уредувачи на зборови, како што се Microsoft Office, Libre Office и други алатки за документи, користат паузи за редови за да изгледа документот убаво. Тука, под убаво, мислиме дека ги поставуваме просторите на рамномерно распространет начин. Не треба да има линии со многу дополнителни простори и некои со мали количини.

Тука, исто така, претпоставуваме дека нашата должина на зборот не ја надминува големината на линијата. Само за да ги направиме работите малку поопшти, ние ја разгледуваме функцијата const во прашањето како (Број на дополнителен простор) ^ 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

 

Само за едноставно разбирање, ние ги покажавме влезовите како зборови наместо големината на зборот.

Објаснување: мачката е_

                        an____

                        животните

Тука, има 4 дополнителни празни места на втората линија и 1 на третата линија.

Пресметка: 4 ^ 3 + 1 ^ 3 = 65

 

Постои подобро решение,

мачка___

е_

животните

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

Сега, ќе го решиме проблемот со завиткување на зборови користејќи Динамичко програмирање. Знаеме дека на нашиот проблем му треба глобално оптимално решение и претходниот алгоритам се обидуваше да ни даде локален оптимум како резултат. Овде ќе го најдеме дополнителниот простор зафатен во секоја линија, и со тоа ќе ги најдеме трошоците за секој ред, соодветно. Willе одржиме матрица екстра простор што ќе му каже на дополнителниот простор оставен во една линија, зборовите од i до j се прикачени на една линија. Потоа, понатаму ќе ја користиме оваа екстра-простор матрица за да ја пронајдеме минималната цена.

Код

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

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

Временска комплексност: О (n ^ 2)

Тука, бидејќи нашата надворешна јамка тече од 1 до n и нашата внатрешна јамка се протега од 1 до i, имаме полиномна временска сложеност на O (n ^ 2).

Комплексноста на вселената: О (n ^ 2)

Еве, нашата низа екстрапростор е низа 2D која е со големина N * N, што ни дава полиномна вселенска сложеност на O (N ^ 2).