算法設(shè)計(jì)及分析課程設(shè)計(jì)報(bào)告

1、. .課 程 設(shè) 計(jì) 報(bào) 告課程設(shè)計(jì)名稱：算法設(shè)計(jì)與分析系 ： 三系 學(xué)生XX： 陽(yáng)班 級(jí)：12軟件(2)班 學(xué) 號(hào)：成 績(jī)：指導(dǎo)教師： 川 開(kāi)課時(shí)間：2021學(xué)年一學(xué)期一、問(wèn)題描述1普通背包問(wèn)題給定n種物品和一個(gè)背包。物品i的重量是Wi,其價(jià)值為Vi,背包的容量為C。選擇裝入的背包的物品，使得裝入背包中的物品的總價(jià)值最大，在選擇物品i裝入背包時(shí)，可以選擇物品i的一局部，而不一定要全部裝入背包，1in。20/1背包問(wèn)題給定n種物品和一個(gè)背包。物品i的重量是Wi,其價(jià)值為Vi,背包的容量為C。選擇裝入的背包的物品，使得裝入背包中的物品的總價(jià)值最大，在選擇物品i裝入背包時(shí)，對(duì)于每種物品i只有兩種選

2、擇，即裝入背包或者不裝入背包，不能將物品裝入背包屢次，也不能只裝入局部的物品i。 3棋盤(pán)覆蓋問(wèn)題在一個(gè)2k x 2k個(gè)格組成的棋盤(pán)中恰有一個(gè)格與其他的不同稱為特殊格，想要求利用四種L型骨牌每個(gè)骨牌可覆蓋三個(gè)格不相互重疊覆蓋的將除了特殊格外的其他格覆蓋。二、問(wèn)題分析1普通背包問(wèn)題對(duì)于背包問(wèn)題，假設(shè)它的一個(gè)最優(yōu)解包含物品j，那么從該最優(yōu)解中拿出所含的物品j的那局部重量，剩余的將是n-1個(gè)原重物品1，2，······，j-1，j+1，·····，n以及重為i的物品j中可裝入容量為C的背包且具

3、有最大價(jià)值的物品。20/1背包問(wèn)題如果當(dāng)前背包中的物品的總?cè)萘渴莄w，前面的k-1件物品都已經(jīng)決定好是否要放入包中，那么第k件物品是否放入包中取決于不等式 cw + wk <= M (其中，wk為第k件物品的容量，M為背包的容量)此即約束條件 然后我們?cè)賹ふ蚁藿绾瘮?shù)，這個(gè)問(wèn)題比較麻煩，我們可以回憶一下背包問(wèn)題的貪心算法，即物品按照 物品的價(jià)值/物品的體積 來(lái)從大到小排列，然后最優(yōu)解為1，1，1.，1，t，0，0，.，其中0<=t<=1； 因此，我們?cè)诖_定第k個(gè)物品到底要不要放入的時(shí)候(在前k-1個(gè)物品已經(jīng)確定的情況下)，我們可以考慮我們能夠到達(dá)的最大的價(jià)值，即我們可以通過(guò)計(jì)算

4、只放入一局部的k物品來(lái)計(jì)算最大的價(jià)值。我們要確保當(dāng)前選擇的路徑的最大的價(jià)值要大于我們已經(jīng)選擇的路徑的價(jià)值。這就是該問(wèn)題的限界條件。通過(guò)該條件，可以減去很多的枝條，大大節(jié)省運(yùn)行時(shí)間。3棋盤(pán)覆蓋問(wèn)題每次都對(duì)分割后的四個(gè)小塊進(jìn)展判斷，判斷特殊格是否在里面。這里的判斷的法是每次先記錄下整個(gè)大塊的左上角格的行列坐標(biāo)，然后再與特殊格坐標(biāo)進(jìn)展比較，就可以知道特殊格是否在該塊中。如果特殊塊在里面，這直接遞歸下去求即可，如果不在，這根據(jù)分割的四個(gè)塊的不同位置，把右下角、左下角、右上角或者左上角的格標(biāo)記為特殊塊，然后繼續(xù)遞歸。在遞歸函數(shù)里，還要有一個(gè)變量s來(lái)記錄邊的格數(shù)，每次對(duì)塊進(jìn)展劃分時(shí)，邊的格數(shù)都會(huì)減半，這個(gè)

