Πρόβλημα αναδίπλωσης λέξεων


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις Αρσεσίου Γεγονότα 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η λέξη στη 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.

Επεξήγηση: cat is_

                        ένα____

                        ζώο

Εδώ, υπάρχουν 4 επιπλέον διαστήματα στη δεύτερη γραμμή και 1 στην τρίτη γραμμή.

Υπολογισμός: 4 ^ 3 + 1 ^ 3 = 65

 

Υπάρχει μια καλύτερη λύση,

Γάτα___

είναι ένα_

ζώο

Δώστε μας συνολικό κόστος 28 (3 ^ 3 + 1 ^ 3 + 0 ^ 3), το οποίο είναι καλύτερο από 65.

Τώρα, θα λύσουμε το πρόβλημα με τη λέξη wrap Δυναμικός προγραμματισμός. Γνωρίζουμε ότι το πρόβλημά μας χρειάζεται μια παγκόσμια βέλτιστη λύση και ο προηγούμενος αλγόριθμός μας προσπαθούσε να μας δώσει το τοπικό βέλτιστο ως αποτέλεσμα. Εδώ θα βρούμε τον επιπλέον χώρο που λαμβάνεται σε κάθε γραμμή, και έτσι θα βρούμε το κόστος για κάθε σειρά αντίστοιχα. Θα διατηρήσουμε μια μήτρα 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 είναι ένας 2D πίνακας μεγέθους N * N, ο οποίος μας δίνει πολυωνυμική πολυπλοκότητα χώρου O (N ^ 2)