ন্যূনতম খরচে n রাস्सি সংযোগ (Connect n ropes with minimum cost)

দেওয়া দৈর্ঘ্যের Nটি রাস্সি আছে। আমাদের সেগুলো সংযোগ করতে হবে। একটি রাস্সি অন্যটির সাথে সংযোগ করার খরচ হল তাদের দৈর্ঘ্যের যোগফল। আমাদের লক্ষ্য Nটি রাস্সি ন্যূনতম খরচে সংযোগ করা।

এই সমস্যাটি হিপ ট্রি ব্যবহার করে সমাধান করা যায়। আমরা একটি মিন হিপ তৈরি করে সব দৈর্ঘ্য ইনসার্ট করব, তারপর মিন হিপ থেকে ন্যূনতম এবং দ্বিতীয় ন্যূনতম আইটেম বের করব, সেগুলো সংযোগ করে আবার হিপ ট্রিতে ইনসার্ট করব। যখন হিপে শুধু একটি এলিমেন্ট থাকবে, প্রক্রিয়া বন্ধ করে ন্যূনতম খরচে সংযুক্ত রাস্সি পাওয়া যাবে।

ইনপুট এবং আউটপুট

ইনপুট: রাস্সিগুলোর দৈর্ঘ্য: {4, 3, 2, 6, 5, 7, 12} আউটপুট: মোট ন্যূনতম খরচ: ১০৩

অ্যালগরিদম

findMinCost(array, n)

ইনপুট - রাস্সির দৈর্ঘ্যের তালিকা, তালিকার এন্ট্রি সংখ্যা।

আউটপুট - কাটার ন্যূনতম খরচ।

শুরু 
  minCost := 0 
  অ্যারে এলিমেন্ট দিয়ে প্রায়ориটি কিউ পূরণ করুন, (বড় মান হাইয়ার প্রায়োরিটি) 
  যতক্ষণ কিউ খালি নয়, করুন 
    item1 := কিউ থেকে আইটেম বের করুন এবং কিউ থেকে ডিলিট করুন 
    item2 := কিউ থেকে আইটেম বের করুন এবং কিউ থেকে ডিলিট করুন 
    minCost := minCost + item1 + item2 
    (item1 + item2) কিউতে যোগ করুন 
  শেষ 
  minCost ফেরত দিন 
শেষ

উদাহরণ

#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