算法：贪心算法

发表于 | 分类于

贪心算法

  • 对问题求解的时候，总是做出在当前看来是最好的做法
  • 适用场景：问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解
  • 与动态规划的不同：对每个子问题的解决方案都做出选择，不能回退

比较

  1. 回溯算法：重复计算
  2. 贪心算法：永远局部最优
  3. 动态规划：记录局部最优子结构，多种记录值

分发饼干

  • g：每个孩子都有一个胃口值，s：每块饼干都有一个尺寸，输出最多满足孩子的数量
  • [1,2,3],[1,1] => 1, [1,2],[1,2,3] => 2

思路：优先使用最小的饼干满足最小的胃口

  1. 饼干、孩子从小到大排序
  2. 遍历饼干和孩子，看g<=s是否成立，满足=>下一个孩子，不满足=>下一个饼干
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function findContentChildren (g, s) {
  let num = 0;
  let cookie = 0;
  let child = 0;
  g.sort();
  s.sort();
  while(cookie<s.length && child<g.length){
    if(g[child]<=s[cookie]){
      child += 1;
      num += 1;
    }
    cookie += 1;
  }
  return num;
}
console.log(findContentChildren([1,2],[1,2,3]))