最小限のコストでn本のロープを接続する

この問題は、ヒープツリーを使用して解決できます。最小ヒープを作成して、最初にすべての異なる長さを挿入し、次に最小ヒープと2番目の最小アイテムを最小ヒープから削除し、それらを接続して、ヒープツリーに再度挿入します。ヒープが1つの要素のみを保持する場合、プロセスを停止して、最小限のコストで接続されたロープを取得できます。

入力と出力

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