一、贪心算法

1、算法描述

贪心算法（Greedy algorithm），又叫做贪婪算法。

在对问题求解时，不从整体考虑，而是从问题的某一个初始解出发，每一步选择中都采取在当前状态下最好或最优的选择（局部最优解），然后向下一步继续进行，且不能回溯，不断地选取当前最优解，通过局部最优解从而使得问题得到全局最优解。

贪心算法必须要注意：

贪心策略的选择
一定会有一个排序
通过局部最优解能够得到全局最优解

贪心算法不是对所有问题都能得到整体最优解，并且贪心算法是没有固定的模板可以遵循的，每个题目都有不同的贪心策略，所以算法设计的关键就是贪心策略的选择。

贪心策略的选择：选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关（当前的选择，不能影响后续选择对于结果的影响）。

2、贪心算法的设计步骤

可按照算法定义设计：

证明原问题的最优解之一可以由贪心选择得到。
将最优化问题转化为这样一个问题，即先做出选择，再解决剩下的一个子问题。
对每一子问题一一求解，得到子问题的局部最优解。
把子问题的解局部最优解合成原来解问题的一个解。

3、适用范围

一般通过以下问题就可以通过贪心算法解决：

1）针对某个问题有限制值，以及有一个期望的最好结果，通常是从某些数据中选出其中一些，达到最好的结果。
2）一般会有一个排序，找出贡献最大的。
3）举例看贪心是否可以解决。

一般用在任务调度，教师排课等系统。实际上，用贪心算法解决问题的思路，并不总能给出最优解，比如背包问题（动态规划解决）。

4、该算法存在的问题

不能保证求得的最后解是最佳的
不能用来求最大值或最小值的问题
只能求满足某些约束条件的可行解的范围

二、示例

1、最优会议安排问题

最优会议安排问题：

公司有N个同等级的会议需要使用同一个会议室，现在给你这N个会议的开始和结束时间，你怎么样安排才能使会议室最大利用？即安排最多场次的会议？

1）会议类

public class Meeting {private int meNum; // 编号private int startTime; // 开始时间private int endTime; // 结束时间public Meeting(int meNum, int startTime, int endTime) {super();this.meNum = meNum;this.startTime = startTime;this.endTime = endTime;}
// getter setter
}

2）贪心算法

public class MeetingArrange {public static void main(String[] args) {List<Meeting> meetingList = new ArrayList<Meeting>();meetingList.add(new Meeting(1, 2, 8));meetingList.add(new Meeting(2, 9, 10));meetingList.add(new Meeting(3, 8, 9));meetingList.add(new Meeting(4, 9, 15));meetingList.add(new Meeting(5, 14, 16));meetingList.add(new Meeting(6, 17, 19));meetingList.add(new Meeting(7, 16, 20));List<Meeting> res = meetingArrange(meetingList, 0, 4);for (Meeting metting : res) {System.out.println("安排的会议：" + metting);}}/*** 会议安排算法（贪心算法）** @param meetingList*            - 待安排的所有会议* @param curTime*            - 会议当前时间，从一天的0点开始,如果领导要求从8点开始 那curTime=8* @param meetingNum*            - 安排几场会议* @return*/private static List<Meeting> meetingArrange(List<Meeting> meetingList, int curTime, int meetingNum) {List<Meeting> resultList = new ArrayList<>();// 1.对开始时间排序meetingList = meetingList.stream().sorted(Comparator.comparingInt(Meeting::getStartTime)).collect(Collectors.toList());// 记录已安排的会议数量int tempCount = 0;// 2.遍历for (Meeting meeting : meetingList) {// 3.若会议的开始时间比我们当前的要大，则表示可以开if (meeting.getStartTime() >= curTime) {resultList.add(meeting);// 贪心策略：会议每次当前时间变为会议的结束时间curTime = meeting.getEndTime();tempCount++;}if (meetingNum == tempCount) {break;}}return resultList;}}

在这里插入图片描述

2、最优装载问题

最优装载问题：

一条小船用来运输古董到河对岸。假设船的最大载重量为MAXWEIGHT，每件古董的重量为 w_i，怎么能够装载最多数量的古董到船上呢？

public class OptimizedLoading {public static void main(String[] args) {int[] weight = { 4, 10, 7, 11, 3, 5, 14, 2 };int[] res = maxLoading(weight, 30);System.out.println("能装入的古董最大数量为: " + res.length);System.out.println("能装入的古董为: " + Arrays.toString(res));}/*** 装载算法（贪心算法）* * @param weight*            - 带装入的所有古董重量* @param maxWeight*            - 小船的最大载重量* @return 返回装载的古董*/public static int[] maxLoading(int[] weight, int maxWeight) {// 记录装载到小船上古董int resIndex = 0;int[] result = new int[weight.length];// 1.对weight数组进行排序Arrays.sort(weight);// 记录已装载到船上的古董重量int tempWeight = 0;// 2.遍历for (int i = 0; i < weight.length; i++) {// 贪心策略：每次装入最轻者tempWeight += weight[i];// 3.若加入最轻者后还小于载重量，则记录古董if (tempWeight <= maxWeight) {result[resIndex++] = weight[i];} else {// 超重，不能装载break;}}// 返回装载的古董return result;}}