贪心法解活动安排问题(计算机算法设计与分析)

实验报告
课程名称：算法设计与分析实验名称：贪心法解活动安排问题任课教师：专业：计算机科学与技术
班级: 20xx 级x班学号：
姓名：完成日期： 20xx年x月xx日
五、实验总结
在做本实验之前，自己看了课本上所列举的贪心法解活动安排问题的代码，代码很简单，很容易理解，于是就按课本的代码实现。

通过几个测试用例测试发现结果不对，后来发现自己忘了进行贪心法的一个前提条件，事先没有按各个活动结束时间对所有活动进行非递减排序，所以才会导致结果错误。

经过修正后，自己真正理解了贪心法解活动安排问题的原理，重新完成本次实验内容也是很顺利，在编程方面没有遇到什么困难。

计算机算法设计与分析第4章贪心算法

4.1 活动安排问题
算法GreedySelector的效率极高。算法GreedySelector的效率极高。当输入 GreedySelector的效率极高的活动已按结束时间的非减序排列时，的活动已按结束时间的非减序排列时，算法只需O(n)的时间安排n个活动， O(n)的时间安排只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。动能相容地使用公共资源。如果所给出的活动未按非减序排列，如果所给出的活动未按非减序排列，可以 O(nlogn)的时间重排的时间重排。用O(nlogn)的时间重排。
O(n)
数组s 数组s和f已按结束时间f的非减序排列
for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { A[i]=true; j=i; } else A[i]=false; }
} //j用以记录最近一次加入到集合中的活动用以记录最近一次加入到集合A中的活动用以记录最近一次加入到集合
4பைடு நூலகம்1 活动安排问题
设待安排的11 11个活动的开始时间和结束时例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：间按结束时间的非减序排列如下：
i S[i] f[i] 1 1 4 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 11 9 8 12 10 2 13 11 12 14
4.1 活动安排问题的最优子结构性质是原问题的一个以贪心选择开始的最优解，若A是原问题的一个以贪心选择开始的最优解，是原问题的一个以贪心选择开始的最优解是活动安排问题E’={i∈E:si≥f1}的则 A’=A-{1}是活动安排问题是活动安排问题 ∈ 的一个最优解。一个最优解。－最优子结构性质证明：如能找到E’的一个解的一个解B’，它包含比A’更多证明：如能找到的一个解，它包含比更多的活动，则将活动1加入中将产生E的一个解加入B’中将产生的一个解B，的活动，则将活动加入中将产生的一个解，它包含比A更多的活动这与A的最优性矛盾更多的活动。的最优性矛盾。它包含比更多的活动。这与的最优性矛盾。

计算机算法设计与分析-贪心算法

2023/10/8
计算机算法设计与分析
4
树的基本性质
连通无回路的图G称为树。树是点比边多一的连通图，G连通且q=p–1 。树是点比边多一的无回路图：G无回路且q=p–1 树若添条边就有回路：G无回路，但对任意的u,
v∈V(G)，若uvE(G)，则G+uv中恰有一条回路树若减条边就不连通：G连通，但对e∈E(G),
图条出且边权该。重回这较路n小中–的1包n条含–边1e必条1。定边该包（回括在路了实中G现必的中有n体个条现顶不为点是n。e个的这边样顶e就点i。得的令到选T’了择={G）T的+。e一1}棵–ei最。小T’生也成是树G的。生成树。又
cc矛K次不要是这((TTr盾选行保连u’’样))s。≤k择=！证通c做a故(cl权因这的T算(是T)必重为或n，法)否定–+较不者T的1c’有可是小能是条(做e图1以G的保无边法) 的G–n证回构呢：的c最–(这路成在？e最1小1条的n树)保，小生–边。，证c生1成(。必条无e成1树)须边回树≤且使构路c包含(这成e的含i有)n树，前了边–？从提e1e1条而下1。。边依
初始化：Path中仅含有源v。
2023/10/8
计算机算法设计与分析
21
最临近算法中的数据结构
图用连接矩阵W[i][j]给出，即W[i][j]为结点i到结点j的权重。
Path[]记录依次连接的城市，p记录当前到达的最后一个顶点，cost为当前路径长度。
如果节点k已经到达，则arrived[k]=true。
3
最小生成树
设G = (V, E)是一个无向连通带权图，即一个网络。E的每条边(v, w)的权为c[v][w]。

算法分析与设计实验二贪心算法

实验二：贪心算法
【实验目的】
应用贪心算法求解活动安排问题。

