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

1、算法設(shè)計(jì)與分析1 什么就是算法？算法得特征有哪些？根據(jù)我自己得理解，算法就是解決問題得方法步驟。比如在解決高數(shù)問題得時(shí)候，可以分步驟進(jìn)行解答，在編程得過程算法可以得到最好得體現(xiàn)。算法就是一系列解決問題得清晰指令，因?yàn)槲易罱诳佳袕?fù)習(xí)，對于會得題目還有 進(jìn)行多次得鞏固，但就是一步步得寫很浪費(fèi)時(shí)間，所以我只就是寫出關(guān)鍵指令，比 如化簡通分，洛必達(dá)法則，上下同階。這樣可以提高效率。算法得指令也就是同樣 得。能夠?qū)σ欢ㄒ?guī)范得輸入，在有限時(shí)間內(nèi)獲得所要求得輸出。一個(gè)算法得優(yōu)劣 可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。2 若給定某一算法，一般如何對其分析與評價(jià)？一個(gè)算法得復(fù)雜性得高低體現(xiàn)在運(yùn)行該算法所需要得計(jì)

2、算機(jī)資源得多少上面，所需得資源越多，我們就說該算法得復(fù)雜性越高；反之，所需得資源越低，則該算 法得復(fù)雜性越低。計(jì)算機(jī)得資源，最重要得就是時(shí)間與空間(存儲器)資源。算法得復(fù)雜性有時(shí)間復(fù)雜 性與空間復(fù)雜性之分。1、時(shí)間復(fù)雜性：例1:設(shè)一程序段如下(為討論方便，每行前加一行號)(1) for i:=1 to n do(2) for j:=1 to n do x:=x+1、試問在程序運(yùn)行中各步執(zhí)行得次數(shù)各為多少？解答：行號次數(shù)(頻度)(1)n+1n *( n+1)n*n可見,這段程序總得執(zhí)行次數(shù)就是：f(n)=2n2+2n+1。在這里,n可以表示問題得規(guī)模，當(dāng)n趨向無窮大時(shí)，如果f(n)得值很小，則算

3、法優(yōu)。作為初學(xué)者，我們可以 用f(n)得數(shù)量級0來粗略地判斷算法得時(shí)間復(fù)雜性，如上例中得時(shí)間復(fù)雜性可粗 略地表示為T(n)=0(n2)。2、空間復(fù)雜性：例2:將一一維數(shù)組得數(shù)據(jù)(n個(gè))逆序存放到原數(shù)組中，下面就是實(shí)現(xiàn)該問題得兩種 算法：算法 1:for i:=1 to n dobi:=a ni+1;for i:=1 to n doai:=bi;算法 2:for i:=1 to n div 2 dobeg int:=ai;ai:=a ni1;a ni1:=tend;算法1得時(shí)間復(fù)雜度為2n,空間復(fù)雜度為2n算法2得時(shí)間復(fù)雜度為3*n/2,空間復(fù)雜度為n+1顯然算法2比算法1優(yōu),這兩種算法得空間復(fù)

4、雜度可粗略地表示為S(n)=O(n)3、從下面算法策略中自選一組，結(jié)合某具體問題得求解來介紹算法思想，并加 以總結(jié)、比較：遞歸與分治、動態(tài)規(guī)劃與貪心法、回溯法與分支限界法動態(tài)規(guī)劃算法類似于分治法，基本思想也就是將待求解問題分解成若干個(gè)子 問題?；麨榱?，減少了運(yùn)算量。貪心算法，就是永不知足得求最優(yōu)解，有點(diǎn)類似于我們所說得完美主義者。兩者之間有相同點(diǎn)，總結(jié)來說某種程度上，動規(guī)就是貪心得泛化，貪心就是動 規(guī)得特例貪心:A最優(yōu)+B最優(yōu)動態(tài)規(guī)劃:(A+B)最優(yōu)就單步而言貪心得A最優(yōu)就是前一步得結(jié)果,B最優(yōu)需要遍歷找到動態(tài)規(guī)劃得A為前一步得可行解，需要選擇一個(gè)B后再去找A動態(tài)規(guī)劃算法之01背包問題:給定

5、n種物品與一個(gè)背包。物品i得重量就是 Wi,其價(jià)值為Vi,背包得容量為C。應(yīng)如何選擇裝入背包得物品,使得裝入背包中 物品得總價(jià)值最大？與01背包問題類似，所不同得就是在選擇物品i裝入背包時(shí)，可以選擇物品i得一 部分，而不一定要全部裝入背包,1 < i < n。這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而01背包問題卻不能用貪心算法求解。用貪心算法解背包問題得基本步驟就是,首先計(jì)算每種物品單位重量得價(jià)值 Vi/Wi,然后,依貪心選擇策略，將盡可能多得單位重量價(jià)值最高得物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)得物品總重量未超過C,則選擇單位重量價(jià)值

6、次高得物品并盡可能多地裝入背包。 依此策略一直地進(jìn)行下去，直到背包裝滿為止。具體代碼如下：1. 4d2貪心算法背包問題2. #include "stdafx 、h"3. #i nclude <iostream>4. using n amespace std;5.5. const int N = 3;7.6. void Knapsack(int n,float M,float v,float w,float x);9.7. int main8. 9. float M = 50;/ 背包所能容納得重量10. /這里給定得物品按單位價(jià)值減序排序11. float w

