Сөздерді орау проблемасы


Күрделілік дәрежесі қиын
Жиі кіреді Арцезий Деректер жинағы Сұр Оранж Microsoft Минтра 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.

 

Сөздерді орау проблемасына көзқарас

Ойлайтын бірінші тәсіл - біз сөздерді бір жолға орналастыруды жалғастыратын ашкөздік шешім. Бір жолға сөз орналастыра алмаған кезде, екінші жолға көшеміз. Бұл өте жақсы жұмыс істейтін сияқты, бірақ бар. Бұл алгоритм оңтайлы нәтиже бермейді, өйткені егер біз қосымша кеңістікті өзгертсек, жаһандық шешімге келуіміз мүмкін.

Ашкөздік тәсілін қолдану арқылы шығару

”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) полиномдық уақыт күрделілігі бар.

Ғарыштың күрделілігі: O (n ^ 2)

Мұнда біздің ExtraSpace массивіміз N * N өлшемді 2D жиымы болып табылады, бұл бізге O (N ^ 2) полиномдық кеңістіктің күрделілігін береді.