算法設計普通背包問題與棋盤覆蓋問題分析

1、目 錄一、問題描述31、普通背包問題：32、棋盤覆蓋問題：3二、問題分析31、普通背包問題：32、棋盤覆蓋問題：4三、建立數(shù)學模型41、普通背包問題：4四、算法設計52、普通背包問題：52、棋盤覆蓋問題：5五、算法實現(xiàn)61、普通背包問題：62、棋盤覆蓋問題：9六、測試分析101、普通背包問題：102、棋盤覆蓋問題：12七、結論13八、源程序131、普通背包問題：132、棋盤覆蓋問題：16九、參考文獻：17一、問題描述1、普通背包問題：有一個背包容量為C，輸入N個物品，每個物品有重量Si，以及物品放入背包中所得的收益Pi。求選擇放入的物品，不超過背包的容量，且得到的收益最好。物品可以拆分，利用貪

2、心算法解決。2、棋盤覆蓋問題：在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。二、問題分析1、普通背包問題：貪心算法的基本思想是：從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的求得更好的解。當達到算法中的某一步不能再繼續(xù)前進時，算法停止。背包問題用貪心算法來解決，先求出每件物品的平均價值即pi/si，然后每次選擇利潤pi/si最大的物品裝進背包，這樣就使得目標函數(shù)增加最快，當最后一種物

3、品放不下時，選擇一個適當?shù)牟鸱?，使物品裝滿背包，使得總的價值最大。2、棋盤覆蓋問題：將2k x 2k的棋盤，先分成相等的四塊子棋盤，其中特殊方格位于四個中的一個，構造剩下沒特殊方格三個子棋盤，將他們中的也假一個方格設為特殊方格。如果是：左上的子棋盤（若不存在特殊方格）則將該子棋盤右下角的那個方格假設為特殊方格右上的子棋盤（若不存在特殊方格）則將該子棋盤左下角的那個方格假設為特殊方格左下的子棋盤（若不存在特殊方格）則將該子棋盤右上角的那個方格假設為特殊方格右下的子棋盤（若不存在特殊方格）則將該子棋盤左上角的那個方格假設為特殊方格當然上面四種，只可能且必定只有三個成立，那三個假設的特殊方格剛好構成

4、一個L型骨架，我們可以給它們作上相同的標記。這樣四個子棋盤就分別都和原來的大棋盤類似，我們就可以用遞歸算法解決。三、建立數(shù)學模型（根據(jù)問題情況選擇，不需要此步驟可不要）1、普通背包問題：求平均價值即pi/si約束條件：c1<=0四、算法設計2、普通背包問題：用貪心算法進行設計，貪心算法的基本思想是：從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的求得更好的解。當達到算法中的某一步不能再繼續(xù)前進時，算法停止。int n 物品個數(shù) double C 背包的容量double sM 物品的重量（或大?。?double pM物品的價值void average(int n,double sM

5、,double pM)/按照價值密度的降序排列函數(shù)；double c1 背包剩余容量 totalp 物品的總價值void bag(int n,double C,double sM,double pM,double xM)求物品總價值的函數(shù)在求物品總價值函數(shù)中藥調(diào)用average函數(shù)，在主函數(shù)中調(diào)用bag()函數(shù)。2、棋盤覆蓋問題：采用分治法設計，分治法的基本思想：分治法求解問題的過程是，將整個問題分解成若干個小問題后分而治之。如果分解得到的子問題相對來說還太大，則可反復使用分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出方便求解的子問題，必要時逐步合并這些子問題的解，從而得到問題的解。將

6、2k x 2k的棋盤，先分成相等的四塊子棋盤，其中特殊方格位于四個中的一個，構造剩下沒特殊方格三個子棋盤，將他們中的也假一個方格設為特殊方格。如果是：左上的子棋盤（若不存在特殊方格）則將該子棋盤右下角的那個方格假設為特殊方格右上的子棋盤（若不存在特殊方格）則將該子棋盤左下角的那個方格假設為特殊方格左下的子棋盤（若不存在特殊方格）則將該子棋盤右上角的那個方格假設為特殊方格右下的子棋盤（若不存在特殊方格）則將該子棋盤左上角的那個方格假設為特殊方格當然上面四種，只可能且必定只有三個成立，那三個假設的特殊方格剛好構成一個L型骨架，我們可以給它們作上相同的標記。這樣四個子棋盤就分別都和原來的大棋盤類似，

