# 贪心算法

# 什么是贪心算法

贪心算法（greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最优的选择，从而希望导致结果是最优的算法。

换句话说，贪心算法总是做出局部最优选择，希望这样能得到全局最优解。

💡 基本思路：

建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
将所有子问题的局部最优解综合起来，得到问题的最终解；

# 什么时候用贪心算法

只有满足 “贪心选择性质” 和 “最优子结构性质” 的问题才能用贪心算法找到最优解。

# 贪心选择性质

贪心选择性质指的是，可以通过做出局部最优选择，来构造全局最优解。换句话说，前面的选择不影响，也不依赖后面的选择。

下面是一个反例：

例子：

🌰 在一个有权图中，我们从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）

贪心算法的解决思路：每次都选择一条跟当前顶点相连的权最小的边，直到找到顶点 T。

按照这种思路，我们求出的最短路径是 S->A->E->T，路径长度是 1+4+4=9。

但是，这种贪心的选择方式，最终求的路径并不是最短路径，因为路径 S->B->D->T 才是最短路径，因为这条路径的长度是 2+2+2=6。

在这个问题上，贪心算法不工作的主要原因是，前面的选择，会影响后面的选择。如果我们第一步从顶点 S 走到顶点 A，那接下来面对的顶点和边，跟第一步从顶点 S 走到顶点 B，是完全不同的。所以，即便我们第一步选择最优的走法，但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。

# 最优子结构性质

如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。

例子：

🌰 举例来说，想要从 A 到 B 找一条最短路径。假设找到的路径为 A->C->D->B 最短。那么最优子结构性质说的是，如果对于路径上的任意一点，到 B 都存在一条最短路径是包含在上述 A 到 B 的最短路径里。

比如这里如果满足最优子结构性质应该有 C->D->B 是 C 到 B 的一条最短路径。不可能是别的路径。

如果说 C->H->B 才是从 C 到 B 的一条最短路径，那么这个问题就不满足最优子结构性质。

# 调度问题

# 找硬币问题

问题描述：用 25 美分，10 美分，5 美分，1 美分硬币找 n 美分零钱，使硬币总数尽可能的少。

思路：通过贪心算法，在每一步选择可能的最大面值硬币，使得每一步选择的硬币面值加一起不超过 n。

// 找零钱的贪心算法

// value：金额；coins：储存硬币面值的数组
public static void change(int value, int[] coins) {
  // count 数组用来给各个面值的硬币计数
  int[] count = new int[coins.length];

  for (int i = 0; i < coins.length; i++) {
    while (value - coins[i] >= 0) {
      value -= coins[i];
      count[i]++;
    }

    System.out.println("需要" + coins[i] + "面值硬币" + count[i] + "个；");
  }
}

在使用 25 美分，10 美分，5 美分，1 美分硬币。去给 50 美分找零的情况下，代码输出如下：

需要 25 面值硬币 2 个；
需要 10 面值硬币 0 个；
需要 5 面值硬币 0 个；
需要 1 面值硬币 0 个；

但是如果只能使用 25 美分，10 美分，1 美分硬币。去给 30 美分找零。上面的算法就会使用 1 个 25 美分，5 个 1 美分。但实际情况下，3 个 10 美分硬币才是最少的选择。

所以，不是所以的硬币面值组合都可以用贪心算法找到最优解。具体的证明这里先不展开。

# 霍夫曼编码

假设我有一个包含 1000 个字符的文件，每个字符占 1 个 byte（1 byte = 8 bits），存储这 1000 个字符就一共需要 8000 bits，那有没有更加节省空间的存储方式呢？

假设我们通过统计分析发现，这 1000 个字符中只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f。而 3 个二进制位（bit）就可以表示 8 个不同的字符，所以，为了尽量减少存储空间，每个字符我们用 3 个二进制位来表示。那存储这 1000 个字符只需要 3000bits 就可以了

霍夫曼编码在上面思路的基础上，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。把出现频率比较多的字符，用稍微短一些的编码；出现频率比较少的字符，用稍微长一些的编码。霍夫曼编码通过这种不等长的编码方法，来进一步增加压缩的效率。

但是编码不等长，在解压的时候，该如何去判断应该读取多长的编码呢？为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。

在解压缩的时候，我们每次会读取尽可能长的可解压的二进制串。一旦发现可识别的编码，就把它截取出来进行翻译。