最优服务次序问题一（贪心算法）

最优服务次序问题（贪心算法）

最近老是布置的作业，在家养病，就把以前写好的整理一下发出来，一起交流学习。

问题描述：设有n个顾客同时等待一项服务，顾客i所需要的服务时间为ti，应如何安排顾客的服务次序，才能使平均等待时间最短？平均等待时间是n个顾客等待服务时间的总和除以n。

贪心算法无非是“此时此刻的最优解问题”，以最优服务次序为例。最优服务次序问题，个人理解，就是理清里面的思路，一般都是按照从小到大的顺序排列，然后在进行依次算出等待时间，如果不止一个服务地点则进行循环算出每一个窗口的等待时间即可（两个及两个服务以上的地点见下一篇blog）。具体算法如下：

以下算法中，需要从文件input.txt中读入数据，然后把数据输出到output.txt中，一开始为了用一下C语言中的文件指针，所以用了用c语言中惯用的手法读入存取数据，用C++的在后面就有
从文件input.txt中输入的内容为如下：

输入到output.txt中的内容如下：

#include <iostream>
#include <algorithm>
#include <cstdio>using namespace std;int main()
{FILE* fp1 = fopen("input.txt","r");FILE* fp2 = fopen("output.txt","w");if(fp1 == NULL || fp2 == NULL){cout << "Opened the file was failed!" << endl;return 0;}int N;fscanf(fp1,"%d",&N);double p[N];for(int i = 0; i < N; i++){fscanf(fp1,"%lf",&p[i]);}sort(p,p + N);double cnt[N];for(int i = 0; i < N; ++i){cnt[i] = p[i];}for(int i = 0; i < N; i++){cout << cnt[i] << " ";}for(int i = 0; i < N; i++){for(int j = 0; j < i; j++){cnt[i] += p[j];}}cout << endl;for(int i = 0; i < N; i++){cout << cnt[i] << " ";}cout << endl;double average = 0;double sum = 0;
//    for(int i = 0; i < N; i++)
//        cout << cnt[i] << " ";//cout << endl;for(int i = 0; i < N; i++){sum += cnt[i];cout << sum << " ";}average = sum / N;fprintf(fp2,"%0.2lf",average);return 0;
}

用c++从文件中进行数据的读取或输入，如果需要，后续会写有关此方面的个人学习见解

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <iomanip>using namespace std;int main()
{ifstream in("input.txt");ofstream out("output.txt");int N;in >> N;double p[N];for(int i = 0; i < N; i++){in >> p[i];}sort(p,p + N);double cnt[N];for(int i = 0; i < N; ++i){cnt[i] = p[i];}for(int i = 0; i < N; i++){for(int j = 0; j < i; j++){cnt[i] += p[j];}}double average = 0;double sum = 0;for(int i = 0; i < N; i++){sum += cnt[i];}average = sum / N;out<<setiosflags(ios::fixed)<<setprecision(2);///保留两位小数out << average;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！