前言

在前端开发过程中，除了一般的逻辑使用之外，也会涉及到算法相关的知识，比如冒泡排序、数组去重/合并、贪心算法、八皇后算法等等，这些都是比较常用的前端算法相关的知识点。关于前端实际开发中用到的算法，虽然没有后端要求的那么多，但是也有比较重要的算法知识，本篇博文就来分享一下关于贪心算法的相关知识点，记录一下，方便查阅使用。

贪心算法概念

贪心算法（又叫贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。（注意： 贪心算法，算法结构犹如其名，以局部最优解，进行小范围的最优累加，但是贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。）

贪心算法的构成

贪心算法的构成有：霍夫曼编码、prim和kruskal最小生成树算法、Dijkstra最短路径算法。

贪心算法的核心

        贪心算法的核心主要是要找出问题的贪心策略，贪心策略的主要逻辑就是每一次都选择当前的最优解，一直到得出全局的最优解。

贪心算法的缺点

虽然贪心算法每一次都选择当前的最优解，直到得出全局的最优解，但每一次的局部最优解不等于最终的全局最优解，不能从整体考虑所有的可能，每次都是采用局部的最优解、不回溯，所以有时候无法得出最优解，这就是贪心算法最大的缺点！

贪心算法的应用场景

  贪心算法的应用场景：1、关于某一组数据，需要有限制值和期望值，想要从中选出几个数据，在满足前面限制值的情况下，期望值最大； 2、每次选择当前条件下，在对限制值同等贡献的情况下，对期望值贡献最大的数据；3、买卖产品的最佳时机；4、分水果、分饼干、分办公用具等分配问题。

贪心算法的使用步骤

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，贪心算法一般按如下思路步骤使用：

• 1、建立数学模型来描述问题；
• 2、把求解的问题分成若干个子问题；
• 3、对每个子问题求解，得到子问题的局部最优解；
• 4、把子问题的解局部最优解合成原来解问题的一个解。

具体的示例如下所示：

Greedy(Q)  { //Q是问题的输入集合，也就是候选集合C={ };  //初始解集合是一个空集合while (not solution(C)) {  //集合C没有构成问题的一个解x=select(Q);    //在候选集合Q中做贪心选择if feasible(C, x)  //判断集合C中加入x后的解是否可行C=C+{x};Q=Q-{x};}return C;}

贪心算法的示例

这里列举两个比较有代表性的贪心算法示例，方便理解使用。

示例一：分水果、分饼干、分办公用具等分配问题———分饼干问题

/*** @param {number[]} h 胃口值* @param {number[]} m 饼干的大小* @return {number} i 最优解*/var findCookies = function(h, m) {const mysort = (a, b) => {return  a-b;}h.sort(mysort);m.sort(mysort);let i = 0;m.forEach((n) => {if(n >= h[i]){i++;}})return i;};

示例二：买卖产品的最佳时机——————买卖股票的最佳时机

/*** @param {number[]} p 价格* @return {number} r 最优解*/var maxOptimal = function(p) {var r = 0;for(var i=1;i<=p.length;i++){if(p[i]>p[i-1]){r = p[i] - p[i-1] + r;}}return r;};

示例三：柠檬水找零——每一杯柠檬水的售价为 5元。每位顾客只买一杯柠檬水，然后付5元或10元或 20元，然后给每个顾客正确找零。

var priceChange = function (rmbs) { //若客户给了20，可以找10+5，或5+5+5，其中10+5就算是贪心let fiveN = 0; //5元0张let tenN = 0; //10元0张for (let i = 0; i < rmbs.length; i++) {let rmb = rmbs[i]; //第i个客户给了张多少元的钱if (rmb === 5) {fiveN += 1;} else if (rmb === 10) {//客户给10元+，有5元找-，找不开直接falseif (fiveN > 0) {fiveN -= 1;tenN += 1;} else {return false;}} else {//客户给20if (tenN >= 1 && fiveN >= 1) {//优先找零组合10+5fiveN -= 1;tenN -= 1;} else if (fiveN >= 3) {//接着找找零组合5+5+5fiveN -= 3;} else {return false;}}}return true;};

示例四：区间覆盖——假设有n个区间，区间的起始断点和结束断点分别是[a1,b1],[a2,b2],….[an,bn]，从这些区间中选出一部分区间，使这部分区间满足两两不想交，最多能选出的区间个数。

var sArray = function(array){let m = array.length;let sizeArray = array.sort(compareA());let res = [],c = 0,d = 0;for(let i = 0;id || right