算法课程设计

当一个问题具有最优子结构性质时，根据其具体情况可以用动态规划算法或者贪心算法来求解。但当问题同时具有贪心选择性质时，贪心算法则通常会给出一个更简单、直观和高效的解法。贪心算法则通常会给出一个更简单、直观和高效的解法。

贪心算法通过一系列的选择来得到一个问题的解，并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。

贪心算法是解决问题的一类重要方法，因其简单、直观和高效而受到人们的重视。特别是对于具有最优子结构和贪心选择性质的一类实际问题，它可以通过一系列局面最优选择来获得整体最优解。

文中首先给出了最优服务次序问题，然后对其进行分析和讨论，并证明了该问题具有贪心选择性质和最优子结构性质，并在此基础上给出了该问题的贪心算法，最后对所提出算法的复杂度进行了分析。

关键词：贪心算法，最优选择，最优服务次序，复杂度。

目录。1 问题描述 1

2 问题分析 2

3 算法设计 4

4 算法实现 5

5 测试分析 6

结论 7参考文献 8

最有服务次序问题：设有n个顾客同时等待同一项服务。顾客i需要的服务时间为ti,1≤i≤n，应如何安排这n个顾客的服务次序才能使平均等待时间达到最小。

平均等待时间是n个顾客等待服务时间的总和除以n。

假设原问题为t，而我们已经知道了某个最优服务系列，即最优解为a=

那么ta-tb=n*[t(1)-t(i)]+n+1-i)*[t(i)-t(i)]=1-i)*[t(i)-t(1)]>0

即ta>tb，这与a是最优服务相矛盾。

故最优服务次序问题满足贪心选择性质。

在进行了贪心选择后，原问题t就变成了如何安排剩余的n-1个顾客的服务次序的问题t’，是原问题的子问题。

若a是原问题t的最优解，则a’=(t(2)．…t(i)…t (n)}是服务次序问题子问题t’的最优解。

证明：假设a’不是子问题t’的最优解，其子问题的最优解为b’，则有tb’因此，tb’+t(1)＜ta’+t(1)=ta ，即存在一个比最优值ta更短的总等待时间，而这与ta为问题t的最优值相矛盾。

从以上贪心选择及最优子结构性质的证明，可知对最优服务次序问题用贪心算法可求得最优解。

#include

using namespace std;

void countingsort(int t,int n,int r,int e,int q)

int i计数排序。

for( i=0;ifor( i=0;i for( i=1;i for( i=n;i>0;i--)将顾客等待时间从小到大排列。

void main()

int i=0,sum=0,n,max=0,u;//n为顾客个数。

float vt,p;

ifstream in(""

if(cout<<"input error!"

对输出设置精度。

in>>n

/new是给指针r分配n长度的空间，设置动态数组r,m，两个数组大小相同。

int *r=new int[n];

int *t=new int[n];

for(i=0;i>t[i];/从文本给等待时间t[i]数组赋值。

for(i=0;iu=maxu为所有顾客中最长的等待时间。

int *q=new int[u+1]; 动态数组用于计数排序，减少排序时间。

countingsort(t,n,r,u+1,q);/调用countingsort（）函数。

for(i=0;i//文件尾：

p=(float)sum;//顾客等待服务时间的总和sum转换成浮点数赋给p

vt=p/n;//计算平均等待时间。

out<法二：

#include

using namespace std;

ifstream in(""

ofstream out(""

int max(int a,int n)

int pos=0;

for(int i=0;ivoid swap(int x,int y)

int temp;

temp=x;x=y;y=temp;

void selectsort(int a,int n)

for(int size=n;size>1;size--)

int j=max(a,size);

swap(a[j],a[size-1]);

int partition(int a,int p,int r)

int i=p,j=r+1,x=a[p];

while(true)

while(a[++i]x);

if(i>=j)break;

swap(a[i],a[j]);

a[p]=a[j];

a[j]=x;

return j;

void quicksort(int a,int p,int r)

if(r-p<=9)

selectsort(&a[p],r-p+1);

else if(pvoid main()

if(cout<<"the is not exist!";

exit(1);

int n;

in>>n;

int *a=new int [n];

for(int i=0;i>a[i];

/文件尾：quicksort(a,0,n-1);

double num=0;

for(i=0;i运行结果：

5 测试分析。

程序主要是花费在对各顾客所需服务时间的排序和贪心算法，即计算平均服务时间上面。其中，贪心算法部分只有一重循环影响时间复杂度，其时间复杂度为0(n)，其时间复杂o(nlogn)。

本文首先给出了最优服务次序问题的最优选择策略，进而证明其所具有的贪心选择性质和最优子结构性质。在此基础上提出了一种最优服务次序问题的贪心解法，并对算法的时间复杂性进行了分析。试验结果验证了所提出算法的有效性。

尽管所提出的算法是对最优服务次序问题提出的，但算法的思想对于其它最优选择问题，同样具有借鉴作用。

算法课程设计

算法课程设计

算法课程设计

算法课程设计

其他用户还读了