C++ में बोर्ड को वर्गों में काटने की न्यूनतम लागत

अवधारणा

मान लीजिए लंबाई p और चौड़ाई q का एक बोर्ड दिया गया है, हमें इस बोर्ड को p*q वर्गों में तोड़ना है ताकि तोड़ने की लागत न्यूनतम हो। इस बोर्ड के लिए, प्रत्येक किनारे के लिए काटने की लागत दी जाएगी। संक्षेप में, हमें काटने का ऐसा क्रम चुनना है जिससे लागत न्यूनतम हो।

उदाहरण

उपरोक्त बोर्ड को वर्गों में काटने का इष्टतम तरीका:

प्रारंभिक मान: Total_cost = 0
Total_cost = Total_cost + edge_cost * total_pieces
लागत 5 क्षैतिज कट: Cost = 0 + 5*1 = 5
लागत 5 लंबवत कट: Cost = 5 + 5*2 = 15
लागत 4 लंबवत कट: Cost = 15 + 4*2 = 23
लागत 3 क्षैतिज कट: Cost = 23 + 3*3 = 32
लागत 3 लंबवत कट: Cost = 32 + 3*3 = 41
लागत 2 क्षैतिज कट: Cost = 41 + 2*4 = 49
लागत 2 लंबवत कट: Cost = 49 + 2*4 = 57
लागत 2 लंबवत कट: Cost = 57 + 2*4 = 65

विधि

इस प्रकार की समस्या को लालची दृष्टिकोण का उपयोग करके हल किया जा सकता है। यदि कुल लागत को S द्वारा दर्शाया जाता है, तो S = b1x1 + b2x2 ... + bkxk, जहां xi किसी किनारे को काटने की लागत है और bi संबंधित गुणांक है। गुणांक bi काटने की प्रक्रिया के अंत में किनारे xi का उपयोग करके पूरे किए गए कटों की कुल संख्या द्वारा निर्धारित किया जाता है।

हम ध्यान दें कि गुणांकों का योग हमेशा स्थिर होता है, इसलिए हम bi का एक वितरण प्राप्त करना चाहते हैं जिससे S न्यूनतम हो। ऐसा करने के लिए हम सबसे बड़ी लागत वाले किनारे पर जल्द से जल्द कट लगाते हैं, जिससे इष्टतम S प्राप्त होगा। यदि हमें कई किनारे समान लागत वाले मिलते हैं, तो हम उनमें से किसी एक को पहले काट सकते हैं।

C++ प्रोग्राम

उपरोक्त दृष्टिकोण का उपयोग करके समाधान निम्नलिखित है: पहले हम किनारे की काटने की लागत को उल्टे क्रम में सॉर्ट करते हैं, और फिर हम उच्च लागत से निम्न लागत तक उनमें लूप करके अपना समाधान बनाते हैं। हर बार जब हम एक किनारा चुनते हैं, तो समकक्ष काउंट 1 से बढ़ जाता है, जिसे हर बार संबंधित किनारे की काटने की लागत से गुणा किया जाता है।

// C++ program to divide a board into p*q squares
#include <bits/stdc++.h>
using namespace std;

int minimumCostOfBreaking(int X1[], int Y1[], int p, int q){
    int res1 = 0;
    sort(X1, X1 + p, greater<int>());
    sort(Y1, Y1 + q, greater<int>());
    int hzntl = 1, vert = 1;
    int i = 0, j = 0;
    while (i < p && j < q){
        if (X1[i] > Y1[j]){
            res1 += X1[i] * vert;
            hzntl++;
            i++;
        }
        else{
            res1 += Y1[j] * hzntl;
            vert++;
            j++;
        }
    }
    int total = 0;
    while (i < p)
        total += X1[i++];
    res1 += total * vert;
    total = 0;
    while (j < q)
        total += Y1[j++];
    res1 += total * hzntl;
    return res1;
}

int main(){
    int p = 6, q = 4;
    int X1[p-1] = {3, 2, 4, 2, 5};
    int Y1[q-1] = {5, 2, 3};
    cout << minimumCostOfBreaking(X1, Y1, p-1, q-1);
    return 0;
}

आउटपुट

65