算法分析與設(shè)計課程設(shè)計報告-閱讀頁
2025-04-07 12:01本頁面
【正文】 for( int i=1。 i++ ) //初始化X[i]，所有物品沒有放入背包 { unit_price[i]=Price[i]/Weight[i]。 } double left=M。 //按單位價值將物品排序，便于貪心選擇 while(left!=0) { for(int i=1。i++) //貪心選擇，總是選擇價值最大放入背包 { if(Weight[i]=left) //當前物品小于背包剩余載重 { //整個放入背包 X[i]=1。 total_price=total_price+Price[i]。 left=0。 } } }}//============結(jié)果輸出======================================int Output(){ char ch。 for(int i=1。i++) { cout第i個物體大小: Weight[i] 物體價值: Price[i] 物體價值密度: unit_price[i] endl。 cout向量表示: ( 。i=N。 } cout)endl。 //背包所裝載總價值 cout按Y或y繼續(xù)操作，否則按任意鍵endl。 return ch。 char ch。 knapsack()。 if(ch==39。||ch==39。) continue。 }}01背包問題include iostreamusing namespace std。 //背包容量int n。 //物品重量數(shù)組double p[N]。 //當前重量double cp。 //當前最優(yōu)價值int path[N]。 //最佳裝載//聲明結(jié)構(gòu)體Goodsstruct Goods{ double weight。 //總價值 int id。 //物品單位價值}。//聲明函數(shù)void backtract(int i)。 //界限函數(shù)void Input()。 //輸出函數(shù)//=================輸入物品數(shù)量、背包容量、各物品重量、各物品價值===============void Input(){ int i。 cinc。 cinn。in。 cinw[i]。in。 cinp[i]。 printf(*******************************************************\n)。 for(i=0。i++) { if(x[i]==1) { cout第goods[i].id個物品放入 價值是goods[i].priceendl。}void knapsack(){ int i,j。 cp=0。 for(i=0。i++) { goods[i].id=i+1。 goods[i].price=p[i]。 } //物品按單位重量從大到小排序 for(i=0。i++) { for(j=0。j++) { if(goods[j].unit_pricegoods[j+1].unit_price) { Goods temp={0,0,0,0}。 goods[j]=goods[j+1]。 } } } //重新給p[]、 w[] 賦值 for(i=0。i++) { p[i]=goods[i].price。 } //初始化當前最優(yōu)路徑 for(i=0。i++) { path[i]=0。 //深度優(yōu)先搜索解空間}//=============================搜索解空間====================void backtract(int i){ //到達葉節(jié)點 if(i=n) // i表示深度（層），in搜索到葉子節(jié)點 { 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)，背包裝滿,物品部分裝入背包 //裝滿背包 if(i=n) bound+=p[i]*cleft/w[i]。 // 當前物品價值與剩余物品價值之和}//===========================主函數(shù)=============================void main(){ Input()。 Output()。 //L型骨牌號int board[64][64]。tc 棋盤中左上角方格所在列。dl 殘缺方塊所在列。 if(size==1) return。 //L型骨牌號 s=size/2。amp。 else // 此棋盤中無特殊方格 { board[tr+s1][tc+s1]=t。 // 覆蓋其余方格 } // 覆蓋右上角子棋盤 if(drtr+s amp。 dc=tc+s) //特殊方格在此棋盤中 chessBoard(tr,tc+s,dr,dc,s)。 // 用 t 號L型骨牌覆蓋左下角 chessBoard(tr,tc+s,tr+s1,tc+s,s)。amp。 else // 此棋盤中無特殊方格 { board[tr+s][tc+s1]=t。 //覆蓋其余方格 } //覆蓋右下角子棋盤 if(dr=tr+s amp。 dc=tc+s) //特殊方格在此棋盤中 chessBoard(tr+s,tc+s,dr,dc,s)。 // 用 t 號L型骨牌覆蓋左上角 chessBoard(tr+s,tc+s,tr+s,tc+s,s)。 printf(請輸入棋盤的size(大小必須是2的n次冪):\n)。s)。 scanf(%d%d,amp。dc)。amp。 for(i=0。i++) { for(j=0。j++) { printf(%4d,board[i][j])。 } } else { printf(the wrong specal point!!\n)。 retur
電大資料相關(guān)推薦
鄂ICP備17016276號-1