贪心算法

[Leo-lin214]

所谓贪心，顾名思义就是在当前环境下选择最优的方案（即局部最优方案），从而使得后面的结果是全局最优的方案。

贪心算法并不能保证局部所选的最优方案对于最后的结果也是最优的，因此它也是动态规划的一个子集。

而且，贪心算法的使用最简单的方式就是，通过遍历，然后每次遍历都拿最优的解出来即可。

找零问题

假设你是一个商店老板，你需要给顾客找零n元钱，你手上有的钱的面值为：100元，50元，20元，5元，1元。请问如何找零使得所需要的钱币数量最少？

该例子其实在我们的生活中很常见，最简单就是每次都拿最大面值的零钱。

举个最简单的例子，需要找零131元，那么我们可以这样：

• 先从最大面值100元开始，减去100元，剩下31元。
• 再看50元面值，明显是大于31元，直接跳过。
• 再看20元面值，减去20元，剩下11元。
• 再看5元面值，减去5元，剩下6元。
• 可以再减5元，剩下1元。
• 因此总共花费100元、20元、5元、5元、1元，最少找零的数量为5个。

可以看到，每次都先从最大面值开始选择，符合贪心算法中的局部最优方案，从而得到最终最优解。

实现如下：

const changeMoney = n => {
  const money = [1, 5, 20, 50, 100];
  const result = [];
  money.sort((a, b) => b - a);
  for (let i = 0; i < money.length; i++) {
    if (n >= money[i]) {
      let mul = parseInt(n/money[i]);
      n -= mul * money[i];
      while (mul) {
      	result.push(money[i]);
        mul--;
      }
    }
  }
  return result;
}

但是找零问题会有些特殊情况并不适合使用贪心算法，举个例子：

现在面值的零钱有1元、5元、11元，这时候要找零15元，该如何处理？

如果单纯按照贪心算法，首先会选择1个11元，然后再选4个1元，总共花费了5个零钱。但是直接找3个5元不是更少吗？

是的，找零问题并不完完全全适合贪心算法，那么什么样的找零才能适合贪心呢？

按照这篇文章怎样的币值可以用贪心算法进行找零的解析，人民币肯定符合！！！但是只要满足以下其中一个条件都能满足贪心算法。

1. a[i] 和 a[i + 1] 存在倍数关系，即 a[i + 1] = k * a[i]。
2. a[i] 和 a[i + 1] 不存在倍数关系，这时候只需要找到一个整数 k，满足：(k - 1) * a[i] < a[i + 1] 并且 k * a[i] >= a[i + 1]。

背包问题

有一个小偷，进到一个店里偷东西，店里每个东西的价值是v，每个东西的重量是w。但小偷只有一个背包，总共能承受的重量是W。请问怎么拿东西能让他拿到的价值最大？

例如：

商品1: v1 = 60，w1 = 10；

商品2: v2 = 100， w2 = 20；

商品3: v3 = 120，w3 = 30；

背包容量：W = 50；

背包问题可以细分为两类问题，分别为：0-1背包和分数背包。

• 0-1背包：要么全拿走，要么就不拿，直到容量不够为止。
• 分数背包：不够容量时，可拿商品的一部分走，直到容量耗尽为止。

我们先来看看0-1背包，如果使用贪心算法，我们肯定会选择价值最大的（价值最大即价值/重量最大），因此会选择v1，剩余40容量，再选择v2，剩下容量20，明显是没法再拿v3的，但这就是最优解吗？明显不是，如果我选择v2和v3，刚好用完背包容量，明显这才是最优解，最终可以得出0-1背包问题并不适合使用贪心算法，也就只能使用动态规划。

