前端开发--算法模式(贪心算法)

贪心算法：遵循的是一种近似解决问题的技术，期盼通过每一个阶段的局部最优选择(当前最优解)，从而达到全局最优。他不像动态规划算法那样计算更大的格局。

最少硬币找零问题

最少营部找零问题就可以使用贪心算法解决，绝大部分的结果是最优解，但是对于一些面额是得不到最优解的。我们现在看一下算法。

function MinCoinChange(coins){
  let coins = coins;
  this.makeChange = function(){
    let change = [];
    let total = 0;
    for(let i = coins.length; i>=0;i--){
      let coin = coins[i];
      while(total+coin <= amount){
        change.push(coin);
        total += coin;
      }
    }
    return change;
  }
}

从上面的代码我们看到了，贪心版本的最少硬币找零问题不论是从代码还是从逻辑上看，都比动态规划版本的腰简单的多。
对于每一个面额来说，吧它的值和total相加后，total需要小于amount的值，我们会将当前面额的coin添加到结果中去，也会将它和total相加。
这个解法很简单，从最大的面额开始，尽可能和多的那这种面额大的硬币，当无法再拿这个大额的硬币的时候，开始拿第二大价值的硬币，一次继续。

let minCoinChange = new MinCoinChange([1,5,10,25]);
console.log(minCoinChange.makeChange(36));

发现上面的输出的代码和动态规划得到的结果是一样的，现在我们通过下图来阐述一下算法执行的过程：

贪心算法的最少硬币的使用场景

分数背包问题

在求解分数背包问题的算法与动态规划稍有不同。在0-1背包问题中，只有向背包中装入完整的物品，而在分数背包中，我们可以转入分数的物品，我们用之前用的例子来比较二者的差异。

分数背包问题的描述

在动态规划的例子里面，我们考虑了背包只能携带重量为5.而在这个例子中，我们可以说最佳的解决方案是向背包中放入物品1和物品2，总重量为5，总价值为7。但是如果在分数背包中，我们考虑相同的容量，得到的结果是一样的，所以我们考虑一下容量为6的背包。在背包容量为6的情况下，解决方案是装入物品1和物品2，还有25%的物品3，这样的话总价值为8.25。
现在我们看一下代码的实现过程：

function knapSack(capacity,values,weights){
  let n = values.length;
  let load = 0,i = 0, val = 0;
  for(i = 0; i<n && load < capacity; i++){ //重量小于背包的重量，继续迭代，装入物品
    if(weights[i] <=(weights - load)){//如果该物品可以完整的装入背包，就假期价值和重量分别计入背包中
      val += values[i];
      load += weights[i];
    }else{
      let r = (capacity - load) / weights[i]; //如果背包的重量是无法完整的装入的，计算部分的价值
      val += r * values[i];
      load += weights[i]
    }
  }
  return w;
}