資源描述：
《回溯算法之01背包問題java源程序》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、實(shí)驗(yàn)報告11課程數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)名稱回溯法第頁班級11計(jì)本學(xué)號105032011130姓名風(fēng)律澈實(shí)驗(yàn)日期：2013年5月20日報告退發(fā)(訂正、重做)一、實(shí)驗(yàn)?zāi)康恼莆栈厮莘ǖ脑砗蛻?yīng)用。二、實(shí)驗(yàn)環(huán)境1、微型計(jì)算機(jī)一臺2、WINDOWS操作系統(tǒng)，JavaSDK，Eclipse開發(fā)環(huán)境三、實(shí)驗(yàn)內(nèi)容必做題：1、編寫程序，實(shí)現(xiàn)n后問題算法。（如果上周沒完成，這周完成）2、編寫程序，采用回溯法實(shí)現(xiàn)0-1背包問題。四、實(shí)驗(yàn)步驟和結(jié)果(附上代碼和程序運(yùn)行結(jié)果截圖)2、0-1回溯背包問題importjava.util.Ar
2、rayList;importjava.util.PriorityQueue;publicclassmain{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstu//初始化工作baga=newbag(7);ArrayList
3、ntv[]={9,10,7,4};intw[]={3,5,2,1};for(inti=0;i4、s,a);//輸出System.out.println(a.getmaxvalue());}privatestaticvoidbacktrack(inti,ArrayList
5、weight()){a.addobject(objects.get(i-1));backtrack(i+1,objects,a);a.removeobjec(objects.get(i-1));}if(bound(i+1,objects,a)>a.getmaxvalue()){backtrack(i+1,objects,a);}}privatestaticintbound(inti,ArrayList
6、tleftcontain=a.getmaxweight()-a.getcontain();intbound=a.getvalue();while((i<=objects.size())&&(objects.get(i-1).getweight()<=leftcontain)){leftcontain-=objects.get(i-1).getweight();bound+=objects.get(i-1).getvalue();i++;}if(i<=objects.size())bound+=objects
7、.get(i-1).getvalue()*leftcontain/objects.get(i-1).getweight();returnbound;}}importjava.util.ArrayList;publicclassbag{privateintcontain;privateintvalue;privateintmaxweight;privateintmaxvalue;privateArrayList
8、this.value=0;this.maxweight=maxw;this.maxvalue=0;this.objects=newArrayList
