최소 비용으로 n개의 로프 연결

주어진 길이의 N개의 로프가 있습니다. 우리는 그들과 연결해야 합니다. 한 로프를 다른 로프와 연결하는 비용은 길이의 합입니다. 우리의 목표는 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