当前位置：首页 > news >正文

贪心算法(Java版本)

news 来源：原创 2024/11/18 23:21:28

一、贪心算法

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;
	}

}