【正文】 1]=temp3。 //計算物品單位價值unit_price[ ] X[ i]=0。i=N。 } else if(Weight[i]left) { //部分放入背包 X[i]=left/Weight[i]。 //背包容量int n。 //當前重量double cp。 //最佳裝載//聲明結構體Goodsstruct Goods{ double weight。 //物品單位價值}。 //界限函數(shù)void Input()。jn。 cp+=p[i]。 cp=p[i]。 // 剩余容量 double bound=cp。 bound+=p[i]。 // 當前物品價值與剩余物品價值之和}棋盤覆蓋問題1）聲明變量：//聲明變量int title=1。dr 殘缺方塊所在行。 //size:棋盤行數(shù) t=title++。 dctc+s) //特殊方格在此棋盤中 chessBoard(tr,tc,dr,dc,s)。amp。 // 覆蓋其余方格 } // 覆蓋左下角子棋盤 if(dr=tr+s amp。 //用 t 號L型骨牌覆蓋右上角 chessBoard(tr+s,tc,tr+s,tc+s1,s)。 else // 此棋盤中無特殊方格 { board[tr+s][tc+s]=t。3）、輸入各物品的大小或重量weight：6 、 5 、 5。2）、輸入物品個數(shù)：3。棋盤覆蓋問題1）、輸入size：8。在開始設計時對貪心算法和分治算法的思想很好理解，但是在設計算法時大概思路還是有的，但寫完算法寫代碼是發(fā)現(xiàn)寫不出來，原因就是算法設計的還不夠細，后來上網查了些資料，分析了別人的算法，最終實現(xiàn)了現(xiàn)在的算法設計。回溯法：就是一種窮舉搜索算法。即將一個難以直接解決的大問題小規(guī)模化，待解出子問題解之后，將子問題解合并為該問題解。 //背包問題最優(yōu)解double Weight[MAX]。 //背包總價值 //聲明函數(shù)void Input()。 //結果輸出 //================輸入函數(shù)====================================void Input(){ int i。 cout請輸入背包總容量M:。 for(i=1。 for(i=1。}//================按照價值密度的降序排列===================void Mergesort() { double temp1,temp2,temp3。j=Ni。 temp2=Weight[j]。unit_price[j]=unit_price[j+1]。 i++ ) //初始化X[i]，所有物品沒有放入背包 { unit_price[i]=Price[i]/Weight[i]。 //按單位價值將物品排序，便于貪心選擇 while(left!=0) { for(int i=1。 total_price=total_price+Price[i]。 } } }}//============結果輸出======================================int Output(){ char ch。i++) { cout第i個物體大小: Weight[i] 物體價值: Price[i] 物體價值密度: unit_price[i] endl。i=N。 //背包所裝載總價值 cout按Y或y繼續(xù)操作，否則按任意鍵endl。 char ch。 if(ch==39。) continue。 //背包容量int n。 //當前重量double cp。 //最佳裝載//聲明結構體Goodsstruct Goods{ double weight。 //物品單位價值}。 //界限函數(shù)void Input()。 cinc。in。in。 printf(*******************************************************\n)。i++) { if(x[i]==1) { cout第goods[i].id個物品放入 價值是goods[i].priceendl。 cp=0。i++) { goods[i].id=i+1。 } //物品按單位重量從大到小排序 for(i=0。j++) { if(goods[j].unit_pricegoods[j+1].unit_price) { Goods temp={0,0,0,0}。 } } } //重新給p[]、 w[] 賦值 for(i=0。 } //初始化當前最優(yōu)路徑 for(i=0。 //深度優(yōu)先搜索解空間}//=============================搜索解空間====================void backtract(int i){ //到達葉節(jié)點 if(i=n) // i表示深度（層），in搜索到葉子節(jié)點 { bestp=cp。 return。 backtract(i+1)。 backtract(i+1)。amp。 } // w[ i] cleft 跳出循環(huán)，背包裝滿,物品部分裝入背包 //裝滿背包 if(i=n) bound+=p[i]*cleft/w[i]。 Output()。tc 棋盤中左上角方格所在列。 if(size==1) return。amp。 // 覆蓋其余方格 } // 覆蓋右上角子棋盤 if(drtr+s amp。 // 用 t 號L型骨牌覆蓋左下角 chessBoard(tr,tc+s,tr+s1,tc+s,s)。 else // 此棋盤中無特殊方格 { board[tr+s][tc+s1]=t。 dc=tc+s) //特殊方格在此棋盤中 chessBoard(tr+s,tc+s,dr,dc,s)。 printf(請輸入棋盤的size(大小必須是2的n次冪):\n)。 scanf(%d%d,amp。amp。i++) { for(j=0。 } } else { printf(the wrong specal point!!\