算法分析與設(shè)計(jì)課程設(shè)計(jì)報(bào)告-文庫吧
2025-01-03 23:42 本頁面
【正文】 //物品單位價(jià)值double total_price。 //背包總價(jià)值 //聲明函數(shù)void Input()。 //輸入函數(shù)void Mergesort()。 //排序void knapsack()。 //背包裝載int Output()。 //結(jié)果輸出。2）實(shí)現(xiàn)了按照價(jià)值密度的降序排列void Mergesort() { double temp1,temp2,temp3。 for(int i=1。iN。i++) { for(int j=1。j=Ni。j++) { if(unit_price[j]unit_price[j+1]) { temp1=Price[j]。Price[j]=Price[j+1]。Price[j+1]=temp1。 temp2=Weight[j]。Weight[j]=Weight[j+1]。Weight[j+1]=temp2。 temp3=unit_price[j]。unit_price[j]=unit_price[j+1]。unit_price[j+1]=temp3。 } } } }3）求最大總價(jià)值void knapsack(){ for( int i=1。i=N。 i++ ) //初始化X[i]，所有物品沒有放入背包 { unit_price[i]=Price[i]/Weight[i]。 //計(jì)算物品單位價(jià)值unit_price[ ] X[ i]=0。 } double left=M。 //背包剩余載重 Mergesort()。 //按單位價(jià)值將物品排序，便于貪心選擇 while(left!=0) { for(int i=1。i=N。i++) //貪心選擇，總是選擇價(jià)值最大放入背包 { if(Weight[i]=left) //當(dāng)前物品小于背包剩余載重 { //整個(gè)放入背包 X[i]=1。 left=leftWeight[i]。 total_price=total_price+Price[i]。 } else if(Weight[i]left) { //部分放入背包 X[i]=left/Weight[i]。 left=0。 total_price=total_price+Price[i]*X[i]。 } } }}01背包問題1）聲明變量、函數(shù)define N 100 //最大物品數(shù)//聲明變量double c。 //背包容量int n。 //物品數(shù)double w[N]。 //物品重量數(shù)組double p[N]。 //物品價(jià)值數(shù)組double cw。 //當(dāng)前重量double cp。 //當(dāng)前價(jià)值double bestp。 //當(dāng)前最優(yōu)價(jià)值int path[N]。 //當(dāng)前最優(yōu)路徑int x[N]。 //最佳裝載//聲明結(jié)構(gòu)體Goodsstruct Goods{ double weight。 //物品重量 double price。 //總價(jià)值 int id。 //物品編號(hào) float unit_price。 //物品單位價(jià)值}。Goods goods[N]={{0,0,0,0}}。//聲明函數(shù)void backtract(int i)。 //搜索解空間函數(shù)double bound(int i)。 //界限函數(shù)void Input()。 //輸入函數(shù)void Output()。 //輸出函數(shù)2) 搜索解空間函數(shù)//=============================搜索解空間====================void backtract(int i){ //到達(dá)葉節(jié)點(diǎn) if(i=n) // i表示深度（層），in搜索到葉子節(jié)點(diǎn) { bestp=cp。 for(int j=0。jn。j++) x[j]=path[j]。 return。 } //搜索子樹 if(cw+w[i]=c) //當(dāng)前物品放入背包不超載 { //進(jìn)入左子樹 cw+=w[i]。 cp+=p[i]。 path[i]=1。 backtract(i+1)。 //繼續(xù)向下深度搜索 cw=w[i]。 cp=p[i]。 } //進(jìn)入右子樹 if(bound(i+1)bestp) //當(dāng)前的節(jié)點(diǎn)不合適時(shí)，跳到下一個(gè)結(jié)點(diǎn) { path[i]=0。 backtract(i+1)。 }}3）界限函數(shù)：//====== 限界函數(shù),計(jì)算當(dāng)前價(jià)值與剩余價(jià)值和====================double bound(int i){ double cleft=ccw。 // 剩余容量 double bound=cp。 // 當(dāng)前物品價(jià)值 //以物品單位重量價(jià)值遞減的順序裝入物品 while(i=namp。amp。w[i]=cleft) // 裝載剩下的物品 { cleft=w[i]。 bound+=p[i]。 i++。 } // w[ i] cleft 跳出循環(huán)，背包裝滿,物品部分裝入背包 //裝滿背包 if(i=n) bound+=p[i]*cleft/w[i]。 return bound。 // 當(dāng)前物品價(jià)值與剩余物品價(jià)值之和}棋盤覆蓋問題1）聲明變量：//聲明變量int title=1。 //L型骨牌號(hào)int board[64][64]。 //二維數(shù)組board[ ][ ]，模擬棋盤/*tr 棋盤中左上角方格所在行。tc 棋盤中左上角方格所在列。dr 殘缺方塊所在行。dl 殘缺方塊所在列。size:棋盤的行數(shù)或列數(shù)*/2）棋盤覆蓋分治實(shí)現(xiàn)：void chessBoard(int tr,int tc,int dr,int dc,int size){ int s,t。 if(size==1) return。 //size:棋盤行數(shù) t=title++。 //L型骨牌號(hào) s=size/2。 // 分割棋盤 // 覆蓋左上角子棋盤 if(drtr+s
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1