文档章节

最优服务次序问题 和 汽车加油问题

Cynthia_x
 Cynthia_x
发布于 2016/11/21 19:20
字数 1923
阅读 44
收藏 0
点赞 0
评论 0

1. 最优服务次序问题

问题描述: 设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1≦i ≦n 。共有s处可以提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小平均等待时间是n个顾客等待服务时间的总和除以n。

算法设计:对于给定的n个顾客需要的服务时间,计算最优服务次序。

数据输入:由文件input.txt给出输入数据。第一行是正整数n,表示有n个顾客。接下来的1行中,有n个正整数,表示n个顾客需要的服务时间。

结果输出:将计算的最小平均等待时间输出到文件output.txt中。

          输入文件示例                                       输出文件示例

          input.txt                                              output.txt

          10                                                          532.00

          56 12 1 99 1000 234 33 55 99 812

问题分析:假设原问题为T(先假设只有一个服务点),我们已知某个最优服务系列,即最优解为 A={t(1),t(2),….t(n)} (其中t(i)为第i个用户需要的服务时间),则每个用户等待时间为: T(1)=t(1);T(2)=t(1)+t(2);...T(n)=t(1)+t(2)+t(3)+…+t(n);则总等待时问,即最优值为: 

TA=T(1)+T(2)+T(3)+...+T(n)=n*t(1)+(n-1)*t(2)+…+(n+1-j)*t(i)+…+2*t(n-1)+t(n);由于平均等待时间是n个顾客等待时间的总和除以n,故本题实际上就是求使顾客等待时间的总和最小的服务次序。

贪心策略: 最短服务时间优先,先将服务时间排序,然后注意后面的等待服务时间既包括等待部分,也包括服务部分。对服务时间最短的顾客先服务的贪心选择策略,首先对需要服务时间最短的顾客进行服务,即做完第一次选择后,原问题T变成了需对n-1个顾客服务的新问 题T'。新问题和原问题相同,只是问题规模由n减小为n-1。基于此种选择策略,对新问题T',选择n-1顾客中选择服务时间最短的先进行服务,如此进行 下去,直至所有服务都完成为止 。 

算法实现: 采用最短服务时间优先的贪心策略。首先将每个顾客所需要的服务时间从小到大排序。然后申请2个数组: st[]是服务数组,st[j]为第j个队列上的某一个顾客的等待时间;su[]是求和数组,su[j]的值为第j个队列上所有顾客的等待时间。

算法复杂性分析 :  程序主要是花费在对各顾客所需服务时间的排序和贪心算法,即计算平均服务时间上面。其中,贪心算法部分只有一重循环影响时间复杂度,其时间复杂度为O(n):而排序算法的时间复杂度为O(nlogn)。因此,综合来看算法的时间复杂度为O(nlogn)。

代码实现:

#include<iostream>   
#include <vector>   
#include<algorithm>  

using namespace std;   
using std::vector;   
  
