वर्ड रैप समस्या

शब्दों का एक अनुक्रम दिया गया है, प्रत्येक पंक्ति के लिए कैरेक्टर्स की संख्या पर एक सीमा है। लाइन ब्रेक लगाकर, इस तरह से कि पंक्तियां स्पष्ट रूप से प्रिंट हों।

पंक्तियां संतुलित होनी चाहिए, जब कुछ पंक्तियों में बहुत अधिक अतिरिक्त स्पेस हों और कुछ पंक्तियों में कम अतिरिक्त स्पेस हों, तो यह उन्हें अलग-अलग पंक्तियों में संतुलित करेगा। यह उन्हें संतुलित बनाने के लिए समान संख्या में अतिरिक्त स्पेस का उपयोग करने का प्रयास करता है।

यह एल्गोरिदम उत्पन्न करेगा कि एक पंक्ति में कितने शब्द रखे जा सकते हैं, और कितनी पंक्तियों की आवश्यकता है।

इनपुट और आउटपुट

इनपुट: प्रत्येक पंक्ति के लिए शब्दों की लंबाई {3, 2, 2, 5}। अधिकतम चौड़ाई 6 है।
आउटपुट:
लाइन नंबर 1: वर्ड नंबर: 1 से 1 (केवल एक शब्द)
लाइन नंबर 2: वर्ड नंबर: 2 से 3 (दूसरा और तीसरा शब्द)
लाइन नंबर 3: वर्ड नंबर: 4 से 4 (चौथा शब्द)

एल्गोरिदम

wordWrap(wordLenArr, size, maxWidth)

इनपुट: शब्द लंबाई ऐरे, ऐरे का आकार और शब्द की अधिकतम चौड़ाई
आउटपुट: प्रति पंक्ति कितने शब्द रखे जाएंगे, इसकी सूची

शुरुआत
    (size + 1) ऑर्डर के दो वर्ग मैट्रिक्स extraSpace और lineCost परिभाषित करें
    (size + 1) आकार के दो ऐरे totalCost और solution परिभाषित करें
    i := 1 से size तक, करें
        extraSpace[i, i] := maxWidth - wordLenArr[i - 1]
        j := i+1 से size तक, करें
            extraSpace[i, j] := extraSpace[i, j-1] - wordLenArr[j - 1] - 1
        पूर्ण
    पूर्ण
    i := 1 से size तक, करें
        j := i+1 से size तक, करें
            यदि extraSpace[i, j] < 0, तो
                lineCost[i, j] = ∞
            अन्यथा यदि j = size और extraSpace[i, j] >= 0, तो
                lineCost[i, j] := 0
            अन्यथा
                lineCost[i, j] := extraSpace[i, j]²
        पूर्ण
    पूर्ण
    totalCost[0] := 0
    j := 1 से size तक, करें
        totalCost[j] := ∞
        i := 1 से j तक, करें
            यदि totalCost[i-1] ≠ ∞ और lineCost[i, j] ≠ ∞ और
                (totalCost[i-1] + lineCost[i,j] < totalCost[j]), तो
                totalCost[i - 1] := totalCost[i - 1] + lineCost[i, j]
                solution[j] := i
        पूर्ण
    पूर्ण
    सॉल्यूशन मैट्रिक्स प्रदर्शित करें
अंत

उदाहरण (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;
    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