5、變量是為了便判斷特殊格的位置。其次還要有一個(gè)變nCount來(lái)記錄L型骨牌的數(shù)量。三、建立數(shù)學(xué)模型1普通背包問(wèn)題普通背包問(wèn)題的數(shù)學(xué)描述為：在選擇物品i裝入背包時(shí)，可以選擇物品i的一局部，而不一定要全部裝入背包，1in。C>0,wi>0,vi>0,1in,要求找出一個(gè)n元0-1向量x1,x2,x3,·····，xn,xi0,1，1in,使得C,而且到達(dá)最大。20/1背包問(wèn)題0-1背包問(wèn)題的數(shù)學(xué)描述為：不能將物品裝入背包屢次，也不能只裝入局部的物品i。 C>0,wi>0,vi>0,1in,要求找出一個(gè)n元0-1向量

6、x1,x2,x3,·····，xn,xi0,1，1in,使得C,而且到達(dá)最大。3棋盤(pán)覆蓋問(wèn)題當(dāng)k>0時(shí)，將2k×2k棋盤(pán)分割為4個(gè)2k-1×2k-1 子棋盤(pán)(a)所示。特殊格必位于4個(gè)較小子棋盤(pán)之一中，其余3個(gè)子棋盤(pán)中無(wú)特殊格。為了將這3個(gè)無(wú)特殊格的子棋盤(pán)轉(zhuǎn)化為特殊棋盤(pán)，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤(pán)的會(huì)合處，如 (b)所示，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤(pán)覆蓋問(wèn)題。遞歸地使用這種分割，直至棋盤(pán)簡(jiǎn)化為棋盤(pán)1×1。四、算法設(shè)計(jì)1普通背包問(wèn)題因?yàn)槊恳粋€(gè)物品都可以分割成單位塊，單位塊的利益越大顯然總收益越

7、大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解決。算法設(shè)計(jì)：首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后按單位重量?jī)r(jià)值從大到小進(jìn)展排序，根據(jù)貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包?；?qū)⑦@種物品全部裝入背包后，背包的物品總重量未超過(guò)背包容量C，那么選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包，依此策略一直進(jìn)展下去，直到背包裝滿為止。20/1背包問(wèn)題該0-1背包問(wèn)題采用的是回溯算法，回溯算法的根本解題步驟是： 1針對(duì)所給問(wèn)題定義問(wèn)題的解空間； 2確定易于搜索的解空間構(gòu)造； 3以深度優(yōu)先式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)防止無(wú)效的搜索。算法設(shè)計(jì)：a.物品有n種，背包容量為C

8、，分別用pi和wi存儲(chǔ)第i種物品的價(jià)值和重量，用xi標(biāo)記第i種物品是否裝入背包，用bestxi存儲(chǔ)第i種物品的最優(yōu)裝載案；b. 用遞歸函數(shù)Backtrack (i,cp,cw)來(lái)實(shí)現(xiàn)回溯法搜索子集樹(shù)形式參數(shù)i表示遞歸深度，n用來(lái)控制遞歸深度，形式參數(shù)cp和cw表示當(dāng)前總價(jià)值和總重量，bestp表示當(dāng)前最優(yōu)總價(jià)值： 假設(shè)i >n，那么算法搜索到一個(gè)葉結(jié)點(diǎn)，判斷當(dāng)前總價(jià)值是否最優(yōu)：1> 假設(shè)cp>bestp，更新當(dāng)前最優(yōu)總價(jià)值為當(dāng)前總價(jià)值即bestp=cp，更新裝載案即bestxi=xi( 1in)； 采用for循環(huán)對(duì)物品i裝與不裝兩種情況進(jìn)展討論0j1：1> xi=j；2

