दी गई लंबाई की N रस्सियाँ हैं। हमें उनसे जुड़ना होगा। एक रस्सी को दूसरे से जोड़ने की लागत उनकी लंबाई का योग है। हमारा लक्ष्य एन रस्सियों को न्यूनतम लागत से जोड़ना है।
एक हीप ट्री का उपयोग करके इस समस्या को हल किया जा सकता है। हम पहले सभी अलग-अलग लंबाई डालने के लिए न्यूनतम ढेर बनाएंगे, फिर न्यूनतम ढेर से न्यूनतम और दूसरा न्यूनतम आइटम हटा देंगे, उन्हें कनेक्ट करेंगे और फिर से ढेर पेड़ में डालेंगे। जब ढेर में केवल एक तत्व होगा, तो हम प्रक्रिया को रोक सकते हैं और न्यूनतम लागत के साथ कनेक्टेड रस्सी प्राप्त कर सकते हैं।
इनपुट और आउटपुट
Input:
The lengths of the ropes: {4, 3, 2, 6, 5, 7, 12}
Output:
Total minimum cost: 103 एल्गोरिदम
findMinCost(array, n)
इनपुट - रस्सी की लंबाई की सूची, सूची में प्रविष्टियों की संख्या।
आउटपुट - न्यूनतम लागत में कटौती।
Begin minCost := 0 fill priority queue with the array elements, (greater value is higher priority) while queue is not empty, do item1 := get item from queue and delete from queue item2 := get item from queue and delete from queue minCost := minCost + item1 + item2 add (item1 + item2) into the queue done return minCost End
उदाहरण
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int findMinimumCost(int arr[], int n) {
//priority queue is set as whose value is bigger, have higher priority
priority_queue< int, vector<int>, greater<int>>queue(arr, arr+n);
int minCost = 0;
while (queue.size() > 1) { //when queue has more than one element
int item1 = queue.top(); //item1 is the shortest element
queue.pop();
int item2 = queue.top(); //item2 is bigger than item1 but shorter then other
queue.pop();
minCost += item1 + item2; //connect ropes and add them to the queue
queue.push(item1 + item2);
}
return minCost;
}
int main() {
int ropeLength[] = {4, 3, 2, 6, 5, 7, 12};
int n = 7;
cout << "Total minimum cost: " << findMinimumCost(ropeLength, n);
} खोजें आउटपुट
Total minimum cost: 103