本文主要介绍贪心算法及一些经典场景案例

算法核心：每次寻求最优解，直到满足最终需求。只看目前，不虑未来。又名：鼠目寸光

1. 分饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

此题第一次做还想复杂了，每个孩子最多只能给一块饼干这句话没注意到…如果每个孩子顶多一块，那就很简单了。
思路：我们的目标是为了尽可能多的喂饱孩子，数量最大，那么就应该按照孩子们的胃口排个序，优先满足胃口小的，同时应该用最小的饼干。我们同时注意到每个孩子顶多一块饼干，所以就很简单了，直接排序+遍历，直到饼干用完。代码如下：

// 方案一： 暴力循环
const findContentChildren = () => {
  // 1. 排序
  const gSort = g.sort((a, b) => {
    return a - b;
  });
  const sSort = s.sort((a, b) => {
    return a - b;
  });
  //  2. 遍历
  let count = 0;
  for (let i = 0; i < gSort.length; i++) {
    const resIndex = gSort.findIndex((item) => item >= gSort[i]);
    if (resIndex) {
      count++;
      gSort.splice(resIndex, 1);
    }
  }
  return count;
};

// 方案二：指针移动
/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
const findContentChildren = function(g, s) {
    if(g.length === 0 || s.length === 0) return 0;
    const g_sort = g.sort((a,b) => a - b);      
    const s_sort = s.sort((a,b) => a - b);     
    let gi = 0, si = 0;
    while(gi < g_sort.length && si < s_sort.length){       
        if(g_sort[gi] <= s_sort[si]){                   
            gi++                                        
        }
        si++                                            
    }
    return gi;
};

2. 凑钞票
一个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。
思路： 为了输出最少的钞票，那我们每次取出的钞票，应该尽可能最大，以此达到数量的最小。先根据从大到小排序，每次及尽可能地用当前币值去消减总金额，直到达到最终的凑满目标金额。代码如下：

const f = (arr, target) => {
    let res = []
    arr.sort((a, b) => {
        return b - a
    })
    console.log(arr)
    while(target) {
        const cur = arr.shift()
        if (cur <= target) {
            const num = Math.floor(target / cur)
            target = target % cur
            res.push({ key: cur, num: num})
        }
    }
    return res
}
const arr = [1, 5, 10, 20, 50, 100]
let target = 666
console.log(f(arr, target))

输出：

[
    { key: 100, num: 6 },
    { key: 50, num: 1 },
    { key: 10, num: 1 },
    { key: 5, num: 1 },
    { key: 1, num: 1 }
]

但是吧，上面的场景，考虑另外一种情况：

const arr = [1, 5, 11]
let target = 15

贪心策略的输出：

[ { key: 11, num: 1 }, { key: 1, num: 4 } ]

用掉了五张钞票，但是很显然，为了凑满15， 三张五块即可实现。为什么？因为贪心算法的精髓: 鼠目寸光，只考虑眼下，无视未来。使用了一张11，其代价是要用四张一块去满足剩下的金额。
至于如何避免？详见动态规划篇