算法設(shè)計(jì)(eclipse編寫貪心算法設(shè)計(jì)活動(dòng)安排)

《算法設(shè)計(jì)(eclipse編寫貪心算法設(shè)計(jì)活動(dòng)安排)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、陜西師大計(jì)科院2009級《算法設(shè)計(jì)與分析》課程論文集算法設(shè)計(jì)（貪心算法解決活動(dòng)安排）設(shè)計(jì)者：朱亞君貪心算法的計(jì)算過程如下圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。圖1貪心算法的計(jì)算過程圖若被檢查的活動(dòng)i的開始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。?貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動(dòng)安排問題，貪心算法卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)

2、論可以用數(shù)學(xué)歸納法證明。-3-陜西師大計(jì)科院2009級《算法設(shè)計(jì)與分析》課程論文集附錄：貪心算法的實(shí)現(xiàn)具體程序如下：//貪心算法實(shí)現(xiàn)代碼n為活動(dòng)個(gè)數(shù)s為活動(dòng)開始起始時(shí)間隊(duì)列f為活動(dòng)結(jié)束隊(duì)列A為已選入集合importjava.util.Scanner;publicclassa{/***@paramargs*/staticvoidGreedySelector(ints[],intf[],booleanA[]){//第一個(gè)活動(dòng)為結(jié)束時(shí)間最早進(jìn)入選入隊(duì)列intn=s.length;A[1]=true;intj=2;for(

3、inti=2;i=f[j]){A[i]=true;j=i;}elseA[i]=false;}}staticvoidpaixu(ints[],intf[])//進(jìn)行以結(jié)束時(shí)間的大小排序{intn=s.length;intm;for(inti=0;if[j+1]){m=f[j];f[j]=f[j+1];f[j+1]=m;//終止時(shí)間如果前一個(gè)大于后一個(gè)就交換位置-3-陜西師大計(jì)科院2009級《算法設(shè)計(jì)與分析》課程論

4、文集m=s[j];s[j]=s[j+1];s[j+1]=m;//起始時(shí)間也同時(shí)進(jìn)行交換位置}}}staticvoidOutput(booleana[],ints[],intf[]){intt=0;System.out.println("可以安排的活動(dòng)有以下幾個(gè)！");for(inti=0;i

5、),");t++;}}System.out.println("；最多可以安排的活動(dòng)是"+t+"個(gè)。");}publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubScannerin=newScanner(System.in);System.out.print("請輸入有幾場活動(dòng)！");intn=in.nextInt();ints[]=newint[n+1];System.out.println("請輸入每場活動(dòng)的開始時(shí)間（用空格隔開，以回車結(jié)

6、束）");for(inti=1;i<=n;i++)s[i]=in.nextInt();intf[]=newint[n+1];System.out.print("請輸入每場活動(dòng)的結(jié)束時(shí)間（用空格隔開，一回車結(jié)束）");for(intj=1;j<=n;j++)f[j]=in.nextInt();booleana[]=newboolean[12];paixu(s,f);GreedySelector(s,f,a);Output(a,s,f);}}-3-