শব্দ মোড়ানো সমস্যা

শব্দের একটি ক্রম দেওয়া হয়েছে, প্রতিটি লাইনের জন্য অক্ষরের সংখ্যার একটি সীমা রয়েছে৷ লাইন ব্রেক করার মাধ্যমে, এমনভাবে যাতে লাইনগুলি পরিষ্কারভাবে মুদ্রিত হয়।

লাইনগুলিকে অবশ্যই ভারসাম্যপূর্ণ হতে হবে, যখন কিছু লাইনে প্রচুর অতিরিক্ত স্পেস থাকে এবং কিছু লাইনে অল্প সংখ্যক অতিরিক্ত স্পেস থাকে, এটি তাদের আলাদা লাইনে ভারসাম্য বজায় রাখবে। এটি তাদের ভারসাম্যপূর্ণ করতে একই সংখ্যক অতিরিক্ত স্পেস ব্যবহার করার চেষ্টা করে৷

এই অ্যালগরিদমটি এক লাইনে কতগুলি শব্দ স্থাপন করা যেতে পারে এবং কতগুলি লাইন প্রয়োজন তা তৈরি করবে৷

ইনপুট এবং আউটপুট

Input:
The length of words for each line. {3, 2, 2, 5}. The max width is 6.
Output:
Line number 1: Word Number: 1 to 1 (only one word)
Line number 2: Word Number: 2 to 3 (Second and 3rd word)
Line number 3: Word Number: 4 to 4 (4th word)

অ্যালগরিদম

wordWrap(wordLenArr, size, maxWidth)

ইনপুট - শব্দের দৈর্ঘ্য অ্যারে, অ্যারের আকার এবং শব্দের সর্বাধিক প্রস্থ।

আউটপুট - প্রতি লাইনে কতগুলো শব্দ বসবে তার তালিকা।

Begin
   define two square matrix extraSpace and lineCost of order (size + 1)
   define two array totalCost and solution of size (size + 1)

   for i := 1 to size, do
      extraSpace[i, i] := maxWidth – wordLenArr[i - 1]
      for j := i+1 to size, do
         extraSpace[i, j] := extraSpace[i, j-1] – wordLenArr[j - 1] - 1
      done
   done

   for i := 1 to size, do
      for j := i+1 to size, do
         if extraSpace[i, j] < 0, then
            lineCost[i, j] = ∞
         else if j = size and extraSpace[i, j] >= 0, then
            lineCost[i, j] := 0
         else
            linCost[i, j] := extraSpace[i, j]^2
      done
   done

   totalCost[0] := 0
   for j := 1 to size, do
      totalCost[j] := ∞
      for i := 1 to j, do
         if totalCost[i-1] ≠∞ and linCost[i, j] ≠ ∞ and
            (totalCost[i-1] + lineCost[i,j] < totalCost[j]), then
            totalCost[i – 1] := totalCost[i – 1] + lineCost[i, j]
            solution[j] := i
      done
   done
   display the solution matrix
End

উদাহরণ

#include<iostream>
using namespace std;

int dispSolution (int solution[], int size) {
   int k;
   if (solution[size] == 1)
      k = 1;
   else
      k = dispSolution (solution, solution[size]-1) + 1;
   cout << "Line number "<< k << ": Word Number: " <<solution[size]<<" to "<< size << endl;
   return k;
}

void wordWrap(int wordLenArr[], int size, int maxWidth) {
   int extraSpace[size+1][size+1];
   int lineCost[size+1][size+1];
   int totalCost[size+1];
   int solution[size+1];

   for(int i = 1; i<=size; i++) {    //find extra space for all lines
      extraSpace[i][i] = maxWidth - wordLenArr[i-1];

      for(int j = i+1; j<=size; j++) {    //extra space when word i to j are in single line
         extraSpace[i][j] = extraSpace[i][j-1] - wordLenArr[j-1] - 1;
      }
   }

   for (int i = 1; i <= size; i++) {    //find line cost for previously created extra spaces array

      for (int j = i; j <= size; j++) {

         if (extraSpace[i][j] < 0)
            lineCost[i][j] = INT_MAX;
         else if (j == size && extraSpace[i][j] >= 0)
            lineCost[i][j] = 0;
         else
            lineCost[i][j] = extraSpace[i][j]*extraSpace[i][j];
      }
   }

   totalCost[0] = 0;
   for (int j = 1; j <= size; j++) {    //find minimum cost for words
      totalCost[j] = INT_MAX;

      for (int i = 1; i <= j; i++) {
         if (totalCost[i-1] != INT_MAX && lineCost[i][j] != INT_MAX && (totalCost[i-1] + lineCost[i][j] < totalCost[j])){
            totalCost[j] = totalCost[i-1] + lineCost[i][j];
            solution[j] = i;
         }
      }
   }

   dispSolution(solution, size);
}

main() {
   int wordLenArr[] = {3, 2, 2, 5};
   int n = 4;
   int maxWidth = 6;
   wordWrap (wordLenArr, n, maxWidth);
}

আউটপুট

Line number 1: Word Number: 1 to 1
Line number 2: Word Number: 2 to 3
Line number 3: Word Number: 4 to 4