const products = [
  { v: 60, w: 10 },
  { v: 100, w: 20 },
  { v: 120, w: 30 }
];
const steal = (w, products) => {
  products.sort((a, b) => (a.v/a.w) - (b.v/b.w));
  const result = [];
  for (let i = 0; i < products.length; i++) {
    result[i].push([]);
    for (let j = 0; j <= w; j++) {
      if (j === 0) {
        result[i][j] = 0;
      } else if (i === 0) {
        result[i][j] = j > products[i].w ? products[i].v : 0;
      } else {
        let getLast = 0;
        if (j > products[i].w && j - products[i].w) {
          getLast = products[i].v + result[i - 1][j - products[i].w];
        }
        result[i][j] = Math.max(result[i - 1][j], getLast)
      }
    }
  }
  return result[products.length - 1][w];
}

好了，我们再来回顾一下分数背包问题，当不够容量时，可以直接拿一部分，那么这样一来肯定满足贪心算法了。

const steal = (w, products) => {
  const result = [];
  products.sort((a, b) => (b.v/b.w) - (a.v/a.w));
  for (let i = 0; i < products.length; i++) {
    if (w >= products[i].w) {
      result.push(products[i].v);
      w -= products[i].w;
    } else {
      const temp = w / products[i].w;
      result.push(products[i].v * temp);
      w = 0;
    }
  }
  return result;
}

数字拼接问题

有n个非负整数，将其按照字符串拼接的方式拼接为一个整数，使得拼接后的整数最大。

例如：32，94，128，1286，6，71，那么拼接到的最大整数位94316321286128。

对于两个数 a 和 b，最简单的做法就是判断 ab 和 ba 两个数哪个最大，然后决定 a 和 b 的位置。而这也刚好满足了贪心的思想，局部最优就是拿两个数组合的最大值。

const getMaxNumber = arr => {
  if (!arr || !Array.isArray(arr) || arr.length <= 1) return arr;
  arr.sort((a, b) => `${b}${a}` - `${a}${b}`)
  return arr.join('');
}

活动选择问题

假设有 n 个活动，这些活动要占用同一片场地，而场地在某时刻只能提供一个活动使用。

每个活动都有一个开始时间 Si 和结束时间 fi（题目中时间以整数表示），表示活动在 [Si, fi) 区间占用场地。

那么，安排那些活动能够使该场地举办的活动的个数最多？

要使得举办的活动个数最多，那么转过来想，那就是将更多的时间留给后面活动，这样一来，在后面就可以更好滴安排活动。

换句话说，应该把结束时间最早的活动安排在第一个，再在剩下的时间里面继续安排结束时间早的活动。因此是符合贪心算法的。

const setPlan = arr => {
  if (!arr || !Array.isArray(arr)) return arr;
  arr.sort((a, b) => a.end - b.end);
  const result = [];
  let end = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i].start >= end) {
      result.push(arr[i]);
      end = arr[i].end;
    }
  }
  return result;
}

分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

要满足尽可能多的孩子能够享受到饼干，用贪心的思想，那么就是优先安排胃口值低的孩子，那么后面的孩子就可以在剩下的饼干得到享受。

const findContentChildren = function(g, s) {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);
  let result = 0;
  let gIndex = 0;
  let sIndex = 0;
  while (gIndex < g.length && sIndex < s.length) {
    if (g[gIndex] <= s[sIndex]) {
      result++;
      gIndex++;
    }
    sIndex++;
  }
  return result;
}

贪心算法的核心，每次都得贪！

那么怎么贪？一句话解析，就是尽可能使得当前结果是最好的，以及对于后续的结果也是最好的！

比如上面的活动安排，要尽可能安排多个活动，那么就应该考虑先安排结束时间最早的，然后后面的活动才可以有更多的时间进行安排。

又比如上面的分发饼干，要尽可能每个孩子都能分发饼干，那么就应该先将胃口值低的孩子先安排，那么后面的孩子才有更多饼干去选择。

但是，贪并不一定就可以使得最后的结果是最好的，比如上面的 0-1 背包问题，明显就无法，要结合题目进行分析。