7、我們就可以用遞歸算法解決。tr: 棋盤左上方格行號；tc：棋盤左上方格列號；dr：特殊方格所在行號；dc：特殊方格所在列號；size：棋盤規(guī)格2k×2k五、算法實現(xiàn)1、普通背包問題：（1）實現(xiàn)了按照價值密度的降序排列：void average(int n,double sM,double pM) int i,j; double temp1,temp2,temp3,cM; for(i=1;i<=n;i+) ci=pi/si; for(i=1;i<n;i+) for(j=1;j<=n-i;j+) if(cj<cj+1) temp1=pj;pj=pj+1;pj+1=

8、temp1; temp2=sj;sj=sj+1;sj+1=temp2; temp3=cj;cj=cj+1;cj+1=temp3; ;（2）求最大總價值：void bag(int n,double C,double sM,double pM,double xM) int i; double c1; average(n,s,p); c1=C; while(c1!=0) for(i=1;i<=n;i+) if(si<=c1) xi=1; c1=c1-si; else if(si>c1) xi=c1/si; c1=0;/ totalp=totalp+pi*xi; ;（3）主函數(shù)：vo

9、id main() int i,n; double C=0,totalp=0,sM,pM,xM; char ch; while(1) display(n,C,s,p); bag(n,C,s,p,x);/totalp cout<<"結果表示為:"<<endl; for(i=1;i<=n;i+) cout<<"第"<<i<<"個物體大小:"<< si<<" 物體價值:"<< pi<<" 物體價值密

10、度:"<< pi/si<<" "<<endl; cout<<endl; cout<<"向量表示:"<<" ( " for(i=1;i<=n;i+) cout<<xi<<" " totalp=totalp+pi*xi; cout<<")"<<endl; cout<<"背包的總價值為："<<totalp<<en

11、dl; /背包所裝載總價值 cout<<"按Y或y繼續(xù)操作，否則按任意鍵"<<endl; cin>>ch; if(ch='Y'|ch='y') continue; else break; 顯示函數(shù)Display():void display(int &n,double &C,double sM,double pM)int i; s0=0; p0=0; cout<<"請輸入物體數(shù)n:" cin>>n; cout<<endl; cout&l

12、t;<"請輸入背包總容量C:" cin>>C; cout<<endl; cout<<"請輸入各物體的大小或重量:"<<endl; for(i=1;i<=n;i+) cin>>si; cout<<"請輸入各物體的價值p:"<<endl; for(i=1;i<=n;i+) cin>>pi; cout<<endl;2、棋盤覆蓋問題：（1）棋盤覆蓋分治實現(xiàn)：void chessBoard(int tr, int tc,

13、 int dr, int dc, int size)if(size=1)return;int t=tile+;int s=size/2;if(dr<tr+s && dc<tc+s)chessBoard(tr, tc, dr, dc, s);elseboardtr+s-1tc+s-1=t;chessBoard(tr, tc, tr+s-1, tc+s-1, s);if(dr<tr+s && dc>=tc+s)chessBoard(tr, tc+s, dr, dc, s);elseboardtr+s-1tc+s=t;chessBoard(tr

14、, tc+s, tr+s-1, tc+s, s);if(dr>=tr+s && dc<tc+s)chessBoard(tr+s, tc, dr, dc, s);elseboardtr+stc+s-1=t;chessBoard(tr+s, tc, tr+s, tc+s-1, s);if(dr>=tr+s && dc>=tc+s)chessBoard(tr+s, tc+s, dr, dc, s);elseboardtr+stc+s=t;chessBoard(tr+s, tc+s, tr+s, tc+s, s);（2）主函數(shù)：void main

