- 1、本文档共5页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
贪心算法解决会场安排问题多处最优服务次序问题(含源代码)
西 安年月日…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i,则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j是相容的。也就是说,当si≥fj或sj≥fi时,活动i与活动j相容。
由于输入的活动以其完成时间的非减序排列,所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说,该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。
算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列,算法只需O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列,可以用O(nlogn)的时间重排。
1.会场安排问题源代码
#include iostream
#include vector
#include algorithm
using namespace std;
struct point
{
int t;
bool f;
};
bool cmp(point x,point y)
{
return x.ty.t;
}
int greedy(vectorpoint x)
{
int max=0,cur=0,n=x.size();
sort(x.begin(),x.end(),cmp);
for(int i=0;in;i++)
{
if(x[i].f)
cur++;
else
cur--;
if(curmax)
max=cur;
}
return max;
}
int main()
{
vectorpoint x;
int n,i;
point temp;
while(cinn,n)
{
for(i=0;in;i++)
{
temp.f=true;
cintemp.t;
x.push_back(temp);
temp.f=false;
cintemp.t;
x.push_back(temp);
}
coutgreedy(x)endl;
x.clear();
}
return 0;
}
2. 多处最优服务次序问题源代码:
#includestdio.h
#includestdlib.h
main()
{
int **window,*timewindow,*array,num,serve,i,j,k,temp;
double min;
printf(请输入等待服务人数\n);
scanf(%d,num);
printf(请输入服务窗口数\n);
scanf(%d,serve);
array = (int *)malloc((num + 1) * sizeof(int));
timewindow = (int *)malloc((serve + 1) * sizeof(int));
window = (int **)malloc((serve + 1) * sizeof(int *));
for(i = 0; i = serve;i++)
window[i] = (int *)malloc((num + 1) * sizeof(int *));
printf(请依次输入服务等待时间\n);
for(i = 1; i = num;i++)
scanf(%d,array[i]);
for(i = 0; i = serve;i++)
{
timewindow[i] = 0;
for(j = 0; j = num; j++)
window[i][j] = 0;
}
for(i = 1; i = num; i++)//排序
{
您可能关注的文档
- 药物分析填空2.doc
- 药物分析--实习报告..doc
- 莲瓣兰的传统种植方法.doc
- 莆田八中高二文科地理期末测试卷.doc
- 菁才中学初二科学竞赛选拨试卷及答案.doc
- 萨克斯《全球视角的宏观经济学》习题详解(第23章遏制高通货膨胀).doc
- 蓝庭西地块院式排屋9-16楼大体积混凝土施工方案.doc
- 蟹爪兰的养殖方法.doc
- 行政职业能力测试真题2006年.doc
- 行车通道侧墙混凝土浇筑方案.doc
- 浙江省临海市白云高级中学2025届高三历史3月月考试题.doc
- 云南拾谷县第一中学2024_2025学年高二物理上学期10月月考试题.doc
- 2025版高考生物总复习第13讲基因的分离定律教案苏教版.doc
- 湖北省黄石实验高中2024_2025学年高一历史下学期期末考试模拟卷.doc
- 通史版2025版高考历史大一轮复习专题七近代化的曲折发展__中日甲午战争至五四运动前4第4讲从维新思想到新文化运动课后达标检测含解析新人教版.doc
- 2024年高考数学考试大纲解读专题04导数及其应用含解析文.doc
- 河南省许汝平九校联盟2024_2025学年高一语文上学期期末考试试题扫描版无答案.doc
- 江西省吉安市吉水县第二中学2024_2025学年高一历史上学期第二次月考试题.doc
- 北京市平谷区2025届高三政治一模考试试题含解析.doc
- 2025届中考物理第四讲物态变化专项复习测试无答案新人教版.docx
文档评论(0)