ورڈ لپیٹنا مسئلہ


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے آرسیسیئم حقیقت گرین اورنج مائیکروسافٹ Myntra اولا کیبس پی پی یو
متحرک پروگرامنگ

مسئلہ یہ بیان

لفظ لپیٹنا مسئلہ بیان کرتا ہے کہ الفاظ کی ترتیب کو ان پٹ کی حیثیت سے ، ہمیں الفاظ کی تعداد ڈھونڈنے کی ضرورت ہے جو ایک وقت میں ایک ہی لائن میں فٹ ہوسکتے ہیں۔ لہذا ، ایسا کرنے کے ل we ہم نے اس ترتیب میں وقفے ڈال دیئے کہ طباعت شدہ دستاویز اچھی لگ رہی ہے۔ مائیکروسافٹ آفس ، لِبر آفس اور دستاویز کے دوسرے اوزار جیسے لفظ ایڈیٹرز دستاویز کو اچھ lookا لگانے کے ل break لائن بریک کا استعمال کرتے ہیں۔ یہاں ، اچھی طرح سے ہمارا مطلب ہے کہ ہم خالی جگہوں کو یکساں طور پر پھیلتے ہوئے انداز میں رکھتے ہیں۔ بہت ساری اضافی جگہوں والی لائنیں نہیں ہونی چاہئیں اور کچھ تھوڑی مقدار میں۔

یہاں ، ہم یہ بھی فرض کرتے ہیں کہ ہمارے لفظ کی لمبائی لائن سائز سے زیادہ نہیں ہے۔ چیزوں کو تھوڑا سا زیادہ عام بنانے کے ل we ہم سوال میں ایک مستعدی فعل پر غور کر رہے ہیں (اضافی جگہ کی تعداد) ^ 3 ، بصورت دیگر یہ بھی آسان ہوتا۔ پوچھے گئے سوال کے مطابق لاگت کا یہ کام مختلف ہوسکتا ہے۔

ورڈ لپیٹ Dp نقطہ نظر

مثال کے طور پر

یہاں ، ہم ان پٹ کے بطور الفاظ کی تعداد ، الفاظ کے سائز اور لائن سائز فراہم کریں گے۔

number of words = 4

wordSize = { 3, 2, 2, 5}

lineSize = 6
28

وضاحت: ہم پہلا لفظ 1st اضافی جگہ کے ساتھ پہلی سطر پر ، دوسرا اور تیسرا لفظ دوسری لائن پر extra اضافی جگہ کے ساتھ ، اور آخری لفظ بغیر کسی اضافی جگہ کے تیسری لائن پر رکھ سکتے ہیں (ہم آخری لفظ کے بعد خالی جگہوں پر غور نہیں کریں گے) اضافی خالی جگہوں کے طور پر)۔ اس طرح ، ہم اپنی لاگت کی تقریب کا استعمال کرتے ہوئے قیمت 1 کے طور پر تلاش کرتے ہیں۔

number of words = 3

wordSize = { 1, 1, 1}

lineSize = 10
00

وضاحت: یہاں ہم تمام الفاظ ایک ہی لائن پر رکھ سکتے ہیں یعنی پہلی لائن اور اس طرح لاگت = 1۔

 

لفظ لپیٹنے کی دشواری کے ل Appro نقطہ نظر

پہلا نقطہ نظر جو ذہن میں آتا ہے وہ ایک لالچی حل ہے جہاں ہم الفاظ کو صرف ایک ہی لائن میں ڈالتے رہتے ہیں۔ جب ہم ایک ہی لائن پر کوئی لفظ نہیں رکھ سکتے تو ہم دوسری لائن میں چلے جاتے ہیں۔ ایسا لگتا ہے کہ یہ ٹھیک کام کرتا ہے ، لیکن ایک کیچ ہے۔ اس الگورتھم سے زیادہ سے زیادہ نتیجہ برآمد نہیں ہوگا کیونکہ ایسے معاملات بھی ہوسکتے ہیں اگر ہم اضافی جگہوں کو تبدیل کردیں تو ہم بہتر عالمی حل کے ساتھ ختم ہوجائیں گے۔

لالچی نقطہ نظر کا استعمال کرتے ہوئے آؤٹ پٹ

”cat is an animal”, line size = 6
65

 

صرف عام تفہیم کے ل we ، ہم ان پٹ کو ورڈ سیز کی بجائے الفاظ کے بطور دکھائے ہیں۔

وضاحت: بلی ہے_

                        ایک____

                        جانور

یہاں ، دوسری لائن پر 4 اور تیسری لائن پر 1 اضافی جگہیں ہیں۔

حساب کتاب: 4 ^ 3 + 1 ^ 3 = 65

 

ایک بہتر حل موجود ہے ،

کیٹ___

ایک_

جانور

ہمیں کل لاگت 28 (3 ^ 3 + 1 ^ 3 + 0 ^ 3) دینا جو 65 سے بہتر ہے۔

اب ، ہم لفظ لفافی مسئلہ کو استعمال کرکے حل کریں گے متحرک پروگرامنگ. ہم جانتے ہیں کہ ہمارے مسئلے کو عالمی سطح پر زیادہ سے زیادہ حل کی ضرورت ہے اور ہمارا سابقہ ​​الگورتھم اس کے نتیجے میں ہمیں مقامی زیادہ سے زیادہ درجہ دینے کی کوشش کر رہا تھا۔ یہاں ہمیں ہر سطر میں لی گئی اضافی جگہ مل جائے گی ، اور اس طرح ہر صف کی قیمت بالترتیب مل جائے گی۔ ہم ایک میٹرکس ایکسٹرا اسپیس کو برقرار رکھیں گے جو ایک لائن میں رہ گئے ایکسٹرا اسپیس کو بتائے گا ، I سے j تک کے الفاظ ایک ہی لائن پر رکھے گئے ہیں۔ پھر مزید کم سے کم لاگت تلاش کرنے کے ل this ہم اس اسپیس اسپیس میٹرکس کا استعمال کریں گے۔

ضابطے

لفظ لپیٹنے میں دشواری کا 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) کی کثیر الوقت پیچیدگی ہے۔

خلائی پیچیدگی: O (n ^ 2)

یہاں ، ہماری ایکسٹرا اسپیس سرنی 2D سرنی ہے جو سائز N * N کی ہے ، جو ہمیں O (N ^ 2) کی کثیر الخلاقی پیچیدگی فراہم کرتی ہے۔