🎉 每个不曾起舞的日子都是对生命的辜负
🎉写在前面
期末考试邻近,为了更好的应对《算法设计与分析》这门课程,我把书上以及老师讲过的案例都详细的做一个重现及解剖,让你熟记每一个潜在的考点,希望能给大家帮助。
🎉目录
问题描述
贪心策略
算法设计
代码实现
选择结构体
随机输入会议
按结束时间排序
最终会议确定
结束语
问题描述
设有n个会议的集合C={1,2,…,n},其中每个会议都要求使用同一个资源(如会议室),而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei,且bi < ei 。如果选择了会议i使用会议室,则它在半开区间[bi, ei)内占用该资源。如果[bi, ei)与[bj , ej)不相交,则称会议i与会议j是相容的。会场安排问题要求在所给的会议集合中选出最大的相容活动子集,也即尽可能地选择更多的会议来使用资源。
贪心策略
1、选择最早开始时间且不与已安排会议重叠的会议
2、选择使用时间最短且不与已安排会议重叠的会议
3、选择具有最早结束时间且不与已安排会议重叠的会议
这里我选取第三种方法
算法设计
设有11个会议等待安排,用贪心法找出满足目标要求的会议集合。这些会议按结束时间的非减序排列如表所示
11个会议按结束时间的非减序排列表:
代码实现
#include <iostream>
#include "会场安排.h"
#define n 11
struct meeting{
int B;//开始时间
int E;//结束时间
};
using namespace std;
int main()
{
meeting M[n] = { {8,11}, {8,12}, {2,13}, {12,14}, {1,4},
{3,5}, {0,6}, {5,7}, {3,8}, {5,9}, {6,10} };
for(int i=0;i<n;i++)
for(int j=0;j<n-i-1;j++)
if (M[j].E > M[j + 1].E) {
meeting T;
T = M[j]; M[j]= M[j+ 1]; M[j+1]= T;
}
int allowedTime = 0;
for (int i = 0,j=0; i < n; i++) {
if (M[i].B > allowedTime) {
j++;
cout << "安排的第"<<j<<"个会议号是 " << i+1 <<" 此会议开始时间为:" << M[i].B
<<" 此会议结束时间是:" << M[i].E << endl;
allowedTime = M[i].E;
}
}
}
选择结构体
定义meeting结构体,只设置会议开始时间B和结束时间E即可。
随机输入会议
n 为11
meeting M[n] = { {8,11}, {8,12}, {2,13}, {12,14}, {1,4},
{3,5}, {0,6}, {5,7}, {3,8}, {5,9}, {6,10} };
按结束时间排序
冒泡排序实现即可:
for(int i=0;i<n;i++)
for(int j=0;j<n-i-1;j++)
if (M[j].E > M[j + 1].E){
meeting T;
T = M[j]; M[j]= M[j+ 1]; M[j+1]= T;
}这里的中间变量必须设置为 meeting 类型,以便于将会议的所有属性都交换
最终会议确定
int allowedTime = 0;
for (int i = 0,j=0; i < n; i++) {
if (M[i].B > allowedTime) {
j++;
cout << "安排的第"<<j<<"个会议号是 " << i+1 <<" 此会议开始时间为:" << M[i].B
<<" 此会议结束时间是:" << M[i].E << endl;
allowedTime = M[i].E;
}
}
先将会议开始时间设置为0,只要把按结束时间升序排列的第一个大于0的开始时间加到第一个内容哦即可,随后将第一个会议的结束时间设置为allowedTime,产生下一个不与第一个会议时间冲突的会议;然后自己加点输出语句,美观的运行出来结果就好了。
文章来源:https://www.toymoban.com/news/detail-472429.html
结束语
这算是贪心法第一个案例,也是比较好理解的一个案例,希望大家分析后都能有自己的收获,下篇博客再见,觉得好就鼓励鼓励博主吧文章来源地址https://www.toymoban.com/news/detail-472429.html
到了这里,关于<算法>贪心策略设计并解决会场安排问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!