სიტყვათა გადაჭრის პრობლემა  


Რთული ტური Hard
ხშირად ეკითხებიან არსიუმი ფაქტები რუხი ნარინჯისფერი microsoft მიტრა ოლა კაბინები პეუ
დინამიური პროგრამირება

პრობლემის განცხადება  

სიტყვის გადახვევის პრობლემა აცხადებს, რომ სიტყვების თანმიმდევრობის გათვალისწინებით, ჩვენ უნდა ვიპოვოთ იმ სიტყვების რაოდენობა, რომლებიც ერთდროულად შეიძლება ერთ სტრიქონში მოთავსდეს. ასე რომ, ამისათვის ჩვენ მოცემულ თანმიმდევრობაში ვუშვებთ შესვენებებს ისე, რომ დაბეჭდილი დოკუმენტი ლამაზად გამოიყურება. სიტყვის რედაქტორები, როგორიცაა Microsoft Office, Libre Office და სხვა დოკუმენტის ხელსაწყოები, იყენებენ ხაზების წყვეტებს, რომ დოკუმენტი ლამაზად გამოიყურებოდეს. აქ, ლამაზად ვგულისხმობთ იმას, რომ ჩვენ ვათავსებთ სივრცეებს ​​თანაბრად განაწილებული წესით. არ უნდა არსებობდეს ხაზები, რომელსაც აქვს ბევრი დამატებითი სივრცე და ზოგიც მცირე რაოდენობით.

აქ ჩვენ ასევე ჩავთვლით, რომ ჩვენი სიტყვის სიგრძე არ აღემატება სტრიქონის ზომას. ცოტა უფრო ზოგადი რომ გახდეს, ჩვენ განვიხილავთ შეკრების ფუნქციას კითხვაში, როგორც (დამატებითი ადგილის რაოდენობა) ^ 3, სხვა შემთხვევაში ეს ძალიან მარტივი იქნებოდა. ხარჯების ეს ფუნქცია შეიძლება განსხვავდებოდეს დასმული შეკითხვის მიხედვით.

Word Wrap მიდგომაPin

მაგალითი  

აქ შეყვანის სახით მოგაწვდით სიტყვების რაოდენობას, სიტყვის ზომას და სტრიქონის ზომას.

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-ს ჯობია.

ახლა, ჩვენ გადავჭრით სიტყვის გადახვევის პრობლემას დინამიური პროგრამირება. ჩვენ ვიცით, რომ ჩვენს პრობლემას გლობალური ოპტიმალური გადაწყვეტა სჭირდება და ჩვენი წინა ალგორითმი ცდილობდა ადგილობრივი ოპტიმი მოგვცა. აქ ჩვენ ნახავთ თითოეულ სტრიქონში აღებულ დამატებით ადგილს და შესაბამისად ვიხილავთ ღირებულებას თითოეული სტრიქონისთვის. ჩვენ შევინარჩუნებთ მატრიცას ექსტრასივრცას, რომელიც გვეუბნება სტრიქონში დატოვებულ ექსტრასივრცას, სიტყვები 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

ჯავა კოდი სიტყვათა შესაფერის პრობლემასთან დაკავშირებით

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).

იხილეთ ასევე
დაითვალეთ მეცხრე კიბეზე ასასვლელი გზები 1, 2 ან 3 ნაბიჯის გამოყენებით

სივრცის სირთულე: O (n ^ 2)

აქ, ჩვენი ექსტრასივრცეული მასივი არის 2D მასივი, რომლის ზომაა N * N, რაც გვაძლევს პოლინომური სივრცის O (N ^ 2) სირთულეს.