資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究以最小成本連線 n 根繩子\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
更新日期：2020 年 6 月 17 日
758 次瀏覽
廣告