貪心法解活動安排問題(計算機(jī)算法設(shè)計與分析)

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

1、實驗報告課程名稱：算法設(shè)計與分析實驗名稱：貪心法解活動安排問題任課教師：張錦雄專業(yè)：計算機(jī)科學(xué)與技術(shù)班級:2007級1班學(xué)號：姓名：藍(lán)冠恒完成日期：2011年1月12日一、實驗?zāi)康模赫莆肇澬姆ń饣顒影才艈栴}的原理，并能夠按其原理編程實現(xiàn)對輸入的活動時間段進(jìn)行合理安排，加深對貪心法解活動安排問題的理解。二、主要實驗內(nèi)容及要求：1．要求按貪心法求解問題；2．要求讀文本文件輸入活動安排時間區(qū)間數(shù)據(jù)；3．要求顯示結(jié)果。三、實驗環(huán)境和工具：操作系統(tǒng):win7操作系統(tǒng)開發(fā)工具：eclipse3.4、jdk1.6開發(fā)語言：java四、實驗結(jié)果與

2、結(jié)論：（經(jīng)調(diào)試正確的源程序和程序的運(yùn)行結(jié)果）1、源代碼：packagecn.lgh;importjava.io.BufferedReader;importjava.io.FileReader;importjava.io.IOException;importjava.io.InputStreamReader;/***貪心法解活動安排問題。*@author藍(lán)冠恒*/publicclassGreedySelector{publicintstartTimes[];//活動起始時間點數(shù)組publicintendTimes[];//活動結(jié)束時

3、間點數(shù)組publicbooleanresultFlags[];//被選活動標(biāo)識數(shù)組publicStringactivRegions="";//活動時間區(qū)間字符串publicStringresult="";//結(jié)果字符串/***構(gòu)造方法*/publicGreedySelector(){}/***構(gòu)造方法*@paramstartTimes*活動起始時間數(shù)組*@paramendTimes*活動結(jié)束時間數(shù)組*/publicGreedySelector(intstartTimes[],intendTimes[]){this.startTim

4、es=startTimes;this.endTimes=endTimes;}//貪心算法具體實現(xiàn)過程privateintgreedySelector(){intn=startTimes.length;resultFlags[0]=true;intj=0;intcount=1;for(inti=1;i=endTimes[j]){resultFlags[i]=true;j=i;count++;}else{resultFlags[i]=false;}}returncount;}//按活動

5、結(jié)束時間非遞減排序privatevoidsort(){inttmp;intn=startTimes.length;for(inti=0;iendTimes[j+1]){tmp=endTimes[j];endTimes[j]=endTimes[j+1];endTimes[j+1]=tmp;tmp=startTimes[j];startTimes[j]=startTimes[j+1];startTimes[j+1]=tmp;}}}}/*

6、**從文件中獲取被安排活動的時間段，并用貪心算法對其選擇。*@paramfilePath*文件路徑*@throwsIOException*/publicvoidgreedyFromFile(StringfilePath)throwsIOException{Stringline;BufferedReaderin=newBufferedReader(newFileReader(filePath));line=in.readLine().replaceAll("","");while(line!=null){activRegions+=

7、line;line=in.readLine();}doGreedyAction();}/***從控制臺中讀取被安排活動的時間段，并用貪心算法對其選擇。*@throwsException*/publicvoidgreedyFromConsole()throwsException{Stringinput;finalStringform="[5，6]、[3，2]、[10，23]";BufferedReaderin=newBufferedReader(newInputStreamReader(System.in));do{System.o

8、ut.println("請輸入活動時間區(qū)間(退出請按數(shù)字鍵1)，格式如："+form);input=in.readLine().trim();}while(input.equals(""));if(input.equals("1")){return