算法设计与分析实验3 贪心法解活动安排问题.doc

《算法设计与分析实验3 贪心法解活动安排问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三贪心法解活动安排问题一、实验内容及要求1．要求按贪心法求解问题；2．要求读文本文件输入活动安排时间区间数据；3．要求显示结果。二、实验仪器和软件平台仪器：普通电脑一台软件平台：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、//活动的开始时间结束时间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("名称开始时间结束时间");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();}}五．运行结果1、活动时间2、活动时间安排结果六.实验小结通过这次实验比较好地理解了贪心法解活动安排问题的算法。贪心算

8、法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的