【正文】 return 。j++) { printf(%4d,board[i][j])。 for(i=0。dc)。s)。 // 用 t 號L型骨牌覆蓋左上角 chessBoard(tr+s,tc+s,tr+s,tc+s,s)。 //覆蓋其余方格 } //覆蓋右下角子棋盤 if(dr=tr+s amp。amp。 dc=tc+s) //特殊方格在此棋盤中 chessBoard(tr,tc+s,dr,dc,s)。 else // 此棋盤中無特殊方格 { board[tr+s1][tc+s1]=t。 //L型骨牌號 s=size/2。dl 殘缺方塊所在列。 //L型骨牌號int board[64][64]。 // 當前物品價值與剩余物品價值之和}//===========================主函數(shù)=============================void main(){ Input()。 bound+=p[i]。 // 剩余容量 double bound=cp。 cp=p[i]。 cp+=p[i]。jn。i++) { path[i]=0。i++) { p[i]=goods[i].price。 goods[j]=goods[j+1]。i++) { for(j=0。 goods[i].price=p[i]。 for(i=0。}void knapsack(){ int i,j。 for(i=0。 cinp[i]。 cinw[i]。 cinn。 //輸出函數(shù)//=================輸入物品數(shù)量、背包容量、各物品重量、各物品價值===============void Input(){ int i。//聲明函數(shù)void backtract(int i)。 //總價值 int id。 //當前最優(yōu)價值int path[N]。 //物品重量數(shù)組double p[N]。 }}01背包問題include iostreamusing namespace std。||ch==39。 knapsack()。 return ch。 } cout)endl。 cout向量表示: ( 。 for(int i=1。 left=0。i++) //貪心選擇，總是選擇價值最大放入背包 { if(Weight[i]=left) //當前物品小于背包剩余載重 { //整個放入背包 X[i]=1。 } double left=M。 } } } }//===============實現(xiàn)背包裝載================================void knapsack(){ for( int i=1。Weight[j+1]=temp2。Price[j]=Price[j+1]。iN。i++) cinPrice[i]。i++) cinWeight[i]。 coutendl。 cinN。 //排序void knapsack()。 //物品價值double unit_price[MAX]。 //物品數(shù)量int M。在01背包問題中，為了提高搜索效率，避免一些無效的搜索，則需要用限界函數(shù)bound()剪去得不到最優(yōu)解的子樹。而且界面不夠友好，不能實現(xiàn)單步覆蓋。3）顯示棋盤覆蓋結果。4）、輸入各物品的價值：4230。5）、顯示背包裝載結果。 //覆蓋其余方格 }}五、測試分析普通背包問題1）、輸入物品個數(shù)N=3,。amp。 dctc+s) //特殊方格在此棋盤中 chessBoard(tr+s,tc,dr,dc,s)。 else // 此棋盤中無特殊方格 { board[tr+s1][tc+s]=t。 // 用 t 號L型骨牌覆蓋右下角 chessBoard(tr,tc,tr+s1,tc+s1,s)。 // 分割棋盤 // 覆蓋左上角子棋盤 if(drtr+s amp。size:棋盤的行數(shù)或列數(shù)*/2）棋盤覆蓋分治實現(xiàn)：void chessBoard(int tr,int tc,int dr,int dc,int size){ int s,t。 //二維數(shù)組board[ ][ ]，模擬棋盤/*tr 棋盤中左上角方格所在行。 } // w[ i] cleft 跳出循環(huán)，背包裝滿,物品部分裝入背包 //裝滿背包 if(i=n) bound+=p[i]*cleft/w[i]。amp。 backtract(i+1)。 backtract(i+1)。 return。 //輸出函數(shù)2) 搜索解空間函數(shù)//=============================搜索解空間====================void backtract(int i){ //到達葉節(jié)點 if(i=n) // i表示深度（層），in搜索到葉子節(jié)點 { bestp=cp。//聲明函數(shù)void backtract(int i)。 //總價值 int id。 //當前最優(yōu)價值int path[N]。 //物品重量數(shù)組double p[N]。 total_price=total_price+Price[i]*X[i]。 left=leftWeight[i]。 //背包剩余載重 Mergesort()。i=N。 temp3=unit_price[j]。Price[j+1]=temp1。i++) { for(int j=1。 //結果輸出。 //背包總價值 //聲明函數(shù)void Input()。 //背包問題最優(yōu)解double Weight[MAX]。理解算法。? dl 殘缺方塊所在列。 ：2）棋盤的識別： 棋盤的規(guī)模是一個必要的信息，有了這個信息，只要知道其左上角的左上角方格所在行、列就可以唯一確定一個棋盤了，殘缺方格或“偽