مشكلة التفاف الكلمات


مستوى الصعوبة الثابت
كثيرا ما يطلب في Arcesium مجموعة الحقائق رمادي Microsoft Myntra علا سيارة أجرة PayU
البرمجة الديناميكية

المشكلة بيان

تنص مشكلة التفاف الكلمات على أنه بالنظر إلى تسلسل الكلمات كمدخلات ، نحتاج إلى إيجاد عدد الكلمات التي يمكن تركيبها في سطر واحد في كل مرة. لذلك ، للقيام بذلك ، نضع فواصل في التسلسل المحدد بحيث يبدو المستند المطبوع جيدًا. تستخدم برامج تحرير الكلمات مثل Microsoft Office و Libre Office وأدوات المستندات الأخرى فواصل الأسطر لجعل المستند يبدو جميلًا. هنا ، نعني باللطف أننا نضع المساحات بطريقة موزعة بالتساوي. يجب ألا تكون هناك خطوط بها العديد من المساحات الإضافية وبعضها بكميات صغيرة.

هنا ، نفترض أيضًا أن طول كلمتنا لا يتجاوز حجم الخط. فقط لجعل الأشياء أكثر عمومية ، فإننا نفكر في وظيفة ثابتة في السؤال كـ (عدد المساحة الإضافية) ^ 3 ، وإلا لكان الأمر سهلاً للغاية. قد تختلف وظيفة التكلفة هذه حسب السؤال المطروح.

نهج Word Wrap Dp

مثال

هنا ، سوف نقدم عدد الكلمات وحجم الكلمة وحجم الخط كمدخلات.

number of words = 4

wordSize = { 3, 2, 2, 5}

lineSize = 6
28

شرح: يمكننا وضع الكلمة الأولى في السطر الأول مع 1 مسافات إضافية ، والكلمة الثانية والثالثة في السطر الثاني بمسافة إضافية ، والكلمة الأخيرة في السطر الثالث بدون مسافة إضافية (لن نأخذ في الاعتبار المسافات بعد الكلمة الأخيرة كمسافات إضافية). وبالتالي ، باستخدام دالة التكلفة الخاصة بنا ، نجد التكلفة 1.

number of words = 3

wordSize = { 1, 1, 1}

lineSize = 10
00

التفسير: هنا يمكننا وضع كل الكلمات على نفس السطر مثل السطر الأول وبالتالي التكلفة = 1.

 

نهج لمشكلة التفاف الكلمات

النهج الأول الذي يتبادر إلى الذهن هو الحل الجشع حيث نواصل ببساطة وضع الكلمات في سطر واحد. عندما لا نستطيع وضع كلمة في نفس السطر ، ننتقل إلى السطر الثاني. يبدو أن هذا يعمل بشكل جيد ، ولكن هناك مشكلة. لن تنتج هذه الخوارزمية النتيجة المثلى لأنه قد تكون هناك حالات مثل أنه إذا قمنا بتغيير المساحات الإضافية ، فقد ينتهي بنا الأمر بحل عالمي أفضل.

الإخراج باستخدام النهج الجشع

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

 

فقط من أجل الفهم البسيط ، أظهرنا الإدخال ككلمات بدلاً من حجم الكلمات.

التفسير: القط is_

                        و _____

                        حيوان

هنا ، توجد 4 مسافات إضافية في السطر الثاني و 1 في السطر الثالث.

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

 

يوجد حل أفضل ،

قط___

هو

حيوان

يعطينا التكلفة الإجمالية 28 (3 ^ 3 + 1 ^ 3 + 0 ^ 3) ، وهو أفضل من 65.

الآن ، سنحل مشكلة التفاف الكلمات باستخدام البرمجة الديناميكية. نحن نعلم أن مشكلتنا تحتاج إلى حل عالمي أمثل وأن خوارزميةنا السابقة كانت تحاول أن تقدم لنا أفضل حل محلي نتيجة لذلك. هنا سنجد المساحة الإضافية المأخوذة في كل سطر ، وبالتالي سنجد تكلفة كل صف على التوالي. سنحتفظ بمصفوفة 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

كود جافا لمشكلة التفاف النص

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 (ن ^ 2)

هنا ، نظرًا لأن الحلقة الخارجية الخاصة بنا تمتد من 1 إلى n وأن الحلقة الداخلية لدينا تمتد من 1 إلى i ، فلدينا تعقيد زمني متعدد الحدود لـ O (n ^ 2).

تعقيد الفضاء: O (n ^ 2)

هنا ، صفيفنا extraSpace عبارة عن مصفوفة ثنائية الأبعاد بحجم N * N ، مما يعطينا تعقيد مساحة متعدد الحدود لـ O (N ^ 2).