/**
* 活动选择之贪心解法
* 在上周学习动态规划时已经用动态规划分析了活动选择,有:
* 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;
}
分享到:
相关推荐
活动选择问题是计算机科学中经典的贪心算法应用案例,主要目标是从一系列有时间限制的活动中选出最多数量的不冲突活动。在这个问题中,每个活动都有一个开始时间(S[i])和结束时间(f[i])。我们的任务是找到一组...
### 贪心算法在活动安排问题中的应用 #### 一、引言 在计算机科学领域,贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过这种方式找到全局最优解...这种简单而优雅的解决方案展示了贪心算法的强大之处。
本资料包"贪心算法之最优合并问题.zip"显然是针对贪心算法在合并问题中的应用进行深入探讨,特别提到了Python编程语言的实现。 首先,我们要理解贪心算法的基本思想。在解决一个问题时,贪心算法不考虑全局最优解,...
贪心算大实现活动安排问题,算法实现使用图形界面动态显示,程序中用到的排序算法为快速排序
总结,贪心算法在解决活动安排问题时,通过优先选择结束时间最早的活动,能够在许多情况下找到一个接近最优的解决方案。虽然这种策略不能保证总能得到全局最优解,但在实际应用中,由于其简单高效,常常被用来快速...
主要是使用贪心算法,实现活动安排的个数最多
贪心算法是一种解决问题的方法,它通过每一步都做出局部最优的选择,来期望最终得到全局最优解。 在贪心算法中,我们通常采取一种简单的策略,即在每一步选择当前状态下最好的决策。对于活动安排问题,一个常见的...
### 活动安排问题与贪心算法 #### 一、问题背景与定义 在活动安排问题中,我们面临的情况是需要在一个或多个会场安排一系列活动,目标是最小化所需的会场数量。该问题可以被视为一个图着色问题:如果我们将每个...
附件是一个使用贪心算法解决活动选择问题(也称为会议时间安排问题)的 Java 示例代码。这个问题的目标是选择最大的活动数量,使得活动之间互不重叠。 在这个示例中,我们定义了一个 Activity 类来表示每个活动的...
活动安排问题的动态规划、贪心算法和树搜索算法求解。 比如有一个多媒体教室,现在有四个待举办活动A、B、C、D。A是在8:00到10:00举行,简单记为[8, 10];B是[12, 14];C是[15, 17];D是[11, 19]。为了让尽可能多的...
附件中一个使用贪心算法解决活动选择问题(也称为会议时间安排问题)的 Java 示例代码。这个问题的目标是选择最大的活动数量,使得活动之间互不重叠。 在示例中,我们定义了一个 Activity 类来表示每个活动的开始和...
用贪心算法解单源最短路径问题 在计算机科学和信息技术领域中,单源最短路径问题是指从一个源点到其他顶点的最短路径问题。它是一种典型的图论问题,广泛应用于交通网络、通信网络、计算机网络等领域。贪心算法是...
**贪心算法与旅行商问题(TSP)** 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法策略。它并不考虑整个问题的全局最优解,而是每一步都...
但需要注意的是,并非所有问题都适合使用贪心算法求解,只有满足贪心选择性质和最优子结构性质的问题才可采用贪心算法。 #### 二、背包问题概述 背包问题是一类经典的组合优化问题,其基本形式为:给定一系列物品...
贪心算法 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法
贪心算法是解决这类问题的一种策略,它通过每一步选择局部最优解来期望得到全局最优解。在这个场景中,我们将探讨如何使用Java编程语言,结合贪心算法,来解决背包问题。 首先,我们要理解贪心算法的基本思想。贪心...
在TSP问题中,贪心算法可能会选择每次连接最近未访问的城市,但这种策略并不总是能得出最优解,因为贪心算法没有考虑到全局的最优路径规划。 在VC++环境下,实现TSP问题的贪心算法通常涉及以下步骤: 1. **数据...
贪心算法的基本思想是每次做出在当前状态下看似最优的选择,而不是一开始就考虑整个问题的全局最优解。这种策略是基于一种假设,即通过一系列局部最优的选择,可以逐步构建出全局最优解。然而,并非所有问题都能通过...
贪心算法是一种优化策略,它在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的。在解决背包问题时,贪心算法的应用尤为常见,尤其是对于部分背包问题。 0-1背包问题是最基础...