資源描述：
《實驗六_分支限界法》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、算法分析與設計實驗報告 學號姓名班級上課地點教師上課時間實驗六分支限界法1.實驗目的1.1掌握分支限界法的設計思想；1.2理解分支限界法的剪枝搜索策略；1.3掌握分支限界法的算法框架；1.4學會利用分支限界法解決實際問題。2.實驗環(huán)境2.1Eclipse2.2WindowXP3.實驗內容3.1裝載問題3.2旅行售貨員問題4.教師批改意見簽字：日期：成績14實驗報告細表1裝載問題1.1算法設計思想解裝載問題的優(yōu)先隊列式分支限界法用最大優(yōu)先隊列存儲活結點表?；罱Y點x在優(yōu)先隊列中的優(yōu)先級定義為從根結點到結點x的路徑所相應的載
2、重量再加上剩余集裝箱的重量之和。優(yōu)先隊列中優(yōu)先級最大的活結點成為下一個擴展結點。以結點x為根的子樹中所有結點相應的路徑的載重量不超過它的優(yōu)先級。子集樹中葉結點所相應的載重量與其優(yōu)先級相同。在優(yōu)先隊列式分支限界法中，一旦有一個葉結點成為當前擴展結點，則可以斷言該葉結點所相應的解即為最優(yōu)解。此時可終止算法。1.2程序源碼packagelab06;importjava.util.Comparator;importjava.util.PriorityQueue;importjava.util.Scanner;importlab06.FIFOBB
3、Loading.HeapNode;publicclassFIFOBBLoading{staticintn;//貨物數量staticintc1;//第一艘船的載重量staticintc2;//第二艘船的載重量staticint[]w;//貨物重量的數組staticintbestw;//當前最優(yōu)載重量staticboolean[]bestx;//當前最最優(yōu)解staticScannerscan=newScanner(System.in);publicstaticvoidmain(String[]args){//輸入貨物數量System.out
4、.print("請輸入貨物數量：n=");n=inputN();bestx=newboolean[n+1];//輸入第一艘船的載重量System.out.print("請輸入第一艘船的載重量：c1=");c1=inputC1();//輸入第二艘船的載重量System.out.print("請輸入第二艘船的載重量：c2=");c2=inputC2();14//輸入各個貨物的重量System.out.println("請輸入各個貨物的重量：");w=inputW();System.out.println("第一艘船可載重："+maxLoad
5、ing(w,c1,n,bestx));intcount=0;System.out.print("第一艘船裝載的貨物為：");for(inti=1;i<=n;i++)if(bestx[i]){System.out.print(w[i]+"");count++;bestx[i]=false;}System.out.println();if(n-count!=0){System.out.println("第二艘船可載重："+maxLoading(w,c2,n-count,bestx));System.out.print("第二艘船裝載的貨物為
6、：");for(inti=1;i<=n-count;i++)if(bestx[i])System.out.print(w[i]+"");}elseSystem.out.println("只需第一艘船便能裝載完所有貨物");}//輸入貨物數量privatestaticintinputN(){n=scan.nextInt();if(n<=0){System.out.println("貨物數量有誤，請重新輸入！");System.out.print("n=");n=scan.nextInt();inputN();}returnn;}//輸入第
7、一艘船的載重量privatestaticintinputC1()14{c1=scan.nextInt();if(c1<=0){System.out.println("第一艘船的載重量輸入有誤，請重新輸入！");System.out.print("c1=");c1=scan.nextInt();inputC1();}returnc1;}//輸入第二艘船的載重量privatestaticintinputC2(){c2=scan.nextInt();if(c2<=0){System.out.println("第二艘船的載重量輸入有誤，請重新輸
8、入！");System.out.print("c2=");c2=scan.nextInt();inputC2();}returnc2;}//輸入第一艘船的載重量privatestaticint[]input
