算法設(shè)計(jì)普通背包問(wèn)題與棋盤(pán)覆蓋問(wèn)題分析

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

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

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

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

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

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

7、我們就可以用遞歸算法解決。tr: 棋盤(pán)左上方格行號(hào)；tc：棋盤(pán)左上方格列號(hào)；dr：特殊方格所在行號(hào)；dc：特殊方格所在列號(hào)；size：棋盤(pán)規(guī)格2k×2k五、算法實(shí)現(xiàn)1、普通背包問(wèn)題：（1）實(shí)現(xiàn)了按照價(jià)值密度的降序排列：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）求最大總價(jià)值：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<<"結(jié)果表示為:"<<endl; for(i=1;i<=n;i+) cout<<"第"<<i<<"個(gè)物體大小:"<< si<<" 物體價(jià)值:"<< pi<<" 物體價(jià)值密

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

11、dl; /背包所裝載總價(jià)值 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<<"請(qǐng)輸入物體數(shù)n:" cin>>n; cout<<endl; cout&l

12、t;<"請(qǐng)輸入背包總?cè)萘緾:" cin>>C; cout<<endl; cout<<"請(qǐng)輸入各物體的大小或重量:"<<endl; for(i=1;i<=n;i+) cin>>si; cout<<"請(qǐng)輸入各物體的價(jià)值p:"<<endl; for(i=1;i<=n;i+) cin>>pi; cout<<endl;2、棋盤(pán)覆蓋問(wèn)題：（1）棋盤(pán)覆蓋分治實(shí)現(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<<"輸入棋盤(pán)的size(大小必須是2的n次冪): "cin>>size;int index_x,index_y;cout<<"輸入特殊方格位置的坐標(biāo): "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; 六、測(cè)試分析1、普通背包問(wèn)題：（1）、輸入物品個(gè)數(shù)n=3（2）、輸入背包容量C：10（3）、輸入各物品的大小或重量：6 、 5 、 5（4）、輸入各物品的價(jià)值p：56 、 23 、 432、棋盤(pán)覆蓋問(wèn)題：（1）、輸入size：8（2）、輸入特殊方塊的位置:1,1七、結(jié)論兩個(gè)算法，普通背包問(wèn)題是用的貪心算法設(shè)計(jì)的，棋盤(pán)覆蓋問(wèn)題是用的分治法設(shè)計(jì)的。在開(kāi)始設(shè)計(jì)時(shí)對(duì)貪心算法和分治算法的思想很好理解，但是在設(shè)計(jì)算法時(shí)大概思路還是有的，但寫(xiě)完算法寫(xiě)代碼是發(fā)現(xiàn)寫(xiě)不出來(lái)，原因就是算法設(shè)計(jì)的還不夠細(xì)，后來(lái)上網(wǎng)查了些資料，分析了別人的算法，最終實(shí)現(xiàn)了現(xiàn)在的算法設(shè)計(jì)。在這兩個(gè)算法中貪心算法求普

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

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

19、le pM)/按照價(jià)值密度的降序排列； 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(總價(jià)值) 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<<"結(jié)果表示為:"

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

22、lt;=n;i+) cout<<xi<<" " totalp=totalp+pi*xi; cout<<")"<<endl; cout<<"背包的總價(jià)值為："<<totalp<<endl; /背包所裝載總價(jià)值 cout<<"按Y或y繼續(xù)操作，否則按任意鍵"<<endl; cin>>ch; if(ch='Y'|ch='y') continue; else break; 2、棋盤(pán)覆蓋問(wèn)題：#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