Kết nối n dây với chi phí tối thiểu

Có N sợi dây có độ dài cho trước. Chúng tôi phải kết nối với họ. Chi phí nối một sợi dây này với sợi dây kia là tổng chiều dài của chúng. Mục tiêu của chúng tôi là kết nối N dây với chi phí tối thiểu.

Vấn đề này có thể được giải quyết bằng cách sử dụng một cây đống. Chúng tôi sẽ tạo min heap để chèn tất cả các độ dài khác nhau trước tiên, sau đó xóa mục tối thiểu và tối thiểu thứ hai khỏi min heap, kết nối chúng và chèn lại vào cây heap. Khi heap chỉ chứa một phần tử, chúng tôi có thể dừng quá trình và lấy sợi dây kết nối với chi phí tối thiểu.

Đầu vào và Đầu ra

Input:
The lengths of the ropes: {4, 3, 2, 6, 5, 7, 12}
Output:
Total minimum cost: 103

Thuật toán

findMinCost(array, n)

Đầu vào - Danh sách chiều dài dây, số mục trong danh sách.

Đầu ra - Chi phí tối thiểu để cắt giảm.

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

Ví dụ

#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);
}

Đầu ra

Total minimum cost: 103