一、贪心算法
什么情况下我们要想到用贪心算法：
1、当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大；
2、我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据 。
3、我们举几个例子看下贪心算法产生的结果是否是最优的。大部分情况下，举几个例子验证一下就可以
了。
注意：不要刻意去记忆贪心算法的原理，要多练习；不要严谨的证明算法，多举几个例子验证一下！
我们用几个案例来理解贪心算法。
1、有一个可以装100kg物品的箱子，我们有5种物品（大米100kg，总价值100元； 玉米30kg，总价值90元；小麦60kg，总价值120元；芝麻20kg，总价值80元；大豆50kg，总价值75元），为了让箱子中所装物品的总价值最大，在箱子中要选择哪些物品，每种物品的要装多少？
这个问题我们可以直接算出来，在箱子装20kg芝麻、30kg玉米、50kg小麦。
代码实现如下：
/**
* 箱子价值最大化
*
* @param w 物品重量
* @param v 物品价值
* @param n 物品数量
* @param m 背包承受重量
*/
public void boxLoading(int[] w, int[] v, int n, int m) {
// 计算每个物品的单价
float[] p = new float[n];
// 记录物品排序后的下标
int[] idxs = new int[n];
for (int i = 0; i < n; i++) {
p[i] = v[i] / (float) w[i];
idxs[i] = i;
}
// 将单价按降序排序
for (int i = 0; i < n; i++) {
// 排序完成标识
boolean flag = false;
for (int j = 0; j < n - i - 1; j++) {
if (p[j] < p[j + 1]) {
float temp = p[j];
p[j] = p[j + 1];
p[j + 1] = temp;
flag = true;
int index = idxs[j];
idxs[j] = idxs[j + 1];
idxs[j + 1] = index;
}
}
if (!flag) {
break;
}
}
// 将重量和总价值降序排序
int[] w1 = new int[n];
int[] v1 = new int[n];
// 每个物品的放到箱子的重量
int[] res = new int[n];
for (int i = 0; i < n; i++) {
w1[i] = w[idxs[i]];
v1[i] = v[idxs[i]];
res[i] = 0;
}
// 箱子剩余可放入重量
int cu = m;
// 计算每个物品要放入重量
for (int i = 0; i < n; i++) {
// 物品重量大于等于可放入的重量
if (w1[i] >= cu) {
// 还有剩余空间
if (cu > 0) {
res[i] = cu;
}
break;
} else {
// 否则，把当前物品全部装入箱子中
cu = cu - w1[i];
res[i] = w1[i];
}
}
// 输出装入箱子的物品的重量
for (int i = 0; i < n; i++) {
int idx = idxs[i] + 1;
System.out.println("第" + idx + "个物品，重量为：" + res[i]);
}
}
2、分糖果
我们有m个糖果和n个孩子（m<n）。每个糖果的大小不等，每个小孩对糖果的需求也是不一样的，如何分配糖，能尽可能满足最多数量的孩子。
我们可以从n个孩子中，抽取一部分分配糖果，让满足的孩子的个数（期望值）是最大的。限制值就是糖果个数m。
我们每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足孩子个数最多的方案。代码实现如下：
/**
* 分糖果
* @param candies 糖果大小
* @param reqs 孩子需求量
* @return 孩子数量
*/
public int divideCandy(int[] candies, int[] reqs) {
int m = candies.length;
int n = reqs.length;
// 对糖果和孩子的需求排序
insertSort(candies);
insertSort(reqs);
// 假设每个小孩只能获得一棵糖果
int[] children = new int[n];
// 记录孩子个数
int count = 0;
int i = 0;
int j = 0;
while (i < m) {
// 糖果的大小要大于等于当前需求才满足
if (candies[i] >= reqs[j]) {
children[j] = reqs[j];
count++;
j++;
}
i++;
}
return count;
}
// 插入排序
private void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int value = arr[i];
int j = i - 1;
for (; j >= 0; j--) {
if (arr[j] > value) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = value;
}
}
3、钱币找零
假设我们有1元、2元、5元、10元、20元、50元，100元这些面额的纸币，它们的张数分别是c1、c2、c5、c20、c50、c100。我们现在要用这些钱来支付K元，最少要用多少张纸币呢？
在贡献相同期望值（纸币数目）的情况下，我们希望多贡献点金额，这样就可以让纸币数量更少，这是一种贪心算法的解决思路。代码如下：
/**
* 零钱找零
*
* @param moneys 钱面额
* @param amounts 每张面额数量
* @param k 要支付多少钱
* @return 要找多少张钱
*/
public int coinChange(int[] moneys, int[] amounts, int k) {
int n = moneys.length;
// 记录金额
int cur = 0;
// 记录钱币的数量
int count = 0;
// 记录需要哪些面额
int[] m1 = new int[n];
// 记录需要面额的张数
int[] a1 = new int[n];
for (int i = n - 1; i >= 0; i--) {
// 从最大的钱币开始判断是否满足
int money = moneys[i];
m1[i] = money;
// 如果钱币的面积大于k,直接到下一个
if (money > k) {
continue;
}
int amount = amounts[i];
int tmep = 0;
// 累计的钱加上当前面额小于等于k，说明这张钱可以找出去
while (cur + money <= k && amount >= 0) {
cur += money;
amount--;
count++;
tmep++;
}
a1[i] = tmep;
// 零钱已经找好了
if (cur == k) {
break;
}
}
return count;
}
4、区间覆盖
假设我们有n个区间，区间的起始端点和结束端点分别是【l1, r1]，[l2, r2]，[l3, r3]，...，[ln, rn]。从这n个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？
比如，区间：[6, 8], [2, 4], [3, 5], [1,5], [5, 9], [8, 10]; 不相交的区别有：[2, 4], [6, 8], [8, 10]
这个处理思想在很多贪心算法问题中都有用到，像任务调度、教师排课。
解决思路：假设这n个区间中最左端点是lmin,最右端点是rmax。我们选择几个不相交的区别，从左到右[lmin, rmax]覆盖上（如下图）。我们按照起始端点从小到大顺序对这几个区间排序。从图可以看出，我们每次选择的时候，左端点跟前面的已经覆盖的区间不重合，右端点又尽量小的，这样可以让剩下的未覆盖区间覆盖尽可能的大，就可以放置更多的区间。
代码实现如下：
/**
* 区间覆盖
*
* @param arr 区间数组
* @return 满足两两不相交区间
*/
public int[][] intervalCoverage(int[][] arr) {
int n = arr.length;
// 对数组按左端点进行排序
selectSort(arr);
int[][] res = new int[n][2];
int left = arr[0][0];
int right = arr[0][1];
// 记录右端点最小的区间
int index = 0;
for (int i = 1; i < n; i++) {
// 判断是否是相交的区间,左端点在区间中,说明相交
if (arr[i][0] >= left && arr[i][0] < right) {
// 判断是右端点小于等于right
if (arr[i][1] <= right) {
right = arr[i][1];
index = i;
}
} else {
// 如果不相交，再以这个区间与下个区间进行比较
left = arr[i][0];
right = arr[i][1];
// 将上一次相交的区间的右端点加到结果中
res[index] = arr[index];
// 更新index
index = i;
}
}
// 如果最后区间就是最小右端点
if (index == n - 1) {
res[index] = arr[index];
}
return res;
}
// 选择排序
private void selectSort(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i; j < arr.length; j++) {
if (arr[min][0] > arr[j][0]) {
min = j;
}
}
int[] temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
5、霍夫曼编码
假设有一个包含1000个字符的文件，每个字符占1个byte(1byte=8bits),存储这1000个字符一共需要8000bits，那有没有节省空间的存储方式呢？
假设通过统计分析发现，这1000个字符只包含6个不同的字符，假设它们分别是a, b, c, d, e, f。而3个二进制位就可以表示8个不同的字符，所以为了尽量减少存储空间，每个字符我们用3个二进制来表示。那存储1000个字符只需要3000bits就可以了。
a(000)、b(001)、c(010)、d(011)、e(100)、f(101)
二进制的存储方式，确实节省了很多空间。不过还更节省存储方式：霍夫曼编码，它是一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在20%~90%之间。
霍夫曼编码是不等长的，每次应该读取1位还是2位、3位等等来解压缩呢？这个问题会导致霍夫曼编码解压缩的时候比较复杂。为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。
我们把字符编码下面这个样子，任何一个字符的编码都不是另一个前缀，在解压缩的时候，每次读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会歧义。经过这种编码压缩之后，这1000个字符只需要2100bits就可以了。
怎么根据字符出现频率的不同，给不同的字符进行不同长度的编码呢？
我们把每个字符看作一个节点，并且附带着频率放到优先队列中。我们从队列中取出频率最小的两个节点A、B，然后新建一个节点C，把频率设置为两个节点的频率之后，并把这个新节点作为A、B节点的父节点。最后再把C节点放入到优先级队列中。重复这个过程，直到队列中没有数据。
现在我们给每一边边上画上一个权值，指向左子节点的边我们统统标记为0，指向右子节点的边，统统标记为1，从根节点到时叶节点的路径就是叶节点对应字符的霍夫曼编码。