double greedy(vector<int>x,int s){   
    vector<int>st(s+1,0);  
    vector<int>su(s+1,0);    
    int n=x.size();    
    sort(x.begin(),x.end());    
    int i=0,j=0;      
    while(i<n){  
        st[j]+=x[i];     
        su[j]+=st[j];     
        i++;  
        j++;     
        if(j==s)j=0;   
    }   
    double t=0;  
    for(i=0;i<s;i++)   
        t+=su[i];   
    t/=n;   
    return t;  
}  
int  main(){  
    int n;//等待服务的顾客人数    
    int s;//服务点的个数    
    int i;    
    int a;     
    int t;//平均服务时间    
    vector<int>x;     
    cout<<"请输入顾客的人数: "<<endl;    
    cin>>n;     
    cout<<"请输入服务点的个数: "<<endl;    
    cin>>s;     
    cout<<"请输入每个顾客需要服务的时间: "<<endl;   
    for(i=1;i<=n;i++){  
        cout<<"第"<<i<<"顾客:  "<<endl;   cin>>a;   x.push_back(a);   
    }   
   t=greedy(x, s);   
   cout<<"最小平均等待时间为: "<<t<<endl;   

运行结果:

2. 汽车加油问题

问题描述:一辆汽车加满油后,可行使nkm。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油才能使加油次数最少。并证明算法产生一个最优解。

算法设计:对于给定的n和k个加油站位置,计算最少加油次数。

数据输入:由文件inpput.txt给出输入数据。第1行有2个正整数n和k,表示汽车加满油后可行驶nkm,且旅途中有k个加油站。接下来的1行中,有k+1个整数,表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地,汽车已加满油。第k+1个加油站表示目的地。

结果输出:将计算的最少加油次数输出到文件output.txt.如果无法到达目的地,则输出”No Solution!”。

        输入文件示例                          输出文件示例

        input.txt                                output.txt

        7 7                                             4

        1 2 3 4 5 6 6

问题分析: 有几种情况:设加油次数为k,每个加油站间距离为a[i];i=0,1,2,3……n 

(1)始点到终点的距离小于n,则加油次数k=0。

(2)始点到终点的距离大于n。

     A  加油站间的距离相等,即a[i]=a[j]=L=N,则加油次数最少k=n;    

     B  加油站间的距离相等,即a[i]=a[j]=L>N,则不可能到达终点;   

     C 加油站间的距离相等,即a[i]=a[j]=L<N,则加油次数k=n/N(n%N==0)或

       k=[n/N]+1(n%N!=0); 

     D  加油站间的距离不相等,即a[i]!=a[j],则加油次数k通过以下算法求解。

算法思路:汽车行驶过程中,应走到自己能走到并且离自己最远的那个加油站,在那个加油站加油后再按照同样的方法贪心。

算法实现先检测各加油站之间的距离,若发现其中有一个距离大于汽车加满油能跑的距离,则输出no solution。否则,对加油站间的距离进行逐个扫描,尽量选择往远处走,不能走了就让num++,最终统计出来的num便是最少的加油站数。

算法复杂性分析 想要知道在哪个加油站加油必须遍历所有的加油站,且不需要重复遍历,所以时间复杂度问O(n)。

代码实现:

/*汽车加油问题 
   先检测各加油站之间的距离,若发现其中有一个距离大于汽车加满油能跑的距离,则输出no solution
   否则,对加油站间的距离进行逐个扫描,尽量选择往远处走,不能走了就让num++,最终统计出来的num便是最少的加油站数 
 */ 
   #include <stdio.h>        
    void greedy(int d[],int n,int k){ 
        FILE *fp;    
        int num = 0;     
        for(int i = 0;i <= k;i++){     
            if(d[i] > n){     
                printf("no solution!其中有一个距离大于汽车加满油能跑的距离!\n");     
                return;     
            }     
        }     
        for(int i=0,s=0;i<=k;i++){     
            s += d[i];     
            if(s > n) {     
                num++;     
                s = d[i];     
            }     
        }     
        printf("最少加油次数为:%d\n",num);
        fp=fopen("output.txt","w");
        fprintf(fp,"%d",num);    
    }                  
    int main(){     
        int i,n,k;     
        int d[1000]; 
        FILE *fp;
        fp=fopen("input.txt","r");
        fscanf(fp,"%d%d",&n,&k);
        printf("汽车加满油后可行驶: %d km\n旅途中加油站个数为: %d \n",n,k);    
        for(i=0;i<=k;i++)
            fscanf(fp,"%d",&d[i]);       
        greedy(d,n,k);
        fclose(fp);  
        return 0;      
    }    

文件input.txt的内容(运行程序前):    output.txt内容(运行程序后):

    

运行结果

© 著作权归作者所有

共有 人打赏支持
Cynthia_x
粉丝 0
博文 8
码字总数 8751
作品 0
西安
前端工程师
蔚来汽车董事长李斌:所有创业中汽车最难,请大家多一点包容

     12月15日,第八届全球新能源汽车大会(GNEV8)在国家会议中心开幕,亿欧汽车受邀参加。 蔚来汽车董事长李斌在开幕论坛上发表主题演讲指出,汽车公司最大难点在于做好用户服务。相对...

深度学习
2017/12/15
0
0
以智能交通化解城市拥堵

  未来,或许仅需按下一个按钮,无人驾驶公共太阳能汽车就可以安全到达目的地;汽车运行路线是经过城市大脑计算出来的,不会堵车,也省去了停车的烦恼……人们对于未来交通的设想,从来没有...

中国机器人
01/09
0
0
全面解决无人驾驶安全问题?网络安全更要注意

自动驾驶汽车可以说是在2016年被讨论得最多的一个话题。自从特斯拉、谷歌、Uber等厂商将无人驾驶概念带到我们面前之后,无论是汽车厂商、科技公司还是普通用户,都梦想着有一天在我们的身边能...

玄学酱
04/18
0
0
“无人”将成常态!这几个赚钱的职业可能要消失了…

当不少人还沉浸在互联网带来的新奇和快感中时,人工智能技术化成一股浪潮袭来了,并迅速地成为了业界聚焦的领域。 去年还被禁锢在实验室的人工智能,今年已经为我们的生活带来了不少“新玩意...

智能编辑
06/14
0
0
大数据“读心术”:你的开车姿势决定了你的买车品质

文/数据侠 包炬强 随着云计算、大数据等各类新技术的兴起普及,汽车行业正迎来一场数据变革。12月7日的线上数据侠实验室中,DT君邀请到了车主服务平台公司“微车”的联合创始人、CTO包炬强,...

大腿君
2017/12/22
0
0
算法设计与分析复习——第四章:贪心算法

第四章:贪心算法 1,贪心算法的设计思想是什么,有什么特点?如果一个问题用贪心算法可以获得全局最优解,那么该问题的求解应满足哪些条件? 答:贪心算法的设计思想是在对问题求解时,总是...

科技小能手
2017/11/12
0
0
非局部静态数据在多编译单元中的窘境

标题有点拗口,先来解释一下。 静态数据包括: 在namespace内定义的名字空间域变量 √ 在类中被声明为static的类域变量 √ 在函数中被声明为static的局部静态变量 × 在文件中被定义的全局变...

林世霖
2017/12/12
0
0
壳牌与几大车企合作 在欧洲高速部署快充

近期荷兰皇家壳牌公司宣布和几大汽车制造商合作,将在欧洲高速路上建设快速充电桩。目前壳牌与宝马、戴姆勒、福特、大众等几家车厂已经建立了合作。 在2019年将在欧洲比利时、英国、法国、荷...

司宇
2017/11/30
0
0
经典动态规划题若干

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,...

樂天
2016/01/22
54
0
阿里云AI走下PPT :我存在于这六大产业场景

12月20日,阿里北京云栖大会,人工智能成为核心词汇。 阿里巴巴集团资深副总裁阿里云总裁胡晓明回顾称,去年云栖大会北京会场,分享的主题还是阿里对云计算的三个认知——云计算最核心基础概...

吕倩
2017/12/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

python浏览器自动化测试库【2018/7/22-更新】

64位py2.7版本 更新 document_GetResources 枚举页面资源 document_GetresourceText 获取指定url的内容 包括页面图片 下载地址下载地址 密码:upr47x...

开飞色
18分钟前
20
0
关于DCL双重锁失效及解决方案

关于DCL双重锁失效及解决方案 Double Check Lock (DCL)实现单例 DCL 方式实现单例的优点是既能够在需要时才初始化单例,又能够保证线程安全,且单例对象初始化后调用getInstance方法不进行...

DannyCoder
24分钟前
0
0
PowerDesigner 16.5 安装配置

PowerDesigner16.5破解版是一款业内领先且开发人员常用的数据库建模工具,PowerDesigner可以从物理和概念两个层面设计数据库,方便用户制作处清晰直观的数据流程图和结构模型,欢迎有需要的朋...

Gibbons
49分钟前
0
0
mac Homebrew 指令积累

1通用命令 brew install [包名] //安装包 brew list //列举安装的包 brew info [包名] // 显示安装包的详细信息 mysql 相关 #启动mysql 服务 brew service start mysql my...

Kenny100120
今天
0
0
前端Tips: 创建, 发布自己的 Vue UI 组件库

创建, 发布自己的 Vue UI 组件库 前言 在使用 Vue 进行日常开发时, 我们经常会用到一些开源的 UI 库, 如: Element-UI, Vuetify 等. 只需一行命令, 即可方便的将这些库引入我们当前的项目: n...

ssthouse_hust
今天
1
0
大数据教程(2.13):keepalived+nginx(多主多活)高可用集群搭建教程【自动化脚本】

上一章节博主为大家介绍了目前大型互联网项目的keepalived+nginx(主备)高可用系统架构体系,相信大家应该看了博主的文章对keepalived/nginx技术已经有一定的了解,在本节博主将为大家分享k...

em_aaron
今天
4
0
Git 2.18版本发布:支持Git协议v2,提升性能

在最新的官方 Git 客户端正式版2.18中添加了对 Git wire 协议 v2 的支持,并引入了一些性能与 UI 改进的新特性。在 Git 的核心团队成员 Brandon Williams 公开宣布这一消息前几周,Git 协议 ...

六库科技
今天
0
0
Java8新特性之接口

在JDK8以前,我们定义接口类中,方法都是抽象的,并且不能存在静态方法。所有的方法命名规则基本上都是 public [返回类型] [方法名](参数params) throws [异常类型] {}。 JDK8为接口的定义带...

developlee的潇洒人生
今天
0
0
aop + annotation 实现统一日志记录

aop + annotation 实现统一日志记录 在开发中,我们可能需要记录异常日志。由于异常比较分散,每个 service 方法都可能发生异常,如果我们都去做处理,会出现很多重复编码,也不好维护。这种...

长安一梦
今天
2
0
将博客搬至CSDN

AHUSKY
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部