【实验性质】
验证性实验。

【实验要求】
活动安排问题是可以用贪心算法有效求解的很好的例子。

问题：有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。

求解：安排尽量多项活动在该场地进行，即求A的最大相容子集。

设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下：
将此表数据作为实现该算法的测试数据。

【算法思想及采用的数据结构】
【程序代码】
【运行结果】
【算法分析和心得体会】
附加题：
【实验要求】
需要在某个城市的n个居民区之间铺设煤气管道，则在这n个居民区之间只要铺设n-1条管道即可。

假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同。

选择最优的施工方案能使总投资尽可能少，这个问题即为求网的“最小生成树”问题。

参照以下居民区示意图，使得求解算法为：在可能架设的m条管道中选取n-1条，既能连通n-1个居民区，有使总投资达到“最小”。

网可采用邻接矩阵为存储结构，以定点对（i,j）
应用贪心算法策略，采用普里姆算法或Kruskal算法来求解居民区示意图的最小生成树，采用合适的数据结构。

用C语言或C++语言编写程序代码，选上述居民区示意图中的数据作为测试数据。

并调试输出正确结果。

【算法思想及采用的数据结构】
【程序代码】
【运行结果】
【算法分析和心得体会】。

算法设计与分析第4章贪心算法

•
for (i=0;i<n;i++) {
•
if (d[i].w>c) break;
•
x[d[i].i]=1;
•
opt+=d[i].v;
算时间上界为 O（nlogn）。当然，为了证明算法的正确
•
c-=d[i].w;
性，还必须证明背包
•
}
•
if (i<n){
•
x[d[i].i]=c/d[i].w;
问题具有贪心选择性质。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
14
4.2 贪心算法的基本要素
•
opt+=d[i].w;
•
c -= d[i].w;
•
}
•
return opt;
其中Element类说明为参见本书P115
•}
23
4.3 最优装载
2.贪心选择性质
可以证明最优装载问题具有贪心选择性质。
3.最优子结构性质
最优装载问题具有最优子结构性质。
由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。
7
4.1 活动安排问题
在下面所给出的解活动安排问题的贪心算法greedySelector :
• public static int greedySelector(int [] s, int [] f, boolean a[])

算法设计与分析讲义贪心法

特点
贪心算法在每一步选择时都采取在当前状态下最好或最优（即最有利）的选择，而不考虑可能出现的后果。
贪心算法与动态规划
贪心算法是一种局部最优策略，即每一步选择在当前状态下是最优的，但不一定能够得到全局最优解。
动态规划是一种全局最优策略，通过将问题分解为子问题，逐步求解得到全局最优解。
贪心算法的历史与发展
选择适当的贪心策略
选择适当的贪心策略可以最大程度地减少计算时间。
空间优化
通过优化算法的空间复杂度，减少算法的空间占用，以提高算法的效率。
并行计算
利用并行计算技术，将算法并行化，以提高算法的运行速度。
数据结构优化
使用合适的数据结构可以加快算法的执行速度，如哈希表、堆等。
06
贪心算法的应用扩展
贪心算法的优化策略
总结词
记忆化搜索、动态规划优化、全局状态决策
详细描述
贪心算法虽然能够得到问题的近似解，但在某些情况下可能无法得到最优解。为了提高贪心算法的性能，可以采用一些优化策略，例如记忆化搜索，将已经计算过的状态存储下来，避免重复计算；动态规划优化，将问题分解为子问题，通过解决子问题来解决原问题；全局状态决策，将问题的所有状态作为一个整体来考虑，利用问题的整体性质来得到更好的解。
在资源分配问题中，贪心算法可以用于求解具有单位资源的最大权值
组合问题、分数背包问题等。
05
贪心算法的实现技巧
贪心算法的编程实现
确定贪心策略
根据问题特性确定贪心策略，通常选择最优解或近似最优解。
编码实现
将贪心策略转化为代码实现，通常使用循环和条件语句实现算法。
测试样例
设计测试样例，覆盖各种情况，提高算法的健壮性和正确性。

(算法分析与设计)2.贪心算法