9、> 假設(shè)總重量不大于背包容量即cw+xi*wi<=c，那么更新當(dāng)前總價(jià) br=""> 值和總重量即cw+=wi*xi,cp+=pi*xi, 對(duì)物品i+1調(diào)用遞歸函數(shù)Backtrack(i+1,cp,cw) 繼續(xù)進(jìn)展裝載；3> 函數(shù)Backtrack(i+1,cp,cw)調(diào)用完畢后那么返回當(dāng)前總價(jià)值和總重量即 cw-=wi*xi,cp-=pi*xi；4> 當(dāng)j>1時(shí)，for循環(huán)完畢； 當(dāng)i=1時(shí)，假設(shè)已測(cè)試完所有裝載案，外層調(diào)用就全部完畢；c. 主函數(shù)調(diào)用一次backtrack(1,0,0)即可完成整個(gè)回溯搜索過(guò)程，最終得到的bestp和b

10、estxi即為所求最大總價(jià)值和最優(yōu)裝載案。3棋盤(pán)覆蓋問(wèn)題該棋盤(pán)算法用的是分治算法，分治法解題的思路就是將大問(wèn)題化為假設(shè)干子問(wèn)題，再依次解決子問(wèn)題，最后獲得問(wèn)題的答案。算法設(shè)計(jì)：1ChessBoard函數(shù)實(shí)現(xiàn)了遞歸的將棋盤(pán)劃分為子棋盤(pán)，并將棋盤(pán)進(jìn)展覆蓋。 2 main()函數(shù)用來(lái)進(jìn)展輸入棋盤(pán)的大小和特殊棋盤(pán)的位置。 3使用memset(Matrix,0,sizeof(Matrix)將Matrix數(shù)組清零。 五、算法實(shí)現(xiàn)1普通背包問(wèn)題#include <stdio.h>struct goodinfofloat p;/物品價(jià)值float w;/物品重量float x;/物品該放數(shù)量int

11、 flag;/物品編碼;void Insertionsort(goodinfo goods,int n)int i,j;for (j=2;j<=n;j+)goods0=goodsj;i=j-1;while (goods0.p >goodsi.p )goodsi+1=goodsi;i-;goodsi+1=goods0;/按物品效益重量比值做降序排列void bag(goodinfo goods,float M,int n)float cu;int i,j;for(i=1;i<=n;i+)goodsi.x=0;cu=M;for(i=1;i<=n;i+)if(goodsi.w

12、>cu)break; /當(dāng)物品重量大于剩余容量時(shí)跳出goodsi.x =1;cu=cu-goodsi.w ;/確定背包新的剩余容量if(i<=n)goodsi.x =cu/goodsi.w ;/該物品所要放的量/按物品編號(hào)做降序排列for(j=2;j<=n;j+)goods0=goodsj;i=j-1;while (goods0.flag <goodsi.flag )goodsi+1=goodsi;i-;goodsi+1=goods0;printf("最優(yōu)解為：n");for(i=1;i<=n;i+)printf("第%d件物品要放:

13、 %f",goodsi.flag ,goodsi.x );printf("n");void main()printf("-運(yùn)用貪心算法求解普通背包問(wèn)題-n");int j,n;float M;goodinfo *goods;while (j)printf("請(qǐng)輸入物品的總數(shù)量: ");scanf("%d",&n);goods= new struct goodinfon+1;printf("請(qǐng)輸入背包的最大容量: ");scanf("%f",&M);p

14、rintf("n");for (int i=1;i<=n;i+)goodsi.flag =i;printf("請(qǐng)輸入第%d個(gè)物品的重量：",i);scanf("%f",&goodsi.w );printf("請(qǐng)輸入第%d個(gè)物品的價(jià)值：",i);scanf("%f",&goodsi.p );goodsi.p =goodsi.p /goodsi.w ;printf("n");Insertionsort(goods,n);bag(goods,M,n);prin

15、tf("如果繼續(xù)那么選擇“1，如果完畢那么選擇“0n");scanf("%d",&j);20/1背包問(wèn)題#include<stdio.h>int n,c,bestp;/物品的個(gè)數(shù)，背包的容量，最大價(jià)值int p10000,w10000,x10000,bestx10000;/物品的價(jià)值，物品的重量，xi暫存物品的選中情況,物品的選中情況void Backtrack(int i,int cp,int cw) /cw當(dāng)前包物品重量，cp當(dāng)前包物品價(jià)值 int j; if(i>n)/回溯完畢 if(cp>bestp) bestp=

16、cp; for(i=0;i<=n;i+) bestxi=xi; else for(j=0;j<=1;j+) xi=j; if(cw+xi*wi<=c) cw+=wi*xi; cp+=pi*xi; Backtrack(i+1,cp,cw); cw-=wi*xi; cp-=pi*xi; int main() int i; bestp=0; printf("請(qǐng)輸入背包最大容量:n"); scanf("%d",&c); printf("請(qǐng)輸入物品個(gè)數(shù):n"); scanf("%d",&n)

17、; printf("請(qǐng)依次輸入物品的重量:n"); for(i=1;i<=n;i+) scanf("%d",&wi); printf("請(qǐng)依次輸入物品的價(jià)值:n"); for(i=1;i<=n;i+) scanf("%d",&pi); Backtrack(1,0,0); printf("最大價(jià)值為:n"); printf("%dn",bestp); printf("被選中的物品依次是(0表示未選中，1表示選中)n"); for(

18、i=1;i<=n;i+) printf("%d ",bestxi); printf("n"); return 0;3棋盤(pán)覆蓋問(wèn)題#include <stdio.h>#include <string.h>int nCount = 0;int Matrix100100;void chessBoard(int tr, int tc, int dr, int dc, int size);int main()printf("注意：矩陣大小為2的k次!n");int y=1;while(y)int size,r,c,

19、row,col;memset(Matrix,0,sizeof(Matrix);printf("請(qǐng)輸入矩陣的大小:n");scanf("%d",&size);printf("請(qǐng)輸入特殊矩陣的坐標(biāo):n");scanf("%d%d",&row,&col);chessBoard(0,0,row,col,size);for (r = 0; r < size; r+)for (c = 0; c < size; c+)printf("%2d ",Matrixrc);prin

20、tf("n");printf("如果繼續(xù)那么按“1，退出那么按“0：");scanf("%d",&y); return 0;void chessBoard(int tr, int tc, int dr, int dc, int size) /覆蓋左上角子棋盤(pán) int s,t; if (1 = size) return; s = size/2; /分割棋盤(pán) t = + nCount;/L型骨牌號(hào) /特殊格在此棋盤(pán)中 if (dr < tr + s && dc < tc +s) chessBoard(t

21、r,tc,dr,dc,s); else Matrixtr+s-1tc+s-1 = t; chessBoard(tr,tc,tr+s-1,tc+s-1,s); /locate the special grid on bottom left corner if (dr < tr + s && dc >= tc + s ) chessBoard(tr,tc+s,dr,dc,s); else Matrixtr+s-1tc+s = t; chessBoard(tr,tc+s,tr+s-1,tc+s,s); /locate the special grid on top right corner if (dr >= tr + s && dc < tc + s) chessBoard(tr+s,tc,dr,dc,s); else Matrixtr+stc+s-1 = t; chessBoard(tr+s,tc,tr+s,tc+s-1,s); /locate the special grid on top left corner if (dr >= tr + s && dc >= tc + s) chessBoard