مشکل بسته بندی کلمات


سطح دشواری سخت
اغلب در ارسیسیوم واقعیت خاکستری نارنجی مایکروسافت میندا کابین های اولا PayU
برنامه نویسی پویا

بیان مسأله

کلمه wrap problem بیان می کند که با توجه به دنباله ای از کلمات به عنوان ورودی ، ما باید تعداد کلماتی را که می توان همزمان در یک خط قرار گیرد پیدا کنیم. بنابراین ، برای انجام این کار ، توالی داده شده را وقفه هایی قرار می دهیم تا سند چاپ شده زیبا به نظر برسد. ویرایشگرهای کلمه مانند Microsoft Office ، Libre Office و سایر ابزارهای اسناد از خطوط شکسته استفاده می کنند تا سند زیبا به نظر برسد. در اینجا ، منظور ما از خوب این است که ما فضاها را به صورت یکنواخت پخش می کنیم. نباید خطوطی با فضای اضافی زیاد و برخی با مقادیر کم وجود داشته باشد.

در اینجا ، ما همچنین فرض می کنیم که طول کلمه ما از اندازه خط فراتر نرود. برای اینکه کمی عمومی تر شود ، ما در سوال یک تابع const را به عنوان (تعداد فضای اضافی) ^ 3 در نظر می گیریم ، در غیر اینصورت خیلی آسان بود. این تابع هزینه ممکن است متناسب با س askedال مطرح شده متفاوت باشد.

رویکرد Dp Word Wrap

مثال

در اینجا ، ما تعداد کلمات ، اندازه کلمه و اندازه خط را به عنوان ورودی ارائه خواهیم داد.

number of words = 4

wordSize = { 3, 2, 2, 5}

lineSize = 6
28

توضیح: ما می توانیم کلمه 1 را با 1 فضای اضافی ، کلمه 3 و 2 را در خط 3 با 2 فضای اضافی ، و کلمه آخر را در خط 1 بدون فضای اضافی قرار دهیم (فضاهای بعد از کلمه آخر را در نظر نخواهیم گرفت به عنوان فضاهای اضافی) بنابراین ، با استفاده از تابع هزینه ما ، هزینه 3 را پیدا می کنیم.

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 است.

اکنون ، ما با استفاده از کلمه wrap problem را حل خواهیم کرد برنامه نویسی پویا. ما می دانیم که مشکل ما به یک راه حل بهینه جهانی نیاز دارد و در نتیجه الگوریتم قبلی ما سعی در بهینه سازی محلی داشت. در اینجا فضای اضافی گرفته شده در هر خط را پیدا خواهیم کرد ، بنابراین به ترتیب هزینه هر سطر را پیدا خواهیم کرد. ما یک فضای اضافی ماتریسی را حفظ خواهیم کرد که به فضای اضافی باقی مانده در یک خط گفته می شود ، کلمات i تا j روی یک خط قرار می گیرند. سپس بیشتر ما از این ماتریس فضای اضافی برای یافتن حداقل هزینه استفاده خواهیم کرد.

رمز

کد 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)

در اینجا ، آرایه extraSpace ما یک آرایه 2D است که به اندازه N * N است ، که به ما پیچیدگی فضای چند جمله ای O (N ^ 2) را می دهد.