算法分析與設(shè)計(jì)課程設(shè)計(jì)報(bào)告-在線瀏覽
2025-05-10 12:01本頁(yè)面
【正文】 void Input()。 //排序void knapsack()。 //結(jié)果輸出。 for(int i=1。i++) { for(int j=1。j++) { if(unit_price[j]unit_price[j+1]) { temp1=Price[j]。Price[j+1]=temp1。Weight[j]=Weight[j+1]。 temp3=unit_price[j]。unit_price[j+1]=temp3。i=N。 //計(jì)算物品單位價(jià)值unit_price[ ] X[ i]=0。 //背包剩余載重 Mergesort()。i=N。 left=leftWeight[i]。 } else if(Weight[i]left) { //部分放入背包 X[i]=left/Weight[i]。 total_price=total_price+Price[i]*X[i]。 //背包容量int n。 //物品重量數(shù)組double p[N]。 //當(dāng)前重量double cp。 //當(dāng)前最優(yōu)價(jià)值int path[N]。 //最佳裝載//聲明結(jié)構(gòu)體Goodsstruct Goods{ double weight。 //總價(jià)值 int id。 //物品單位價(jià)值}。//聲明函數(shù)void backtract(int i)。 //界限函數(shù)void Input()。 //輸出函數(shù)2) 搜索解空間函數(shù)//=============================搜索解空間====================void backtract(int i){ //到達(dá)葉節(jié)點(diǎn) if(i=n) // i表示深度（層），in搜索到葉子節(jié)點(diǎn) { bestp=cp。jn。 return。 cp+=p[i]。 backtract(i+1)。 cp=p[i]。 backtract(i+1)。 // 剩余容量 double bound=cp。amp。 bound+=p[i]。 } // w[ i] cleft 跳出循環(huán)，背包裝滿(mǎn),物品部分裝入背包 //裝滿(mǎn)背包 if(i=n) bound+=p[i]*cleft/w[i]。 // 當(dāng)前物品價(jià)值與剩余物品價(jià)值之和}棋盤(pán)覆蓋問(wèn)題1）聲明變量：//聲明變量int title=1。 //二維數(shù)組board[ ][ ]，模擬棋盤(pán)/*tr 棋盤(pán)中左上角方格所在行。dr 殘缺方塊所在行。size:棋盤(pán)的行數(shù)或列數(shù)*/2）棋盤(pán)覆蓋分治實(shí)現(xiàn)：void chessBoard(int tr,int tc,int dr,int dc,int size){ int s,t。 //size:棋盤(pán)行數(shù) t=title++。 // 分割棋盤(pán) // 覆蓋左上角子棋盤(pán) if(drtr+s amp。 dctc+s) //特殊方格在此棋盤(pán)中 chessBoard(tr,tc,dr,dc,s)。 // 用 t 號(hào)L型骨牌覆蓋右下角 chessBoard(tr,tc,tr+s1,tc+s1,s)。amp。 else // 此棋盤(pán)中無(wú)特殊方格 { board[tr+s1][tc+s]=t。 // 覆蓋其余方格 } // 覆蓋左下角子棋盤(pán) if(dr=tr+s amp。 dctc+s) //特殊方格在此棋盤(pán)中 chessBoard(tr+s,tc,dr,dc,s)。 //用 t 號(hào)L型骨牌覆蓋右上角 chessBoard(tr+s,tc,tr+s,tc+s1,s)。amp。 else // 此棋盤(pán)中無(wú)特殊方格 { board[tr+s][tc+s]=t。 //覆蓋其余方格 }}五、測(cè)試分析普通背包問(wèn)題1）、輸入物品個(gè)數(shù)N=3,。3）、輸入各物品的大小或重量weight：6 、 5 、 5。5）、顯示背包裝載結(jié)果。2）、輸入物品個(gè)數(shù)：3。4）、輸入各物品的價(jià)值：4230。棋盤(pán)覆蓋問(wèn)題1）、輸入size：8。3）顯示棋盤(pán)覆蓋結(jié)果。在開(kāi)始設(shè)計(jì)時(shí)對(duì)貪心算法和分治算法的思想很好理解，但是在設(shè)計(jì)算法時(shí)大概思路還是有的，但寫(xiě)完算法寫(xiě)代碼是發(fā)現(xiàn)寫(xiě)不出來(lái)，原因就是算法設(shè)計(jì)的還不夠細(xì)，后來(lái)上網(wǎng)查了些資料，分析了別人的算法，最終實(shí)現(xiàn)了現(xiàn)在的算法設(shè)計(jì)。而且界面不夠友好，不能實(shí)現(xiàn)單步覆蓋。回溯法：就是一種窮舉搜索算法。在01背包問(wèn)題中，為了提高搜索效率，避免一些無(wú)效的搜索，則需要用限界函數(shù)bound()剪去得不到最優(yōu)解的子樹(shù)。即將一個(gè)難以直接解決的大問(wèn)題小規(guī)?；?，待解出子問(wèn)題解之后，將子問(wèn)題解合并為該問(wèn)題解。 //物品數(shù)量int M。 //背包問(wèn)題最優(yōu)解double Weight[MAX]。 //物品價(jià)值double unit_price[MAX]。 //背包總價(jià)值 //聲明函數(shù)void Input()。 //排序void knapsack()。 //結(jié)果輸出 //================輸入函數(shù)====================================void Input(){ int i。 cinN。 cout請(qǐng)輸入背包總?cè)萘縈:。 coutendl。 for(i=1。i++) cinWeight[i]。 for(i=1。i++) cinPrice[i]。}//================按照價(jià)值密度的降序排列===================void Mergesort() { double temp1,temp2,temp3。iN。j=Ni。Price[j]=Price[j+1]。 temp2=Weight[j]。Weight[j+1]=temp2。unit_price[j]=unit_price[j+1]。 } } } }//===============實(shí)現(xiàn)背包裝載================================void knapsack(){
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1