Bài Toán Ngắt Dòng Văn Bản (Word Wrap Problem)

Giới thiệu

Cho dãy độ dài các từ và độ rộng dòng tối đa. Xác định cách ngắt dòng sao cho các dòng cân bằng (tối thiểu hóa tổng bình phương khoảng trống thừa).

Đầu vào và Đầu ra

Đầu vào: Độ dài từ {3, 2, 2, 5}, độ rộng tối đa = 6
Đầu ra:
Dòng 1: Từ 1 đến 1
Dòng 2: Từ 2 đến 3
Dòng 3: Từ 4 đến 4

Thuật toán Quy hoạch động

Tính ma trận extraSpace[i][j] = khoảng trống thừa khi đặt từ i đến j trên một dòng. Tính lineCost[i][j] = bình phương khoảng trống (hoặc ∞ nếu âm, 0 nếu là dòng cuối). Tìm totalCost[j] = chi phí tối thiểu cho j từ đầu tiên, và solution[j] = từ bắt đầu của dòng cuối.

wordWrap(wordLenArr, size, maxWidth)
Begin
    extraSpace, lineCost [size+1][size+1]
    totalCost, solution [size+1]
    for i=1 to size: extraSpace[i][i] = maxWidth - wordLenArr[i-1]
        for j=i+1 to size: extraSpace[i][j] = extraSpace[i][j-1] - wordLenArr[j-1] - 1
    for i=1 to size:
        for j=i to size:
            if extraSpace[i][j] < 0: lineCost = ∞
            else if j==size and extraSpace>=0: lineCost = 0
            else lineCost = extraSpace^2
    totalCost[0]=0
    for j=1 to size:
        totalCost[j] = ∞
        for i=1 to j:
            if totalCost[i-1]!=∞ and lineCost[i][j]!=∞ and totalCost[i-1]+lineCost[i][j] < totalCost[j]:
                totalCost[j] = totalCost[i-1] + lineCost[i][j]
                solution[j] = i
    hiển thị solution
End

Ví dụ C++

#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++) {
        extraSpace[i][i] = maxWidth - wordLenArr[i-1];
        for(int j=i+1; j<=size; j++)
            extraSpace[i][j] = extraSpace[i][j-1] - wordLenArr[j-1] - 1;
    }
    for(int i=1; i<=size; i++) {
        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++) {
        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);
}

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

Kết quả

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