设总共有n项活动(1,2,...,n),并且所有的活动都需要使用同一个会场,而且任意两个活动不能同时使用这个会场。设活动i占用会场的时间是[bi,ei),其中bi<ei(bi是活动i的开始时间,ei是活动的结束时间),那么怎么安排才能使该会场有尽可能多的活动。
1. 最先想到的一个简单模型
有一个容器,容量为K,有n杯水,体积按小到大分别为L1, L2, ..., Ln,要尽可能往容器中倒入最多杯的水,那么我们会一直选当前最小杯的水往里面倒,直到下一杯水倒不完就停止。这个模型好像有点跟上面的活动安排差不多,也有一个给定的范围,也是求最大值。那是不是活动安排的例子中,我们总是去选时间最短的活动呢?
2. 从找最短活动时间考虑
记当前的活动集为S,已选出的活动集为X
(1) 找到活动时间最短的k,把它从活动集S中去除,加入到X集中,同时把和K它不相容的活动从S中去除;
(2) 反复执行过程1,直到x中的活动时间和大于要求的数;
(3) 去除x中最后一个活动,X就是所求的活动集,X中元素的个数就是允许的最大活动个数;
但是这样可以吗? (有问题!!)
如果本题是:有N个时间单位,n项活动进行的时间分别为t1,t2,...,tn,各项活动不一定要在某个时间段完成,那么活动也就没有相容问题,那么可以找时间最短的活动。
然而现在找时间最短是会出问题的:可以看一个例子:
// ######### #### ########
// ###### #####
上图的#是活动的表示,#的多少表示活动时间的长短,上图总共有5个活动,但是若按最短活动时间来选,就只有3个活动,但实际能进行的活动有4个,所以从最短时间来选是有问题的。
3. 从找开始最早的活动选起
这种选法还是会有问题,见下图:
// ####################
// ###### #####
最早活动开始时间考虑的话,只有1个活动,而实际最大可以有两个。
3. 从最早结束的活动找起
这个是可行的,具体证明还在想。。。
简单实现:
public static void main(String[] args) {
int[] b = { 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12 };
int[] e = { 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
int endTime = 0; //当前活动的结束时间,初始化0
for(int i = 0; i < b.length; i++){
if(b[i] >= endTime){
System.out.print(i + " ");
endTime = e[i];
}
}
}
分享到:
相关推荐
### 贪心算法在活动安排问题中的应用 #### 一、引言 在计算机科学领域,贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过这种方式找到全局最优解。活动安排问题(Activity Selection Problem)是贪心...
### 活动安排问题与贪心算法 #### 一、问题背景与定义 在活动安排问题中,我们面临的情况是需要...总结而言,活动安排问题是贪心算法应用的一个典型例子,通过合理的排序和筛选策略,可以有效地减少所需的资源数量。
活动安排问题是一个经典的计算机科学问题,它涉及到优化和时间调度的策略。在这个问题中,我们有一系列的活动,每个活动都有一个开始时间和结束时间。我们的目标是选择尽可能多的活动,使得这些活动之间不发生冲突,...
【活动安排问题(贪心算法)报告】 活动安排问题是一个典型的优化问题,旨在在一个资源有限的情况下,找到最多相容的活动子集。在这个问题中,每个活动都有一个开始时间和结束时间,同一时间只能进行一个活动。贪心...
贪心算大实现活动安排问题,算法实现使用图形界面动态显示,程序中用到的排序算法为快速排序
在活动安排问题中,可能涉及将多个活动按照结束时间排序,每次都选择最早结束的活动,以尽可能多地参加活动。 2. **数据结构**:可能需要使用数组或链表来存储活动信息,如开始时间、结束时间和活动ID等。 3. **...
总结来说,贪心法解决活动安排问题的关键在于:首先对活动按结束时间排序,然后每次选取结束最早的未冲突活动。这种方法虽然简单,但并不保证总能找到全局最优解,而是在特定条件下提供了一个有效且高效的解决方案。...
活动安排问题的动态规划、贪心算法和树搜索算法求解。 比如有一个多媒体教室,现在有四个待举办活动A、B、C、D。A是在8:00到10:00举行,简单记为[8, 10];B是[12, 14];C是[15, 17];D是[11, 19]。为了让尽可能多的...
在"贪心算法活动安排问题"中,我们面临的是一个典型的资源调度问题。假设有一系列的活动(E={1,2,...,n}),它们都需要占用相同的资源,比如一个会议室,而且在任何时刻只能有一个活动使用这个资源。每个活动i都有一...
1. **活动安排问题**:这个问题涉及在一个有限的时间段内安排尽可能多的不冲突的活动。贪心策略通常是选择最早结束的活动,这样可以保证后续活动有更多的可能性被安排。在实际应用中,这可能用于会议调度或资源分配...
主要是使用贪心算法,实现活动安排的个数最多
活动安排问题是一个经典的计算机科学问题,它涉及到在有限的资源约束下如何优化任务调度。贪心算法是解决这类问题的一种有效方法,它通过每一步都选择局部最优解,期望最终能得到全局最优解。在这个问题中,我们将...
在计算机科学与编程的实践中,活动安排问题、汽车加油问题和删数问题是三个具有代表性的经典问题,它们分别涵盖了贪心算法、动态规划以及结合数学策略的算法设计思想。这三个问题不仅在学术研究中占有一席之地,而且...
贪心算法在活动安排问题中的应用 贪心算法是一种常用的近似算法,广泛应用于解决复杂的优化问题。在活动安排问题中,贪心算法可以用于寻找最优解。下面,我们将详细介绍贪心算法在活动安排问题中的应用。 活动安排...
活动安排问题是一个经典的计算机科学问题,常常出现在算法课程中,特别是在哈工程的算法课程中作为实验项目出现。这个问题的核心是优化一系列活动的安排,使得在满足特定约束条件下,尽可能多地完成活动。这个问题在...
活动安排问题是日常生活中常见的问题之一,在会议安排、课程排课、项目调度等多个领域都有广泛的应用。贪心算法以其简单高效的特性,在解决这类问题时尤为突出。本文档将详细介绍如何使用贪心算法解决活动安排问题,...
这里,我们关注的是一个针对新手的活动安排问题,它强调了如何处理活动的开始时间和结束时间,以及它们如何进行排序。在这个场景下,我们通常会使用数据结构来有效地存储和操作这些信息。虽然在描述中提到“没有用...
贪心算法解决活动安排问题 贪心算法是一种常用的近似算法,应用于解决活动安排问题。活动安排问题是指在给定的活动集合中,选择出最大的相容活动子集合,以便使更多的活动得到资源的安排。贪心算法的思路是尽可能多...