算法設(shè)計與分析實驗3 貪心法解活動安排問題.doc

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

1、實驗三貪心法解活動安排問題一、實驗內(nèi)容及要求1．要求按貪心法求解問題；2．要求讀文本文件輸入活動安排時間區(qū)間數(shù)據(jù)；3．要求顯示結(jié)果。二、實驗儀器和軟件平臺儀器：普通電腦一臺軟件平臺：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、//活動的開始時間結(jié)束時間String[]name;//活動名稱publicvoidinitData(){JFramef=newJFrame();FileDialogfileDialog=newFileDialog(f);fileDialog.setMode(0);fileDialog.setTitle("打開文件");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("活動安排時間如下：");System.out.println("名稱開始時間結(jié)束時間");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、活動時間2、活動時間安排結(jié)果六.實驗小結(jié)通過這次實驗比較好地理解了貪心法解活動安排問題的算法。貪心算

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