Масъалаи печонидани калима


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Артезий 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 пайдо мекунем.

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-ро нигоҳ медорем, ки он Extra-ро дар сатр боқӣ мегузорад, калимаҳои аз 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 мо массиви 2D мебошад, ки андозаи N * N мебошад, ки ба мо мураккабии фазои полиномии O (N ^ 2) -ро медиҳад.