算法分析與設(shè)計課程設(shè)計報告-文庫吧資料
2025-01-24 23:42本頁面
【正文】 ]=Weight[j+1]。Price[j+1]=temp1。j++) { if(unit_price[j]unit_price[j+1]) { temp1=Price[j]。i++) { for(int j=1。 for(int i=1。 coutendl。i=N。 cout請輸入各物體的價值price:endl。i=N。 cout請輸入各物體的大小或重量weight:endl。 cinM。 coutendl。 cout請輸入物體數(shù)N:。 //背包裝載int Output()。 //輸入函數(shù)void Mergesort()。 //物品單位價值double total_price。 //物品重量 double Price[MAX]。 //背包容量double X[MAX]。七、源程序普通背包問題include define MAX 100 //物品件數(shù)最大值// 聲明變量int N。分治法：分而治之。通俗地講：回溯法是一種“能進則進，進不了則換，換不了則退”的基本搜索方法。不過，總的來說這次實踐也是有一定收獲的，至少對書中這三個算法的知識進行了鞏固，自己更進一步地理解了這三個算法——貪心算法：從問題的初始解出發(fā)逐步逼近給定的目標(biāo)，每一步都做出當(dāng)前看來是最優(yōu)的選擇（貪心選擇），最終得到整個問題的最優(yōu)解。在最終完成的程序中：貪心算法求普通背包問題，基本上已經(jīng)實現(xiàn)了主要的功能；01背包問題也能實現(xiàn)主要功能，但一開始未使用到界限函數(shù)，后來才加上；在分治算法求棋盤覆蓋問題時，也基本上實現(xiàn)了它的功能，但在輸入時還有不足，需要人工輸入2的指數(shù)冪，不夠方便。六、結(jié)論三個算法，普通背包問題是用的貪心算法設(shè)計的，01背包問題是用回溯算法實現(xiàn)的，棋盤覆蓋問題是用的分治法設(shè)計的。2）、輸入特殊方塊的位置:4 3。5）、顯示背包裝載結(jié)果。3）、輸入各物品重量：6 、 5 、 5。01背包問題1）、輸入背包容量：10,。4）、輸入各物品的價值p：4230。2）、輸入背包容量M：10。 // 用 t 號L型骨牌覆蓋左上角 chessBoard(tr+s,tc+s,tr+s,tc+s,s)。 dc=tc+s) //特殊方格在此棋盤中 chessBoard(tr+s,tc+s,dr,dc,s)。 //覆蓋其余方格 } //覆蓋右下角子棋盤 if(dr=tr+s amp。 else // 此棋盤中無特殊方格 { board[tr+s][tc+s1]=t。amp。 // 用 t 號L型骨牌覆蓋左下角 chessBoard(tr,tc+s,tr+s1,tc+s,s)。 dc=tc+s) //特殊方格在此棋盤中 chessBoard(tr,tc+s,dr,dc,s)。 // 覆蓋其余方格 } // 覆蓋右上角子棋盤 if(drtr+s amp。 else // 此棋盤中無特殊方格 { board[tr+s1][tc+s1]=t。amp。 //L型骨牌號 s=size/2。 if(size==1) return。dl 殘缺方塊所在列。tc 棋盤中左上角方格所在列。 //L型骨牌號int board[64][64]。 return bound。 i++。w[i]=cleft) // 裝載剩下的物品 { cleft=w[i]。 // 當(dāng)前物品價值 //以物品單位重量價值遞減的順序裝入物品 while(i=namp。 }}3）界限函數(shù)：//====== 限界函數(shù),計算當(dāng)前價值與剩余價值和====================double bound(int i){ double cleft=ccw。 } //進入右子樹 if(bound(i+1)bestp) //當(dāng)前的節(jié)點不合適時，跳到下一個結(jié)點 { path[i]=0。 //繼續(xù)向下深度搜索 cw=w[i]。 path[i]=1。 } //搜索子樹 if(cw+w[i]=c) //當(dāng)前物品放入背包不超載 { //進入左子樹 cw+=w[i]。j++) x[j]=path[j]。 for(int j=0。 //輸入函數(shù)void Output()。 //搜索解空間函數(shù)double bound(int i)。Goods goods[N]={{0,0,0,0}}。 //物品編號 float unit_price。 //物品重量 double price。 //當(dāng)前最優(yōu)路徑int x[N]。 //當(dāng)前價值double bestp。 //物品價值數(shù)組double cw。 //物品數(shù)double w[N]。 } } }}01背包問題1）聲明變量、函數(shù)define N 100 //最大物品數(shù)//聲明變量double c。 left=0。 total_price=total_price+Price[i]。i++) //貪心選擇，總是選擇價值最大放入背包 { if(Weight[i]=left) //當(dāng)前物品小于背包剩余載重 { //整個放入背包 X[i]=1。 //按單位價值將物品排序，便于貪心選擇 while(left!=0) { for(int i=1。 } double left=M。 i++ ) //初始化X[i]，所有物品沒有放入背包 { unit_price[i]=Price[i]/Weight[i]。 } } } }3）求最大總價值void knapsack(){ for( int i=1。unit_price[j]=unit_price[j+1]。Weight[j+1]=temp2。 temp2=Weight[j]。Price[j]=Price[j+1]。j=Ni。iN。2）實現(xiàn)了按照價值密度的降序排列void Mergesort() { double temp1,temp2,temp3。 //背包裝載int Output()。 //輸入函數(shù)void Mergesort()。 /
高考資料相關(guān)推薦
鄂ICP備17016276號-1