数据结构
联网
关系型数据库管理系统 (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 次观看
广告