数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告