GDPU 算法分析与设计 天码行空6

本文主要是介绍GDPU 算法分析与设计 天码行空6，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、【实验目的】

（1）熟悉贪心法的设计思想
（2）理解贪心法的最优解与正确性证明之间的关系
（3）比较活动选择的各种“贪心”策略，探讨最优算法。

二、【实验内容】

有n项活动申请使用同一场所，每项活动有一个开始和结束时间，如果任何两个活动不能重叠，问如何选择这些活动，使得被安排活动数量达到最多。
要求至少选择两项“贪心”策略进行比较，其中一个是最优的。建议最优算法参考教材P88的算法4.1.同时可以采用教材例4.1的数据进行验证。

三、实验源代码

💖 Main.java

import java.util.ArrayList;
import java.util.Collections;public class Main
{
//	活动类static class Activity{int start;// 开始时间int end;// 结束时间public Activity(int l, int r){super();this.start = l;this.end = r;}}static int[] s = { 1, 3, 2, 5, 4, 5, 6, 8, 8, 2 };static int[] e = { 4, 5, 6, 7, 9, 9, 10, 11, 12, 13 };static int n;static ArrayList<Activity> list;public static void main(String[] args){n = s.length;list = new ArrayList<>();for (int i = 0; i < n; i++)list.add(new Activity(s[i], e[i]));System.out.println("\n最大活动数：" + greedyByEnd() + "\n");System.out.println("\n最大活动数：" + greedyByStart() + "\n");System.out.println("\n最大活动数：" + greedyByLength() + "\n");}private static int greedyByEnd(){Collections.sort(list, (o1, o2) -> o1.end - o2.end);// 根据结束时间升序排序System.out.println("根据结束时间排序：");return cal();}private static int greedyByStart(){Collections.sort(list, (o1, o2) -> o1.start - o2.start);System.out.println("根据开始时间排序：");return cal();}private static int greedyByLength(){Collections.sort(list, (o1, o2) -> (o1.end - o1.start) - (o2.end - o2.start));System.out.println("根据活动时长排序：");return cal();}private static int cal(){int margin = -1;// 表示当前的最迟的活动结束时间int ans = 0;System.out.println("选择的活动编号：");for (int i = 0; i < n; i++){Activity x = list.get(i);if (x.start >= margin){System.out.print((i + 1) + " ");ans++;margin = x.end;}}return ans;}
}

四、实验结果

根据结束时间排序：
选择的活动：
1 4 8 
最大活动数：3根据开始时间排序：
选择的活动：
1 5 
最大活动数：2根据活动时长排序：
选择的活动：
1 2 4 
最大活动数：3

这篇关于GDPU 算法分析与设计 天码行空6的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---