لفظ لفافي جو مسئلو


تڪليف جي سطح سخت
بار بار پڇڻ ۾ آرڪسيميم حقيقت جو جائزو گرين اورنج Microsoft جي Myntra اولا ڪئابس پي يو يو
متحرڪ پروگرامنگ

مسئلي جو بيان

لفظ لفافي جو مسئلو ٻڌائي ٿو ته لفظن جي تسلسل کي انپٽ جي طور تي ، اسان کي انهن لفظن جو تعداد ڳولڻ جي ضرورت آهي جيڪي هڪ وقت ۾ هڪ ئي قطار ۾ سمائجي سگهن. پوءِ ، هي ڪرڻ لاءِ اسان ڏنل ڏنل تسلسل ۾ وقفو رکون ٿا جئين ڇپيل دستاويز سٺو لڳن. لفظ ايڊيٽرن جهڙوڪ مائڪروسوفٽ آفيس ، لائبر آفيس ۽ ٻيا دستاويزي اوزار دستاويز کي سٺو بڻائڻ لاءِ لڪيرين استعمال ڪندا آهن. هتي ، سٺي طور تي اسان جو مطلب اهو آهي ته اسان هنڌن کي هڪ جيتري spreadهليل انداز ۾ رکون ٿا. اتي ڪيترن ئي اضافي جڳهن ۽ ڪجهه نن smallن مقدار سان قطارون نه هجڻ گهرجن.

هتي ، اسان اهو به فرض ڪريون ٿا ته اسان جي لفظ جي ڊيگهه لڪير جي ماپ کان وڌيڪ نه آهي. رڳو شين کي ٿورو وڌيڪ عام ڪرڻ لاءِ ، اسان سوال ۾ هڪ ڪن فنڪشن تي غور ڪري رهيا آهيون جيئن ته (اضافي جڳهه جو نمبر) ^ 3 ، ٻي صورت ۾ اهو ڪافي آسان ٿي وڃي ها. قيمت جي لحاظ کان پڇيل سوال جي مطابق مختلف ٿي سگهن ٿا.

لفظ لفاف ڊي پي جو رستو

مثال

هتي ، اسان لفظ نمبر ، لفظي سائيز ، ۽ ان لائن جي طور تي لائن جي شڪل فراهم ڪنداسين.

number of words = 4

wordSize = { 3, 2, 2, 5}

lineSize = 6
28

وضاحت: اسان 1 لفظ کي پهرين جڳهه تي 1 اضافي جڳهه سان گڏ ڪري سگهو ٿا ، 3 لفظ ۽ ٽيون لفظ 2 قطار تي 3 اضافي جڳهه سان ، ۽ آخري لفظ 2 ليڪ تي اضافي جڳهه سان گڏ (اسان آخري لفظ کان پوءِ جي جڳهن تي غور نه ڪندا سين) اضافي جڳهن جي طور تي). اهڙي طرح ، اسان جي قيمت جي فنڪشن کي استعمال ڪندي اسين قيمت طور حاصل ڪندا آهيون 1.

number of words = 3

wordSize = { 1, 1, 1}

lineSize = 10
00

وضاحت: هتي اسان سڀني لفظن کي هڪ ئي لڪير تي رکي سگهون ٿا يعني پهرين لڪير ۽ اهڙيءَ ريت قيمت = 1.

 

لفظ وارڊنگ مسئلي لاءِ نقطه نظر

پهرين طريقي سان جيڪو ذهن ۾ اچي ٿو اهو هڪ لالچ حل آهي جتي اسان لفظن کي هڪٻئي ۾ رکڻ ۾ رُڌل آهيون. جڏهن اسان هڪ لفظ کي ساڳي لڪير تي رکي نٿا سگهون ، اسين ٻئي لڪير تي منتقل ڪريون ٿا. اهو ڪم سٺو لڳي ٿو ، پر هتي هڪ پڪ آهي. هي الگورٿٿم سٺا نتيجا نٿي پيدا ڪندو ڇو ته اهڙا ڪيس هوندا ته جيڪڏهن اسان اضافي جڳيون تبديل ڪيون ته بهتر عالمي حل سان ختم ٿي سگهون.

لالچي طريقي سان استعمال ڪندي ٻا

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

 

صرف سادي سمجھڻ جي لاءِ ، اسان لفظ لفظ جي بدران انپٽ کي لفظن طور ڏيکاريو آهي.

وضاحت: ٻلي آهي_

                        هڪ ____

                        حيوان

هتي ، سيڪنڊ تي 4 اضافي جڳهه ۽ ٽئين لائن تي 1 آهن.

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

 

هتي بهتر حل آهي ،

ٻلي

آهي هڪ_

حيوان

اسان کي 28 جي مجموعي قيمت ڏيو (3 ^ 3 + 1 ^ 3 + 0 ^ 3) ، جيڪو 65 کان بهتر آهي.

هاڻي ، اسان استعمال ڪندي لفظ ويڙھڻ جو مسئلو حل ڪنداسين متحرڪ پروگرامنگ. اسان thatاڻون ٿا ته اسان جو مسئلو عالمي بھترين حل جي ضرورت آھي ۽ اسان جو اڳوڻو الگورٿم ڪوشش ڪندو ھو ته اسان کي نتيجي ۾ ، لوڪل بھترائي ڏيو. هتي اسين هر قطار ۾ اضافي جڳهه ڳولينداسين ، ۽ اهڙي ريت هر قطار ۾ لاڳت سان ترتيب ڏينداسين. اسان ميٽرڪس اضافي اسپيس کي برقرار رکون ٿا جيڪو اضافي اسپيس کي هڪ لڪير ۾ ٻڌائي سگهندو ، لفظن مان i کان ج تائين هڪ ئي قطار تي لڳل آهن. ان کان پوءِ گهٽ ۾ گهٽ قيمت ڳولڻ لاءِ اسين انهي اضافي اسپيس ميٽرڪس کي استعمال ڪنداسين.

ڪوڊ

لفظ لپڻ واري مسئلي لاءِ سي ++ ڪوڊ

#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

پيچيدگي تجزيي

وقت جي پيچيدگي: اي (ن ^ 2)

هتي ، ڇو ته اسان جو ٻاهرين لوپ 1 کان ن تائين هلندو آهي ۽ اسان جو اندروني لوپ 1 کان ن تائين هلندو آهي ، اسان کي O (n ^ 2) جي پولينوميل ٽائيم پيچيدگي آهي

خلائي پيچيدگي: او (n ^ 2)

هتي ، اسان جي اضافي اسپيس صف 2D صف آهي جيڪا N * N جي سائيز آهي ، جيڪا اسان کي O (N ^ 2) جي پولينومائل خلائي پيچيدگي ڏي ٿي.