2017-03-11

JavaScript 版贪心算法题：分饼干

今天，我们要讲的是一道贪心算法题：分饼干。这道题也来自 LeetCode：

https://leetcode.com/problems/assign-cookies

本文将先介绍贪心算法的基础知识，然后使用贪心算法解决这个问题，所用的语言依然是 JavaScript。

贪心算法简介

贪心法，又称贪心算法、贪婪算法、或称贪婪法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。简单来说，贪心算法的核心思想就是今朝有酒今朝醉，活在当下。举几个贪心算法的例子吧！

1，一般人换零钱的时候会应用到贪心算法。把$36换散︰$20 > $10 > $5 > $1。先换大面额再换小面额！

2，但有时候贪心算法并不准确，比如上学时候，学渣使用贪心算法，坚持当下玩乐，但最后却没有好工作，当然前提是他也没有好爸爸。

3，在编程中，贪心算法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。

分饼干

了解了贪心算法，我们来使用它解决“分饼干问题”。“分饼干问题”的题目是这样的：

假设你是一个好爸爸（妈妈），你想给你的孩子们分一些饼干。每个孩子只能得到一块饼干，但每个孩子想要的饼干大小不尽相同。你的目标就是尽量让更多的孩子满意。

下面我们再用断言表示一下需求。编写一个方法 findContentChildren ，它接受一个表示饼干的数组作为参数，返回能满足的孩子的最大数量。

// 如果孩子的要求是 [1, 3, 5, 4, 2]，饼干是[1, 1]，最多能让1个孩子满足。
expect(findContentChildren([1, 3, 5, 4, 2], [1, 1])).toBe(1);
// 如果孩子的要求是 [10, 9, 8, 7, 6]，饼干是[7, 6, 5]，最多能让2个孩子满足。
expect(findContentChildren([10, 9, 8, 7, 6], [7, 6, 5])).toBe(2);

题目分析完了，让我们使用贪心算法来解决它！贪心算法的核心思想是坚持当下的最好选择。那么在这道题中，当下的最好选择是什么？答案是，先将“较小的饼干”分给“对饼干尺寸要求最小”、“最好说话”的孩子，因为他们最容易满足，这样才能最大化满足孩子的数量。那么，整个分配流程就应该是这样的：

首先，将孩子们按“对饼干尺寸要求最小”排序，将饼干按尺寸大小排序。
然后，判断第一块饼干是否能满足第一个孩子，能就分给他，否则就换个稍微大点的，直到满足这个孩子。
满足第一个孩子后，再对第二个、第三个以及后面的孩子重复上面一步，直到饼干分完为止。
最后统计满足了多少个孩子，并返回结果。

那么用 JavaScript 实现就是：

LeetCode/455-assignCookies.js

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function (g, s) {
  var sortFunc = function (a, b) {
    return a - b;
  };
  g.sort(sortFunc);
  s.sort(sortFunc);
  var i = 0;
  for (var j = 0; i < g.length && j < s.length; j++) {
    if (g[i] <= s[j]) {
      i++;
    }
  }
  return i;
};