/**
* 活动选择之贪心解法
* 在上周学习动态规划时已经用动态规划分析了活动选择,有:
* A[i][j] = A[i][k] ∪ {a[k]} ∪ A[k][j]
* c[i][j] = c[i][k] + 1 + c[k][j]
* 将A[i][j]的解分解到两个子集(A[i][k]和A[k][j])的解,如果进一步分析:
* 假设对于任意非空子集S[i][j],设a[m]是S[i][j]中具有最小结束时间的活动即:
* f[m] = min{f[k]: a[k] 属于S[i][j]}
* 于是有新的结论:
*
* 1. 活动a[m]在S[i][j]的某最大兼容活动子集中被使用
* 2. 子问题S[i][m]为空,所以a[m]将使子问题S[m][j]为唯一可能非空的子问题
* 简单证明一下:首先,假设S[i][m]为非空,可设a[k]属于S[i][m],有 s[i] <= s[k] < f[k] <= s[m] < f[m],这说明a[k]具有比a[m]更早的结束时间,这与a[m]的选择相矛盾
* 其次,假设A[i][j]是Sij的最大兼容活动子集,且其元素按照结束时间排序,设a[k]是Aij第一个活动,若a[k]=a[m]则得到结论,
* 若a[k] != a[m],则可构造子集A'[i][j]=A[i][j] ∪ {a[m]} - a[k],因为A[i][j]中各活动兼容即A中的各个活动(除了a[k]子集本身)
* 的开始时间均比a[k]的结束时间大,而a[m]具有比a[k]更小的结束时间,所以在A中的各个活动(除了a[k])的开始时间也必定比a[m]的结束时间大
* 所以,A'[i][j]是兼容的,而A'与A具有相同个数的活动,故A'是包含a[m]的最大活动集合。
* 所以我们只要每一步都选择结束时间最小的a[k]就可以,这就是贪心选择
* @author song
*
*/
代码就比动态规划解法简单多了:
public static List<Integer> greedySelectActivity(int[] s, int[] f, int n){
List<Integer> result = new ArrayList<Integer>();
result.add(1);
int i = 1;
for(int m = 2; m < s.length; ++m){
if(s[m] >= f[i]){
result.add(m);
i = m;
}
}
return result;
}
分享到:
相关推荐
贪心算大实现活动安排问题,算法实现使用图形界面动态显示,程序中用到的排序算法为快速排序
活动安排问题是利用贪心算法有效求解的很好例子。该问题要求高校的安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法,使尽可能多的活动可以兼容的使用某一公共资源
活动选择问题的C#实现 S:1,3,0,5,3,5,6,8,8,2,12 f:4,5,6,7,9,9,10,11,12,14,16 以上是测试数据
贪心算法之最优合并问题
主要是使用贪心算法,实现活动安排的个数最多
附件是一个使用贪心算法解决活动选择问题(也称为会议时间安排问题)的 Java 示例代码。这个问题的目标是选择最大的活动数量,使得活动之间互不重叠。 在这个示例中,我们定义了一个 Activity 类来表示每个活动的...
活动安排问题的动态规划、贪心算法和树搜索算法求解。 比如有一个多媒体教室,现在有四个待举办活动A、B、C、D。A是在8:00到10:00举行,简单记为[8, 10];B是[12, 14];C是[15, 17];D是[11, 19]。为了让尽可能多的...
附件中一个使用贪心算法解决活动选择问题(也称为会议时间安排问题)的 Java 示例代码。这个问题的目标是选择最大的活动数量,使得活动之间互不重叠。 在示例中,我们定义了一个 Activity 类来表示每个活动的开始和...
贪心算法 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法
(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于给定的k个待安排的活动,编程计算...
贪心算法之汽车加油问题
贪心算法贪心算法贪心算法贪心算 背包问题背包问题背包问题
算法设计与分析实验报告,附已通过源码,...1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用图表进行了分析) 6.结论 7.程序源码
贪心算法 背包问题 c语言 绝对无误 运行成功
贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法
贪心算法之会场安排问题,直接可运行,python文件
用贪心算法解单源最短路径问题 明确单源最短路径问题的概念;利用贪心算法解决单源最短路径问题;并通过本例熟悉贪心算法在程序设计中的应用方法。
贪心算法之装箱问题,使用c语言来实现的,贪心算法之装箱问题,使用c语言来实现的,
实验2装箱问题-贪心算法
贪心算法 贪心算法的理解 贪心算法的算法 贪心算法的讲解