資料結構
聯網
關係型資料庫管理系統 (RDBMS)
作業系統
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
更新於： 17-Jun-2020
759 次觀看
廣告