7、= 0,10,20,30;/ 下標(biāo)從 1 開始12. float v = 0,60,100,120;16.13. float xN+1;18.14. cout«"背包所能容納得重量為："vvMvvendl;15. coutvv"待裝物品得重量與價(jià)值分別為:"<<e ndl;16. for(inti=1; i<=N; i+)17. 18. coutvvTvvivv":("v<wivv","vvvivv")"vve ndl;19. 25.20. Kn apsack(

8、N,M,v,w,x);27.21. coutvv"選擇裝下得物品比例如下:"<<endl;22. for(int i=1; i<=N; i+)23. 24. coutvv""v<ivv":"vvxivve ndl;25. 33.26. return 0;27. 36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.void Knapsack(int n,float M,float v,float w,float x) Sort(

9、n,v,w);這里假定w,v已按要求排好序int i;for (i=1;i<=n ;i+)xi=0;初始化數(shù)組xfloat c=M;for (i=1;i<=n;i+)物品整件被裝下,xi=1if (wi>c)break;xi=1;c=wi;/物品i只有部分被裝下 if (i<=n)60. xi=c/wi;61. 62. 程序運(yùn)行結(jié)果為：動態(tài)規(guī)劃之01背包狀態(tài)轉(zhuǎn)換方程 fi,j = Max fi1,jWi+Pi( j >= Wi ),fi1,j fi,j表示在前i件物品中選擇若干件放在承重為j得背包中，可以取得得最 大價(jià)值。Pi表示第i件物品得價(jià)值。決策:為了背包中

10、物品總價(jià)值最大化，第i件物品應(yīng)該放入背包中嗎？題目描述：61296有編號分別為a,b,c,d,e得五件物品，它們得重量分別就是2,2,6,5,4,它們得 價(jià)值分別就是6,3,5,4,6,現(xiàn)在給您個(gè)承重為10得背包，如何讓背包里裝入得物品 具有最大得價(jià)值總與？nawevalmeightuea26b23c656 6 6 6 60 06 6 6 6 6 6 6這張表就是至底向上，從左到右生成得。為了敘述方便，用e2單元格表示e行2列得單元格，這個(gè)單元格得意義就是 用來表示只有物品e時(shí)，有個(gè)承重為2得背包，那么這個(gè)背包得最大價(jià)值就是0,因 為e物品得重量就是4,背包裝不了。對于d2單元格，表示只有物品

11、e,d時(shí),承重為2得背包，所能裝入得最大價(jià)值, 仍然就是0,因?yàn)槲锲積,d都不就是這個(gè)背包能裝得。同理,c2=0,b2=3,a2=6。對于承重為8得背包,a8=15,就是怎么得出得呢？根據(jù)01背包得狀態(tài)轉(zhuǎn)換方程，需要考察兩個(gè)值，一個(gè)就是fi1,j,對于這個(gè)例子來說就就是b8得值9,另一個(gè)就是 fi1,jWi+Pi;在這里，fi1,j表示我有一個(gè)承重為8得背包,當(dāng)只有物品b,c,d,e四件可選時(shí),這個(gè)背 包能裝入得最大價(jià)值fi1,jWi表示我有一個(gè)承重為6得背包（等于當(dāng)前背包承重減去物品a得重 量），當(dāng)只有物品b,c,d,e四件可選時(shí)，這個(gè)背包能裝入得最大價(jià)值fi1,jWi就就是指單元格b6,值

12、為9,Pi指得就是a物品得價(jià)值，即6由于fi1,jWi+Pi = 9 + 6 = 15 大于fi1,j = 9,所以物品a應(yīng)該放入承重 為8得背包1. public fun ctio n getO1PackageA nswer(bagltems:Array,bagSize:i nt):Arrayvar bagMatrix:Array=;var i:i nt;var item:Packageltem;for(i=0;i<bagltems 、 length;i+)bagMatrixi = 0;for(i=1;i<=bagSize;i+)for(var j:int=0;j<bagl

13、tems 、 length;j+)item = bagItemsj as PackageItem;if(item 、weight > i)/i背包轉(zhuǎn)不下itemif(j=0)bagMatrixji = 0;2. 3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.else23.24.bagMatrixji=bagMatrixj1i;25.26.27.else28.29./ 將 item 裝入背包后得價(jià)值總與30.var itemInBag:int;31.if(j=0)32.33.bagMatrixji = item、 value;34

14、.continue;35.36.else37.38.itemInBag = bagMatrixj1iitemweight+item、value;39.40.bagMatrixji = (bagMatrixj1i > itemInBagbagMatrixj1i : itemInBag)41. 44./find answer45.var answers:Array=;46.var curSize:int = bagSize;47.for(i=bagItems 、 length1;i>=0;i)48.49.item = bagItemsi as PackageItem;50.if(curSize=0)51.52.break;53.54.if(i=0 && curSize > 0)55.56.answers 、 push(item 、name);57.break;58.59.if(bagMatrixicurSizebagMatrixi1curSizeitemweight=item 、value)60.61.answers 、 push(item 、name);62.curSize =