算法第六节（第2部分（切金条））

2021-11-25

#include #include #include #include #include #include #include #include #include using namespace std; // //test.h //test // //Created by 吴珝君 on 2018/12/31. //Copyright?2018年闲着也是贤者. All rights reserved. // /************************************************************************/ /************************************************************************/ /* 一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为 10+20+30=60. 金条要分成10,20,30三个部分。如果，先把长度60的金条分成10和50，花费60 再把长度50的金条分成20和30，花费50 一共花费110铜板。但是如果，先把长度60的金条分成30 和30，花费60 再把长度30 金条分成10和20，花费30 一共花费90铜板。输入一个数组，返回分割的最小代价。 */ /************************************************************************/ /************************************************************************/ /* 算法思想：要实现这个目标 :要利用哈夫曼编码编码长度越短，代价越低*/ /************************************************************************/ classCostLessMoney { // public: int costLetestMoney(vectorv) { int sum = 0; priority_queue, greater> p; //小顶推每次选择小的 for (int i =0; i < v.size(); i++) { p.push(v[i]); } while(p.size() > 1) { int t1 = p.top(); p.pop(); int t2 = p.top(); p.pop(); sum = t1 + t2; p.push(sum); } return sum; } }; //优先级队列 class project { public: project(int c, int p) { cost = c; profit = p; } int cost; int profit; }; class compare1 { public: bool operator()(project p1, project p2)//从大到小排列 {return p1.cost > p2.cost; // 小顶堆 } }; class compare2 { public: bool operator() (project p1, project p2)//从小到大排列 { return p1.profit < p2.profit; // 大顶堆 } }; classMoreMoney { public: intgetMoreMoney(vector v, int k, int principal) { priority_queue, compare1> costHeap; //建立小顶堆 priority_queue【算法第六节（第2部分（切金条））】, compare2>profitHeap; //建立大顶堆for (int i =0; i < v.size(); i++) { //sort(v.begin(),v.end(),compare1()); costHeap.push(v[i]); } int w = principal; for (int i =0 ; i < k ; i++) { while( !costHeap.empty() && costHeap.top().cost <= w) { profitHeap.push(costHeap.top()); costHeap.pop(); } if(!profitHeap.empty()) { w += profitHeap.top().profit ; profitHeap.pop(); } else break; } return w; }}; int main() { project p1(17,4); project p2(10,2); project p3(15,3); project p4(15,4); vector v; v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); MoreMoney m; cout << m.getMoreMoney(v,4,13); system("pause"); return 0; }

推荐阅读

上一篇：Deep|深度学习系列（Seq2Seq原理及相关案例（附代码））

下一篇：【搜索与回溯算法】有重复元素的排列问题