ต่อเชือก n ตัวด้วยต้นทุนขั้นต่ำ

มี N เชือกตามความยาวที่กำหนด เราต้องเชื่อมต่อกับพวกเขา ค่าใช้จ่ายในการต่อเชือกเส้นหนึ่งเข้ากับอีกเส้นคือผลรวมของความยาว เป้าหมายของเราคือการเชื่อมต่อเชือก N ด้วยต้นทุนขั้นต่ำ

ปัญหานี้สามารถแก้ไขได้โดยใช้ฮีปทรี เราจะสร้าง min heap เพื่อแทรกความยาวที่แตกต่างกันทั้งหมดก่อน จากนั้นจึงลบรายการขั้นต่ำและวินาทีขั้นต่ำจาก min heap เชื่อมต่อพวกมันและแทรกอีกครั้งในแผนผัง heap เมื่อฮีปมีองค์ประกอบเพียงตัวเดียว เราสามารถหยุดกระบวนการและรับเชือกที่เชื่อมต่อด้วยต้นทุนขั้นต่ำ

อินพุตและเอาต์พุต

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