贪心算法
概述
贪心法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的「局部最优解」。但对于一个问题，人们总是喜欢得到这个问题的「整体最优解」，因此，使用贪心法解决问题时，需要证明通过某一「贪心策略」得到的局部最优解，就是当前问题的整体最优解。
这自处我们提出两个概念，最优子结构性、无后效性：
最优子结构性，问题的最优解所包含的子问题的解也是最优的，这样的问题具有最优子结构性。
无后效性，子问题的解确定后就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
贪心法并不是万能的，只能解决具有最有「最优子结构性」的问题，该性质是可使用贪心法或者是动态规划解决问题的关键特征。在解决问题的过程中，贪心策略的选择是最为关键的步骤。
举个简单的例子：小偷偷东西的时候，总是希望自己有限容量背包里装着的是最贵的东西对吧？所以对于小偷最好的做法就是，把眼前看上去最贵的东西全部塞进自己背包里。也就是说对于小偷而言，「拿走眼前最贵的东西」是他的贪心策略，每次将眼前最贵的东西塞进背包里，便是小偷对于每个子问题的求最优解，也就是「局部最优解」。最后，当自己背包装不下了，便不在装了，此时小偷便获得了「整体最优解」。
活动安排问题
设有需要使用固定某一时间段的n个活动，同一时刻只能开始一个活动。每个活动有一开始时间B与结束时间E，其执行时间为E – B，设最早活动执行时间为0。设计一算法，使得所有安排的活动个数最多。
首先考虑的是使用什么方法保存数据以方便我们操作。主要的数据有：活动的数量、活动的编号、每个活动的开始时间、结束时间。
自然使用二维数组或者是两个一维数组都是可以的，在这里我选择使用两个一维数组，可读性更高但排序时的操作相对更加繁琐。对于活动i而言，它的开始时间与结束时间分别为B[i]与E[i]。
假设我们此次的输入为：
int[] B = {0, 2, 4, 5, 7, 1, 2, 9}; // 开始时间
int[] E = {1, 3, 7, 6, 10, 3, 6, 12}; // 结束时间
接下来便是对贪心策略的选择，想要安排更多的活动，应该怎么做呢？以普遍理性而论，一件事情结束得越早，便能有更多剩下的时间去做其他的事。
因此，我们将贪心策略定制为：上一活动结束后，在开始时间比上个活动结束时间晚的所有活动中，选择结束时间最早的作为下一个活动。
对此，我们需要以活动的结束时间为基准，对所有活动进行一次排序方便我们进行选择。排序时需注意同时对两个数组进行处理，排序后的结果为：
int[] B = {0, 1, 2, 2, 5, 4, 7, 9}; // 开始时间
int[] E = {1, 3, 3, 6, 6, 7, 10, 12}; // 结束时间（递增）
我们在增加一个变量preEnd，用于存储当前选择的活动的结束时间，方便下次进行选择，该变量的初始值为最早活动执行时间0。最终我们得到如下代码：
void solve(int[] B, int[] E) {
sort(B, E);
// 记录上一个活动的结束时间
int preEnd = 0;
for (int i = 0; i < B.length; i++) {
if (B[i] >= preEnd) {
System.out.print("(" + B[i] + "," + E[i] + ") ");
preEnd = E[i];
}
}
}
最终的输出为：
(0,1) (1,3) (5,6) (7,10)
对于该算法而言，主要的时间花费在排序上，本人选择使用稳定的归并排序，该排序的时间复杂度为O(nlog2n)，因此整个算法的时间复杂度就是O(nlog2n)。
畜栏保留问题
农场有n头牛，每头牛有特定时间区间[b, e]在一个蓄栏中，每一个畜栏中只能由一头牛。求出满足上述条件的最少蓄栏数量，并且给出一种每头牛被安排的方案。
假设此次我们的输入为：
int n = 8;
int[] B = {0, 2, 4, 5, 7, 1, 2, 9};
int[] E = {1, 3, 7, 6, 10, 3, 6, 12};
理解了上一题的思路后，这一题的大致思路也就出来了，我们可以将每头牛在畜栏的时间相当于活动时间 ，运用求解活动安排问题类似的贪心思路，将所有活动按照结束时间递增排序。
排序后的结果为：
int[] B = {0, 1, 2, 2, 5, 4, 7, 9};
int[] E = {1, 3, 3, 6, 6, 7, 10, 12};
随后，在n头牛中找到一个最大兼容子集，将他们全部安排在一个畜栏中。类似于上题中寻找最多数量的活动安排一样。随后再在剩余未被安排的奶牛中继续寻找下一个最大兼容子集，将他们安排在另一个畜栏中。重复上述步骤，直至所有奶牛都被安排完毕。
不难看出，通过上述步骤得出的最大兼容子集的数量，就是题目中要求的最少畜栏数量。
在编码过程中，为了判断一奶牛是否被选择安排进畜栏，我设置了一个布尔数组进行标记。最终编码结果为：
void solve(int[] B, int[] E) {
// 先以结束时间进行排序
sort(B, E);
// 标记是否已选择
boolean[] select = new boolean[B.length];
// 标记本次循环是否进行过选择
boolean choose;
do {
choose = false;
int preEnd = 0;
for (int i = 0; i < E.length; i++) {
if (B[i] >= preEnd && !select[i]) {
System.out.print("(" + B[i] + "," + E[i] + ") ");
preEnd = E[i];
select[i] = true;
choose = true;
}
}
System.out.println();
} while (choose);
}
最终输出为：
(0,1) (1,3) (5,6) (7,10)
(2,3) (4,7) (9,12)
(2,6)
同理，该算法的时间复杂度与上一题相同。
背包问题
有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
背包问题常见的有01背包问题以及完全背包问题。01背包的特点是，每种物品仅有一件。而完全背包问题中，每种物品都有多件。在这里，我们要解决的是适用贪心法的完全背包问题，01背包更适合使用动态规划解决。
设有编号为1、2、…、n的n个物品，它们的重量分别为w1、w2、…、wn，价值分别为v1、v2、…、vn，其中wi、vi（1≤i≤n）均为正数，背包可以携带的最大重量为W。设计算法以求出背包能装载的最大价值。
假设此次输入为：
int W = 100, n = 5;
double[] w = {10, 20, 30, 40, 50};
double[] v = {20, 30, 66, 40, 60};
接下来便是对贪心策略的选择，既然物品是可分的，我们从物品的集合中选择单位重量价值最大的物品即可，并将背包容量减去该物品的重量。面对剩余的物品和剩余的背包容量，便是下一个子问题，寻找该子问题的最优解与上一步相同。重复上述步骤直至背包容量塞满为止。
为了记录所有物品的单位价值，以及经过排序后仍能找到对应的物品数据，我们新增了一个double数组和一个int数组进行记录。分别是存放单位价值的vm和物品对应下标的index。
随后计算出所有物品的单位价值，存放在vm数组中。index数组则存放物品对应的下标0, 1, 2, 3, 4, 5。然后对vm数组进行排序，注意排序过程中同时处理index数组。排序结果为：
double[] vm = {1.0, 1.2, 1.5. 2.0, 2.2};
int[] index = {3, 4, 1, 0, 2};
随后设置一计数器count，用于存储背包每次被装入后的价值，背包装满后，计数器count的值便是背包能装载的最大价值。代码如下：
void solve(int W, int n, double[] w, double[] v){
// 存放性价比的vm数组与物品对应下标的index数组
double[] vw = new double[n];
int[] index = new int[n];
for (int i = 0; i < w.length; i++) {
vw[i] = v[i] / w[i];
index[i] = i;
}
sort(vw, index);
// max指向最具性价比物品下标数组的下标
int max = index.length - 1;
double count = 0;
while (W > 0) {
// 获取当前尚未装入的物品中，最具性价比物品的下标
int i = index[max];
if (W > w[i]) {
W -= w[i];
count += v[i];
max--;
} else {
count += W * vw[max];
break;
}
}
System.out.println("最大价值：" + count);
}
最终输出结果为：
最大价值：164.0
田忌赛马
这是一道非常经典的贪心算法题目，题目大意为：
齐威王与大将田忌赛马，现在双方各「n」匹马，依次派出一匹马进行比赛。田忌已知所有马的速度值并可以安排出场顺序，如何安排比赛胜场最多。已知各方马的数量n、齐威王每匹马的速度int[] B、田忌每匹马的速度int[] A
这道题的核心思想是，尽可能把每一匹马的价值发挥至最大，把己方每次比试赢得概率拉满。
首先我们对齐王以及田忌的马各自进行一次排序。在这里每次比较皆通过双方快马进行分析，慢马思路大致相同。每次用田忌最快的马与齐王最快的马进行比较，会出现多种不同的情况，根据所有不同的情况来定制相应的贪心策略，不断执行该策略直至所有马匹比赛完毕，统计胜场得出答案。
快马比较时的情况以及相应的策略：
1、田忌的马快
最快的马必然要打败另一匹最快的马，体现田忌这匹快马的最大价值。
策略：二者比赛，胜场++
2、田忌的马慢
这种情况可以说明田忌所有马都不能打败齐王当前的这匹马，则使用田忌最慢的马和它比，同样在输的情况下尽可能削弱齐王的战力。
策略：让田忌当前最慢的马与 齐王当前最快的马比赛，胜场–
3、两匹马速度相等，此时需要再比较双方「最慢的两匹」，会出现两种情况：
①田忌的慢马比齐王的快
慢马能赢一个算一个，以最小的代价取得一场胜利。
策略：双方慢马比赛，胜场++
②田忌的慢马比齐王的慢马慢或相同
当前田忌的这匹慢马是所有马中最慢的，永远会输，则让它与齐王最快的马比，同样在输的情况下尽可能削弱齐王的战力。
策略：田忌慢马与齐王快马比赛，胜场–
算法实现后的代码如下：
void solve(int n, int[] A, int[] B) {
// A与B数组的左右指针，胜场计数器count
int aLeft = 0, bLeft = 0, aRight = n - 1,
bRight = n - 1, count = 0;
// 开始比较
while (aLeft <= aRight) {
if (A[aLeft] > B[bLeft]) {
aLeft++;
bLeft++;
count++;
} else if (A[aLeft] < B[bLeft]) {
aRight--;
bLeft++;
count--;
} else {
if (A[aRight] > B[bRight]) {
aRight--;
bRight--;
count++;
} else {
aRight--;
bLeft++;
count++;
}
}
}
System.out.println("胜场为：" + count);
}
输入：
int n = 3;
int[] A = {92, 83, 71};
int[] B = {95, 87, 74};
输出：
胜场为：1