算法設(shè)計(jì)與分析實(shí)驗(yàn)3 貪心法解活動(dòng)安排問(wèn)題.doc

《算法設(shè)計(jì)與分析實(shí)驗(yàn)3 貪心法解活動(dòng)安排問(wèn)題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、實(shí)驗(yàn)三貪心法解活動(dòng)安排問(wèn)題一、實(shí)驗(yàn)內(nèi)容及要求1．要求按貪心法求解問(wèn)題；2．要求讀文本文件輸入活動(dòng)安排時(shí)間區(qū)間數(shù)據(jù)；3．要求顯示結(jié)果。二、實(shí)驗(yàn)儀器和軟件平臺(tái)儀器：普通電腦一臺(tái)軟件平臺(tái)：WIN-XP+MyEclipse6.0三、源程序importjava.awt.FileDialog;importjava.io.*;importjava.util.ArrayList;importjava.util.List;importjavax.swing.JFrame;publicclassGreedySelectorTest{boolean[]A;int[]S,F;

2、//活動(dòng)的開(kāi)始時(shí)間結(jié)束時(shí)間String[]name;//活動(dòng)名稱publicvoidinitData(){JFramef=newJFrame();FileDialogfileDialog=newFileDialog(f);fileDialog.setMode(0);fileDialog.setTitle("打開(kāi)文件");fileDialog.setVisible(true);Listlist=newArrayList();try{Filefile=newFile(fileDialog.getDirectory()+fileDialog.getFile(

3、));BufferedReaderin=newBufferedReader(newInputStreamReader(newFileInputStream(file)));Strings;while((s=in.readLine())!=null){if(s.length()>1)list.add(s);}in.close();}catch(Exceptione){}f.dispose();//排序list=this.sortList(list);//初始化name=newString[list.size()+1];A=newboolean[list.

4、size()+1];S=newint[list.size()+1];F=newint[list.size()+1];String[]s;for(inti=1;i<=list.size();i++){s=list.get(i-1).toString().split(",");name[i]=s[0].trim();S[i]=Integer.parseInt(s[1].trim());F[i]=Integer.parseInt(s[2].trim());}}publicvoidgreedySelector(intn){A[1]=true;intj=1;fo

5、r(inti=2;i<=n;i++){if(S[i]>=F[j]){A[i]=true;j=i;}elseA[i]=false;}}publicvoidshowResult(){this.greedySelector(A.length-1);System.out.println("活動(dòng)安排時(shí)間如下：");System.out.println("名稱開(kāi)始時(shí)間結(jié)束時(shí)間");for(inti=1;i

6、排序*@paramlist*@return*/publicListsortList(Listlist){String[]s;Objectss;inttemp,temp1;for(inti=0;i

7、t(s[2].trim());if(temp>temp1){ss=list.get(j);list.set(j,list.get(j+1));list.set(j+1,ss);}}}returnlist;}publicstaticvoidmain(Stringargs[]){GreedySelectorTesttest=newGreedySelectorTest();test.initData();test.showResult();}}五．運(yùn)行結(jié)果1、活動(dòng)時(shí)間2、活動(dòng)時(shí)間安排結(jié)果六.實(shí)驗(yàn)小結(jié)通過(guò)這次實(shí)驗(yàn)比較好地理解了貪心法解活動(dòng)安排問(wèn)題的算法。貪心算

8、法在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的