n
wixi
vixi
28.2
31
31.5
...
i1
[算法思路]1).将各物体按单位价值由高到低排序.
2).取价值最高者放入背包.
3).计算背包剩余空间.
4).在剩余物体中取价值最高者放入背包.
若背包剩余容量=0或物体全部装入背包为止
算法设计与分析 > 贪心算法
背包问题的贪心算法
print tour, cost }
*该算法不能求得最优解. 算法的最坏时间复杂性为O(n2)
该问题为NP难问题.
算法设计与分析 > 贪心算法
4.7 多机调度问题
问题:设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理. 作业i所需时间为t i. 约定:任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。要求给出一种作业调度方案，使所给的n 个作业在尽可能短的时间内由m台机器加工处理完成。该问题为NP完全问题.
A complete tree is filled from the left: • all the leaves are on • the same level or • two adjacent ones and • all nodes at the lowest level are as far to the left as possible.
最大相容活动子集(1, 4, 8, 11), 也可表示为等长n元数组:(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1)
算法设计与分析 > 贪心算法
活动安排问题贪心算法
template< class Type > void GreedySelector(int n, Type s[ ], Type f[ ], bool A[] ) { A[ 1 ] = true;

算法设计与分析_ 贪心法(1)_

| I* {1}| > | I {1} | = | I' |
与 I'是关于N' 和C' 的最优解矛盾.
I* 1 I1
I*-{1} I-{1}
I*-{1} I-{1}=I '
不最优
8
小结
• 装载问题是0-1背包的子问题 (每件物品重量为1)，NP难的问题存在多项式时间可解的子问题.
• 贪心法证明：对规模归纳
vi都等于1，轮船载重限制 C 相当于
背包重量限制 b.
2
建模
设 <x1, x2, ... , xn> 表示解向量，xi= 0,1, xi= 1当且仅当第 i 个集装箱装上船
目标函数约束条件
n
max xi
i=1
n
w xi i C
i=1
xi = 0,1 i = 1,2,...,n
3
算法设计
• 贪心策略：轻者优先 • 算法设计：
贪心法的优势：算法简单，时间和空
间复杂性低
8
最优装载问题
最优装载问题
问题：
n 个集装箱1, 2, … , n 装上轮船，集
装箱 i 的重量 wi, 轮船装载重量限制为C, 无体积限制. 问如何装使得上船的集装箱最多？不妨设每个箱子的重
量 wi C.
该问题是0-1背包问题的子问题. 集装
箱相当于物品，物品重量是 wi，价值
实例 v1=1, v2=5, v3=14, v4=18, wi=1, i=1,2,3,4. y=28
最优解：x3=2, x1=x2=x4=0，总重2
fi 4 5 6 7 9 9 10 11 12 13
解：{1, 4, 8}

列举用贪心算法求解的经典问题

列举用贪心算法求解的经典问题
1. 零钱兑换问题：给定一些面值不同的硬币和一个金额，要求用最少的硬币凑出这个金额。

2. 最小生成树问题：给定一个无向带权图，要求用最小的权值构建一棵生成树。

3. 背包问题：给定一些物品和一个背包，每个物品有对应的价值和重量，要求在背包容量限制下，选取物品使得总价值最大。

4. 活动安排问题：有若干个活动需要分配一段时间，每个活动有对应的开始时间和结束时间，要求选取尽可能多的活动，使得任两个安排的活动时间不重叠。

5. 单源最短路径问题：给定一个有向带权图和一个起始节点，要求求出从起始节点到其他所有节点的最短路径。

6. 任务调度问题：有若干个需要完成的任务和多个可执行任务的处理器，要求将任务分配给处理器，使得执行总时间最小。

7. 区间覆盖问题：给定一些区间，要求用尽可能少的区间覆盖整个线段。

8. 哈夫曼编码问题：给定一些字符及其对应的出现概率，要求用最短的编码方式表示这些字符。

实验二贪心算法-最少活动会场安排问题

中原工学院计算机学院实验报告实验项目名称实验二、最少活动会场安排问题课程名称算法设计与分析学生姓名梁斐燕学生学号************所在班级网络14卓越学科专业网络工程任课教师吴志刚完成日期2016年月日实验二最少活动会场安排问题一、实验目的1．掌握贪心算法的基本概念和两个基本要素2．熟练掌握贪心算法解决问题的基本步骤。

3．学会利用贪心算法解决实际问题。

二、实验内容•问题描述：•题目一：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。

设计一个有效的贪心算法来进行安排，试编程实现。

•题目二：一辆汽车加满油后,可行使n千米。

旅途中有若干个加油站。

若要使沿途加油次数最少,设计一个有效算法，指出应在哪些加油站停靠加油。

•数据输入：个人设定，由键盘输入。

•要求：–上述题目任选一做。

上机前，完成程序代码的编写–独立完成实验及实验报告三、实验步骤㈠、数据结构与核心算法的设计描述提示：题目一：参考教材活动安排问题；有关队列操作参考数据结构。

void GreedySelector(int n, int *s, int *f, int *A) {//用集合A来存储所选择的活动A[1] = TURE; //默认从第一次活动开始执行int j = 1; //j记录最近一次加入到A中的活动for (int i = 2; i <= n; i++) { //f[j]为当前集合A中所有活动的最大结束时间//活动i的开始时间不早于最近加入到集合A中的j的时间f[j]if (s[i] >= f[j]) {A[i] = TURE; //当A[i]=TURE时，活动i在集合A中j = i;}else A[i] = FALSE;}}㈡、函数调用及主函数设计㈢程序调试及运行结果分析㈣实验总结在做本实验之前，自己看了课本上所列举的贪心法解活动安排问题的代码，代码很简单，很容易理解，于是就按课本的代码实现。

通过几个测试用例测试发现结果不对，后来发现自己忘了进行贪心法的一个前提条件，事先没有按各个活动结束时间对所有活动进行非递减排序，所以才会导致结果错误。

算法设计与分析动态规划与贪心算法的应用

算法设计与分析动态规划与贪心算法的应用算法设计与分析：动态规划与贪心算法的应用一、引言算法设计与分析是计算机科学中的重要课题之一。

动态规划与贪心算法是常用的解决问题的方法。

本文将分析和探讨动态规划与贪心算法的应用，为读者提供深入了解算法设计与分析的知识。

二、动态规划的应用动态规划是一种将问题拆分为子问题并逐步求解的算法。

它通常用于解决具有重叠子问题性质的问题，通过保存每个子问题的解，避免了重复计算，提高了计算效率。

1. 背包问题背包问题是动态规划中的经典问题之一。

给定一个背包容量和一系列物品的重量和价值，求在背包容量限制下，如何选择物品使得总价值最大。

通过动态规划的思想，我们可以逐步求解子问题，并得到最优解。

2. 最长公共子序列最长公共子序列是算法设计中的另一个经典问题。

对于两个序列，找出它们最长的共同子序列长度。

通过定义状态转移方程，我们可以利用动态规划的方法解决这一问题，提高计算效率。

三、贪心算法的应用贪心算法是一种简单而有效的算法，它通过每一步选择当前最优解来求解整个问题。

贪心算法通常适用于满足最优子结构性质并能通过贪心选择获得全局最优解的问题。

1. 零钱兑换问题零钱兑换问题是贪心算法的一个经典应用。

给定一些面额不同的硬币和一个需要凑齐的金额，求凑齐该金额所需的最少硬币数。

贪心算法可以通过每次选择面额最大的硬币来逐步逼近最优解。

2. 活动选择问题活动选择问题是贪心算法的另一个常见应用。

给定一些活动的开始时间和结束时间，求能参加的最多活动数。

通过贪心选择结束时间最早的活动，我们可以逐步求解最优解。

四、动态规划与贪心算法的比较动态规划与贪心算法都是解决问题的有效方法，但它们在某些方面存在差异。

1. 最优子结构动态规划适用于具有最优子结构性质的问题，而贪心算法则适用于满足贪心选择性质的问题。

最优子结构指子问题的最优解能够构成原问题的最优解，贪心选择性质指每一步都选择当前最优解。

2. 时间复杂度动态规划通常需要保存中间结果，可能会导致较高的空间复杂度。

算法设计与分析-第8章贪心算法

贪心算法
一. 贪心法的基本原理
2. 贪心法的基本思想
贪心算法的几个经典例子： Dijkstra算法：求有向图的单源最短路径（8.2） Kruskal算法：求最小生成树 (8.3) Prim算法：求最小生成树 (8.4)
Huffman树、Huffman编码的算法 (8.5)
贪心算法
一. 贪心法的基本原理
贪心算法
二. 贪心算法设计示例
3. Huffman树 Huffman编码
例：字符集{A, B, C, D, E, F, G, H} , 频数：5, 29, 7, 8, 14, 23, 3, 11.
贪心算法
二. 贪心算法设计示例
4. 最小生成树（Prim算法）
有关概念：生成树：设G=(V, E)为连通图，G的生成树是G的包含其所有顶点的极小连通子图(这里极小的含义是包含的边最少) 。一个连通图的生成树不一定唯一。含n个顶点的连通图的生成树恰含n-1条边。最小生成树：设G=(V, E)为连通网，G的最小代价的生成树称为G的最小生成树。
贪心算法
一. 贪心法的基本原理
2. 贪心法和动态规划
贪心法：每一步的选择不依赖于其子问题的解，选择是局部最优的，但不能保证最终得到最优解。
动态规划：问题的解依赖于其子问题的解，选择是全局最优的，可保证最终得到最优解。
贪心算法
二. 贪心算法设计示例
1. 分数背包问题
问题描述：设有一个容量为 C的背包， n个物品
贪心算法
二. 贪心算法设计示例
6. 多机调度问题该问题的判定问题是一个NP完全问题，该问题本身是一个NP难问题，目前还未找到有效的
算法，但用贪心算法可得到较好的近似最优解。

《计算机算法设计与分析》PPT第四章贪心算法资料

11
假设活动已按结束时间的单调非递减顺序排序 f0≤f1≤f2≤… ≤fn<fn＋1
则，当i≥j时， Sij=φ。
假设存在一活动ak∈Sij，其中i≥j，则在已排的序列中 ai在aj后面。
因fi≤sk<fk≤sj<fj ，与在已排的序列中ai在aj后面的假设相矛盾。
所以，设活动按结束时间的单调非递减顺序排序，子问题空间被用来从sij中选择最大相容活动子集，其中 0≤i<j≤n+1，而且所有其它的sij是空的。
14
步骤2：递归地定义最优解的值设c[i, j]为Sij中最大相容子集中的活动数。当 Sij=φ时，c[i, j] = 0。对于一个非空子集Sij，如果ak在Sij的最大相容子集中被使用，则子问题Sik和Skj的最大相容子集也被使用。从而：
c[i, j] = c[i, k] + c[k, j] + 1
活动安排问题：要在所给的活动集合中选出最大的相容活动子集合。
10
用动态规划方法求解
步骤1：分析最优解的结构特征构造子问题空间 Sij={ ak∈S: fi≤sk<fk≤sj} Sij是S中活动的子集，其中每个活动都在活动ai 结束之后开始，且在活动aj开始之前结束。 Sij包含了所有与ai和aj相容的活动，并且与不迟于ai结束和不早于aj开始的活动相容。此外，虚构活动a0和an+1，其中f0=0, Sn+1=∞。原问题即为寻找S0,n+1中最大相容活动子集。
（5）约束函数constraint：检查解集合中加入一个候选对象是否满足约束条件。例如，在找零钱问题中，约束函数是每一步选择的货币和已付出的货币相加不超过应找零钱。
7
贪心算法的一般框架

算法分析与设计实验二贪心算法

算法分析与设计实验二贪心算法贪心算法（Greedy Algorithm）是一种常用的算法设计方法，其核心思想是在每一步都做出当前情况下最优选择，以期望最终得到全局最优解。

本实验主要介绍贪心算法的原理、应用和分析。

一、贪心算法的原理贪心算法的基本思路是在每一步都做出当前情况下最优选择，并且不考虑当前选择对后续选择的影响。

贪心算法通常采用贪心选择策略和最优子结构两个基本要素。

1.贪心选择策略贪心选择策略是指在每一步都选择当前情况下最优解的策略。

这种策略要求我们能够证明，通过选择当前最优解，可以使得问题的规模减小到原问题的一个子问题，并且该子问题的最优解一定包含在全局最优解中。

2.最优子结构最优子结构是指问题的最优解包含其子问题的最优解。

贪心算法求解问题的过程通常包括两个步骤，选择最优子结构和利用最优子结构得到最优解。

二、贪心算法的应用1.集合覆盖问题集合覆盖问题是指在给定的一组集合中，找出最小的子集合，使得这些子集合的并集包含所有的元素。

贪心算法可以通过每一步选择包含最多未覆盖元素的集合，直到覆盖所有元素为止。

2.挑选活动问题挑选活动问题是指在给定一组活动的起始时间和结束时间，找出最大的相容活动子集合。

贪心算法可以通过每一步选择结束时间最早的活动，之后将该活动与其他相容的活动进行比较，从而得到最大的相容活动子集合。

3.分数背包问题分数背包问题是指在给定一组物品和一个背包容量的情况下，选择部分物品放入背包，使得放入背包的物品总价值最大。

贪心算法可以通过每一步选择单位重量价值最高的物品，直到背包容量不足为止。

三、贪心算法的分析贪心算法通常具有高效性和近似最优性的特点。

由于贪心算法每一步都选择当前最优解，不进行回溯和剪枝的操作，因此贪心算法的时间复杂度较低。

然而，贪心算法并不总能得到问题的最优解，它通常只能得到近似最优解。

贪心算法的近似性证明可以分为两步。

首先，我们需要证明贪心选择策略的正确性，即每一步选择的最优解一定包含在全局最优解中。

算法设计与分析论文(贪心算法)

3.1 贪心选择
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。
物品超出背包容量为止。伪代码如下：
public static void DepWePr(double[][] a, double c, int[] ans) { // depend on
// the // weight // and price double[] w = new double[a[0].length]; // the weight of goods System.arraycopy(a[0], 0, w, 0, w.length); // copy the array
贪心算法
——不在贪心中爆发，就在贪心中灭亡徐晓龙武汉理工大学计算机科学与技术学院软件 ZY1101 班
摘要
本文介绍贪心算法的基本意义以及算法的使用范围，并通过具体的案例来分析贪心算法的具体应用，从而指出其特点和存在问题。关键字：贪心算法，贪心策略，TSP、0/1 背包
引言
我们用了 13 周的时间学完了《算法设计与分析》这本书。这本书中涵盖了大量的常见算法，包括蛮力法、分治法、动态规划法、贪心算法等等。我最有印象的就是贪心算法。贪心算法是一种有合理的数据组织和清晰高效的算法，它简单有效。下面我们来详细解读一下这个算法。

算法设计与分析课件--贪心法-会场安排问题

7
4.1 概述
◼ 贪心法基本思想的推论
❖精髓是“今朝有酒今朝醉”； ❖每个阶段的决策一旦做出就不可更改。不允许回溯。 ❖ 贪心法根贪心法的实际意义和学术价值：
❖可算得上是最接近人们日常思维的一种解题策略； ❖简单、直接和高效； ❖对范围相当广泛的许多实际问题通常都能够产生整
A {1}; //首先选择会议1
k 1;
//已被选择会议集合中最晚结束的会议(k)
for m 2 to n do
if B[m] >= E[k] then //会议m开始时间不小于会议k结束时间
A A ∪ {m}; //将会议m加入到集合A中
k m;
//此时集合A中最晚结束的会议为m
return A;
✓ 因此，会场安排问题的最优子结构性质得到证明
19
12
4.2 会场安排问题
◼ 几种贪心选择策略：
❖选择最早开始时间且不与已安排会议重叠的会议： ✓但如果会议的使用时间无限长，如此选择策略就只能安排1个会议来使用资源。不可行。
❖选择使用时间最短且不与已安排会议重叠的会议： ✓但如果会议的开始时间最晚，如此选择策略也就只能安排1个会议来使用资源。不可行。
❖选择最早结束时间且不与已安排会议重叠的会议： ✓如果选择开始时间最早且使用时间最短的会议，较为理想。而此即结束时间最早的会议。可行。
13
4.2 会场安排问题
◼ 求解步骤：
❖步骤1：初始化，并按会议结束时间非减序排序。
✓开始时间存入数组B，结束时间存入数组E中； ✓按照结束时间的非减序排序E，B需做相应调整； ✓集合A存储解。如果会议i在集合A中，当且仅当其被选中。
6
4.1 概述
◼ 贪心法基本思想的推论

贪心算法解决活动安排问题报告

1.引言：贪心法是一种改进了的分级处理方法。

用贪心法设计算法的特点是一步一步地进行，每一步上都要保证能获得局部最优解。

每一步只考虑一个数据，它的选取满足局部优化条件。

若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。

这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。

贪心算法总是做出在当前看来是最优的选择，也就是说贪心算法并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心算法可以得到最优解或较优解。

2.贪心算法的基本思想及存在问题贪心法的基本思想：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。

当达到某算法中的某一步不能再继续前进时，算法停止。

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

3.活动安排问题：3.1 贪心算法解决活动安排问题学校举办活动的安排问题是用贪心算法有效求解的一个很好例子。

活动安排问题要求安排一系列争用某一公共资源的活动。

用贪心算法可使尽可能多的活动能兼容的使用公共资源。

设有n个活动的集合｛0，1，2，…，n-1｝，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能使用这一资源。

每个活动i都有一个要求使用该资源的起始时间starti和一个结束时间endi，且starti<endi。

如选择了活动i，则它在半开时间区间[starti,endi）内占用资源。

若区间[starti,endi)与区间[startj,endj)不相交，称活动i与活动j是相容的。

也就是说，当start j≥endi或starti≥endj时，活动i与活动j相容。

活动安排问题就是在所给的活动集合中选出最大的相容子活动集合。

贪心法解活动安排问题(计算机算法设计与分析)

合集下载