15、() int size;cout<<"輸入棋盤的size(大小必須是2的n次冪): "cin>>size;int index_x,index_y;cout<<"輸入特殊方格位置的坐標: "cin>>index_x>>index_y;chessBoard(0,0,index_x,index_y,size);for(int i=0;i<size;i+)for(int j=0;j<size;j+)cout<<boardij<<" "cout<

16、;<endl; 六、測試分析1、普通背包問題：（1）、輸入物品個數(shù)n=3（2）、輸入背包容量C：10（3）、輸入各物品的大小或重量：6 、 5 、 5（4）、輸入各物品的價值p：56 、 23 、 432、棋盤覆蓋問題：（1）、輸入size：8（2）、輸入特殊方塊的位置:1,1七、結論兩個算法，普通背包問題是用的貪心算法設計的，棋盤覆蓋問題是用的分治法設計的。在開始設計時對貪心算法和分治算法的思想很好理解，但是在設計算法時大概思路還是有的，但寫完算法寫代碼是發(fā)現(xiàn)寫不出來，原因就是算法設計的還不夠細，后來上網(wǎng)查了些資料，分析了別人的算法，最終實現(xiàn)了現(xiàn)在的算法設計。在這兩個算法中貪心算法求普

17、通背包問題，基本上已經(jīng)實現(xiàn)了主要的功能，在分治算法求棋盤覆蓋問題，也基本上實現(xiàn)了它的功能，但在輸入時還有不足，需要人工輸入2的指數(shù)冪，不夠方便。不過總的來說這次實踐收獲很多，不僅對先前學到的知識進行了鞏固，還在應用實踐中獲得了經(jīng)驗。八、源程序1、普通背包問題：#include<iostream.h> #define M 100 void display(int &n,double &C,double sM,double pM) int i; s0=0;p0=0; cout<<"請輸入物體數(shù)n:" cin>>n; cout&

18、lt;<endl; cout<<"請輸入背包總容量C:" cin>>C; cout<<endl; cout<<"請輸入各物體的大小或重量:"<<endl; for(i=1;i<=n;i+) cin>>si; cout<<"請輸入各物體的價值p:"<<endl; for(i=1;i<=n;i+) cin>>pi; cout<<endl;void average(int n,double sM,doub

19、le pM)/按照價值密度的降序排列； int i,j; double temp1,temp2,temp3,cM; for(i=1;i<=n;i+) ci=pi/si; for(i=1;i<n;i+) for(j=1;j<=n-i;j+) if(cj<cj+1) temp1=pj;pj=pj+1;pj+1=temp1; temp2=sj;sj=sj+1;sj+1=temp2; temp3=cj;cj=cj+1;cj+1=temp3; ;void bag(int n,double C,double sM,double pM,double xM)/totalp(總價值) i

20、nt i; double c1; average(n,s,p); c1=C; while(c1!=0) for(i=1;i<=n;i+) if(si<=c1) xi=1; c1=c1-si; else if(si>c1) xi=c1/si; c1=0; / totalp=totalp+pi*xi; ;void main() int i,n; double C=0,totalp=0,sM,pM,xM; char ch; while(1) display(n,C,s,p); bag(n,C,s,p,x);/totalp cout<<"結果表示為:"

21、<<endl; for(i=1;i<=n;i+) cout<<"第"<<i<<"個物體大小:"<< si<<" 物體價值:"<< pi<<" 物體價值密度:"<< pi/si<<" "<<endl; cout<<endl; cout<<"向量表示:"<<" ( " for(i=1;i&

22、lt;=n;i+) cout<<xi<<" " totalp=totalp+pi*xi; cout<<")"<<endl; cout<<"背包的總價值為："<<totalp<<endl; /背包所裝載總價值 cout<<"按Y或y繼續(xù)操作，否則按任意鍵"<<endl; cin>>ch; if(ch='Y'|ch='y') continue; else break; 2、棋盤覆蓋問題：#include<iostream.h>int tile=1;int board100100;void chessBoard(int tr, int tc, int dr, int dc, int size)if(size=1)return;int t=tile+;int s=size/2;if(dr<tr+s && dc<tc+s)chessBoard(tr, tc, dr, dc, s);elseboardtr+s-1tc+s-1=t;chessBoard(tr, t