अवधारणा
मान लीजिए कि लंबाई p और चौड़ाई q का एक बोर्ड दिया गया है, हमें इस बोर्ड को p*q वर्गों में तोड़ने की आवश्यकता है ताकि तोड़ने की लागत कम से कम हो। इस बोर्ड के लिए हर किनारे के लिए कटिंग कॉस्ट दी जाएगी। संक्षेप में, हमें काटने के ऐसे क्रम का चयन करने की आवश्यकता है जिससे लागत कम से कम हो।
>उदाहरण
उपरोक्त बोर्ड के संबंध में वर्ग में कटौती करने का इष्टतम तरीका है -
उपरोक्त मामले में कुल न्यूनतम लागत 65 है। इसकी गणना निम्नलिखित चरणों को लागू करके की जाती है।
Initial Value : Total_cost = 0 Total_cost = Total_cost + edge_cost * total_pieces Cost 5 Horizontal cut Cost = 0 + 5*1 = 5 Cost 5 Vertical cut Cost = 5 + 5*2 = 15 Cost 4 Vertical cut Cost = 15 + 4*2 = 23 Cost 3 Horizontal cut Cost = 23 + 3*3 = 32 Cost 3 Vertical cut Cost = 32 + 3*3 = 41 Cost 2 Horizontal cut Cost = 41 + 2*4 = 49 Cost 2 Vertical cut Cost = 49 + 2*4 = 57 Cost 2 Vertical cut Cost = 57 + 2*4 = 65
विधि
लालची दृष्टिकोण को लागू करके इस प्रकार की समस्या को हल किया जा सकता है। यदि कुल लागत को S द्वारा माना जाता है, तो S =b1x1 + b2x2 … + bkxk, जहां xi को कुछ किनारे काटने की लागत के रूप में माना जाता है और द्वि संबंधित गुणांक है, गुणांक द्वि को कटौती की कुल संख्या से निर्धारित किया जाता है जिसे हमने बढ़त को लागू करने के लिए प्रतिस्पर्धा की है xi काटने की प्रक्रिया के अंत में।
हमें ध्यान देना चाहिए कि गुणांकों का योग हमेशा स्थिर होता है, इसलिए हम द्वि प्राप्य वितरण की गणना करना चाहते हैं जैसे कि एस सबसे कम है। ऐसा करने के लिए हम जितनी जल्दी हो सके सबसे बड़े लागत किनारे पर कटौती करते हैं, जो इष्टतम एस तक पहुंच जाएगा। अगर हमें समान लागत वाले कई किनारों का सामना करना पड़ता है, तो हम उनमें से किसी एक को पहले हटा या काट सकते हैं।
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