貪心算法解決會(huì)場(chǎng)安排問題、多處最優(yōu)服務(wù)次序問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 西 安 郵 電 大 學(xué) （計(jì)算機(jī)學(xué)院）課內(nèi)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 貪心算法 專業(yè)名稱： 計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)： 學(xué)生姓名： 學(xué)號(hào)（8位）： 指導(dǎo)教師： 實(shí)驗(yàn)日期： 2014年5月22日1 實(shí)驗(yàn)?zāi)康募皩?shí)驗(yàn)環(huán)境 實(shí)驗(yàn)?zāi)康模和ㄟ^實(shí)際應(yīng)用熟悉貪心算法，并解決會(huì)場(chǎng)安排問題、多出最優(yōu)服務(wù)次序問題 實(shí)驗(yàn)環(huán)境：Visual C+ 6.0二. 實(shí)驗(yàn)內(nèi)容1.會(huì)場(chǎng)安排問題. 假設(shè)要在足夠多的回廠里安排一批活動(dòng)，并希望使用盡可能少的會(huì)場(chǎng)，設(shè)計(jì)一個(gè)有效的貪心算大進(jìn)行安排（這個(gè)問題實(shí)際上是注明的圖著色問題。若將每一個(gè)活動(dòng)作為圖的一個(gè)頂點(diǎn)，不相容活動(dòng)間用邊相連。使相鄰頂點(diǎn)著有不同顏色的最小著色數(shù)，

2、相應(yīng)于要找的最小會(huì)場(chǎng)數(shù)）2.多處最優(yōu)服務(wù)次序問題設(shè)有n個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。顧客i需要的服務(wù)時(shí)間為ti，1<=i<=n。共有s處可以提供此項(xiàng)服務(wù)。應(yīng)如何安排n個(gè)顧客的服務(wù)次序才能使平均等待時(shí)間達(dá)到最小？平均等待時(shí)間是n個(gè)顧客等待服務(wù)時(shí)間的總和除以n。三 方案設(shè)計(jì)1、設(shè)有n個(gè)活動(dòng)的集合E=1,2,n，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si <fi 。如果選擇了活動(dòng)i，則它在半開時(shí)間區(qū)間si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交

3、，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說，當(dāng)sifj或sjfi時(shí)，活動(dòng)i與活動(dòng)j相容。由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。 1.會(huì)場(chǎng)安排問題

4、源代碼#include <iostream>#include <vector>#include <algorithm>using namespace std;struct point int t; bool f;bool cmp(point x,point y) return x.t<y.t;int greedy(vector<point> x) int max=0,cur=0,n=x.size(); sort(x.begin(),x.end(),cmp); for(int i=0;i<n;i+) if(xi.f) cur+; els

5、e cur-; if(cur>max) max=cur; return max; int main() vector<point> x; int n,i; point temp; while(cin>>n,n) for(i=0;i<n;i+) temp.f=true; cin>>temp.t; x.push_back(temp); temp.f=false; cin>>temp.t; x.push_back(temp); cout<<greedy(x)<<endl; x.clear(); return 0;2.

6、 多處最優(yōu)服務(wù)次序問題源代碼：#include<stdio.h>#include<stdlib.h>main()int *window,*timewindow,*array,num,serve,i,j,k,temp;double min;printf("請(qǐng)輸入等待服務(wù)人數(shù)n");scanf("%d",&num);printf("請(qǐng)輸入服務(wù)窗口數(shù)n");scanf("%d",&serve);array = (int *)malloc(num + 1) * sizeof(int)

7、;timewindow = (int *)malloc(serve + 1) * sizeof(int);window = (int *)malloc(serve + 1) * sizeof(int *);for(i = 0; i <= serve;i+) windowi = (int *)malloc(num + 1) * sizeof(int *);printf("請(qǐng)依次輸入服務(wù)等待時(shí)間n");for(i = 1; i <= num;i+) scanf("%d",&arrayi);for(i = 0; i <= serve;

8、i+) timewindowi = 0; for(j = 0; j <= num; j+) windowij = 0;for(i = 1; i <= num; i+)/排序 for(k = i,j = i + 1; j < num; j+) if(arrayj < arrayk) k = j; temp = arrayk; arrayk = arrayi; arrayi = temp;for(i = 1; i <= num; i+) for(k = 1,j = 2; j <= serve;j+) if(timewindowk > timewindowj

9、) k = j; timewindowk +=arrayi; windowk+windowk0 = arrayi; for(min = 0.0,i = 1; i <= serve;i+) for(j = 1; j <= windowi0;j+) min += windowij * (windowi0 - j + 1); min /= num; printf("n此方案最優(yōu)服務(wù)次序?yàn)?fn",min); getch();4 運(yùn)行結(jié)果 1.2.五心得體會(huì) 通過本次實(shí)驗(yàn)，我了解了貪心算法的性質(zhì)與解題思路。會(huì)場(chǎng)安排問題和多出最優(yōu)服務(wù)次序問題很好的利用了貪心算法，我進(jìn)一步理解了貪心算法的性