परिचय
दिए गए लंबाई की N रस्सियाँ हैं। हमें उन्हें जोड़ना है। एक रस्सी को दूसरी से जोड़ने की लागत उनकी लंबाई का योग है। हमारा लक्ष्य N रस्सियों को न्यूनतम लागत पर जोड़ना है।
इस समस्या को हीप ट्री का उपयोग करके हल किया जा सकता है। हम सभी अलग-अलग लंबाईयों को डालने के लिए मिन हीप बनाएंगे, फिर मिन हीप से न्यूनतम और दूसरी न्यूनतम आइटम को हटाएंगे, उन्हें जोड़ेंगे और फिर से हीप ट्री में डालेंगे। जब हीप में केवल एक तत्व रह जाएगा, तो हम प्रक्रिया को रोक सकते हैं और न्यूनतम लागत के साथ जुड़ी रस्सी प्राप्त कर सकते हैं।
इनपुट और आउटपुट
इनपुट: रस्सियों की लंबाईयाँ: {4, 3, 2, 6, 5, 7, 12}
आउटपुट: कुल न्यूनतम लागत: 103
एल्गोरिदम
findMinCost(array, n)
इनपुट: रस्सी की लंबाईयों की सूची, सूची में प्रविष्टियों की संख्या
आउटपुट: काटने की न्यूनतम लागत
Begin
minCost := 0
सरणी तत्वों के साथ प्राथमिकता कतार भरें, (बड़ा मान उच्च प्राथमिकता है)
जब तक कतार खाली नहीं है, करें
item1 := कतार से आइटम प्राप्त करें और कतार से हटाएं
item2 := कतार से आइटम प्राप्त करें और कतार से हटाएं
minCost := minCost + item1 + item2
(item1 + item2) को कतार में जोड़ें
done
minCost लौटाएं
End
उदाहरण (C++ कोड)
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int findMinimumCost(int arr[], int n) {
// प्राथमिकता कतार सेट करें जिसके मान बड़े हों, उनकी प्राथमिकता अधिक हो
priority_queue<int, vector<int>, greater<int>> queue(arr, arr+n);
int minCost = 0;
while (queue.size() > 1) {
// जब कतार में एक से अधिक तत्व हों
int item1 = queue.top(); // item1 सबसे छोटा तत्व है
queue.pop();
int item2 = queue.top(); // item2 item1 से बड़ा है लेकिन दूसरों से छोटा
queue.pop();
minCost += item1 + item2; // रस्सियों को जोड़ें और उन्हें कतार में जोड़ें
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
