[数据结构与算法]贪心算法理解与经典案例---背包案例

如题：

已知五个物品重量分别是：{10,15,18,20,25};
五个物品价值依次为{12,15,20,25,27};
现有一个能容纳重量100的背包，求如何搭配能使不超过背包容量装下最大价值的物品!

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

贪心算法一般按如下步骤进行

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

我们按照步骤依次来分析：如题，简单来说就是如何在重量100的限制下选出物品的最佳配置。

这里我们有三个可以思考的策略

1. 每次装入的都是价值和重量比率最高的，也就是我们常说的性价比最高的
2. 每次装入的是当前可选择的东西中，价值最高的
3. 每次装入的是当前可选择东西中，重量最轻的

首先我们本能上会觉得策略一是最佳方案，我们将思路转换成代码来验证一下：

let arr = [
    //货物名，重量，价值
    { name: 'goodA',  weight: 10, value: 12 },
    { name: 'goodB',  weight: 15, value: 15 },
    { name: 'goodC',  weight: 18, value: 21 },
    { name: 'goodD',  weight: 20, value: 25 },
    { name: 'goodE',  weight: 25, value: 27 },
  ]
function greedy(data) {//data为背包容量
    arr.map(e => {
        e.ratio=e.value/e.weight;//计算价值与重量比率，比率越高越好
    })
    // 我们先排序
    let sort=arr.sort(compare('ratio'))
    let values=0;
    // 我们先用比率最大的装满背包---直到装不下为止，取余数依次往下装
    sort.map(el=>{
        if(data>el.weight){
            values=values+parseInt(data/el.weight)*el.value
            data=data%el.weight
        }
    })
    console.log(values);
}
// 数组排序方法
function compare(value) {//value:根据什么属性排序
     return function(a,b){
      var value1 = a[value];
      var value2 = b[value];
      /*
      * value2 - value1; ——> 降序
      * value1 - value2; ——> 升序
      */
      return value2- value1;//升序排序
     }
    }
greedy(119);//背包的容量

我的思路是先计算重量价值比，再降序排列，比率最大的优先装到最大，剩余重量依次往下排，当余数大于下一个货物重量时，再求整取余，获得最终的最大价值的方案。

结果输出完毕。这是实现按比例的思路实现的最优解，哪装入价值最大与装入最轻的值会更小吗？我推测应该是的，这个问题就留给小伙伴你们来尝试一下了。

晚安，头有点疼了