ন্যূনতম খরচের সাথে দড়ি সংযুক্ত করুন

প্রদত্ত দৈর্ঘ্যের 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