ปัญหาการตัดคำ

ให้ลำดับของคำ มีการจำกัดจำนวนอักขระสำหรับแต่ละบรรทัด โดยใส่ตัวแบ่งบรรทัดเพื่อให้พิมพ์บรรทัดได้ชัดเจน

เส้นต้องสมดุลกัน เมื่อบางบรรทัดมีช่องว่างพิเศษจำนวนมาก และบางบรรทัดมีการเว้นวรรคจำนวนน้อย มันจะสร้างสมดุลให้บรรทัดที่แยกจากกัน มันพยายามใช้ช่องว่างเพิ่มเติมจำนวนเท่ากันเพื่อให้สมดุล

อัลกอริธึมนี้จะกำหนดจำนวนคำที่สามารถวางในหนึ่งบรรทัด และจำนวนบรรทัดที่ต้องการ

อินพุตและเอาต์พุต

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