1、.算法設計與分析什么是算法？算法的特征有哪些？根據我自己的理解，算法是解決問題的方法步驟。比如在解決高數(shù)問題的時候，可以分步驟進行解答，在編程的過程算法可以得到最好的體現(xiàn)。算法是一系列解決問題的清晰指令， 因為我最近在考研復習， 對于會的題目還有進行多次的鞏固， 但是一步步的寫很浪費時間， 所以我只是寫出關鍵指令， 比如化簡通分，洛必達法則，上下同階。這樣可以提高效率。 算法的指令也是同樣的。能夠對一定規(guī)范的輸入， 在有限時間內獲得所要求的輸出。 一個算法的優(yōu)劣可以用空間復雜度與時間復雜度來衡量。若給定某一算法，一般如何對其分析與評價？一個算法的復雜性的高低體現(xiàn)在運行該算法所需要的計算機資源的

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

3、)的值很小，則算法優(yōu)。作為初學者，我.們可以用 f(n)的數(shù)量級 O 來粗略地判斷算法的時間復雜性，如上例中的時間復雜性可粗略地表示為T(n)=O(n2)。2.空間復雜性 :例 2:將一一維數(shù)組的數(shù)據 (n 個)逆序存放到原數(shù)組中 ,下面是實現(xiàn)該問題的兩種算法 :算法 1:for i:=1 to n dobi:=an-i+1;for i:=1 to n doai:=bi;算法 2:for i:=1 to n div 2 dobegint:=ai;ai:=an-i-1;an-i-1:=tend;算法 1 的時間復雜度為2n,空間復雜度為2n算法 2 的時間復雜度為3*n/2, 空間復雜度為 n+

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

5、的可行解，需要選擇一個B 后再去找 A動態(tài)規(guī)劃算法之 0-1 背包問題：給定 n 種物品和一個背包。物品 i 的重量是Wi，其價值為 Vi，背包的容量為 C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大 ?與 0-1 背包問題類似，所不同的是在選擇物品 i 裝入背包時，可以選擇物品 i 的一部分，而不一定要全部裝入背包， 1in。這 2 類問題都具有最優(yōu)子結構性質，極為相似，但背包問題可以用貪心算法求解，而 0-1 背包問題卻不能用貪心算法求解。 用貪心算法解背包問題的基本步驟是，首先計算每種物品單位重量的價值 Vi/Wi ，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品

6、裝入背包。 若將這種物品全部裝入背包后， 背包內的物品總重量未超過 C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。具體代碼如下：1. /4d2 貪心算法 背包問題2. #include "stdafx.h"3. #include <iostream>4. using namespace std;5.6. const int N = 3;7.8. void Knapsack(int n,float M,float v,float w,float x);9.10. int main()11. 12. float M

7、= 50;/ 背包所能容納的重量.13. / 這里給定的物品按單位價值減序排序14. float w = 0,10,20,30;/ 下標從 1 開始15. float v = 0,60,100,120;16.17. float xN+1;18.19. cout<<" 背包所能容納的重量為： "<<M<<endl;20. cout<<" 待裝物品的重量和價值分別為： "<<endl;21. for(int i=1; i<=N; i+)22. 23. cout<<"&qu

8、ot;<<i<<":("<<wi<<","<<vi<<")"<<endl;24. 25.26. Knapsack(N,M,v,w,x);27.28. cout<<" 選擇裝下的物品比例如下： "<<endl;29. for(int i=1; i<=N; i+)30. 31. cout<<""<<i<<":"<<xi&

9、lt;<endl;32. 33.34. return 0;35. .36.37. void Knapsack(int n,float M,float v,float w,float x)38. 39. /Sort(n,v,w);/ 這里假定 w,v 已按要求排好序40. int i;41. for (i=1;i<=n;i+)42. 43. xi=0;/ 初始化數(shù)組 x44. 45.46. float c=M;47. for (i=1;i<=n;i+)/ 物品整件被裝下 ,xi=148. 49. if (wi>c)50. 51.break;52. 53. xi=1;54.

10、 c-=wi;55. 56.57. / 物品 i 只有部分被裝下58. if (i<=n).59. 60. xi=c/wi;61. 62. 程序運行結果為：動態(tài)規(guī)劃之 01 背包狀態(tài)轉換方程 fi,j = Max fi-1,j-Wi+Pi( j >= Wi ),fi-1,j fi,j表示在前 i 件物品中選擇若干件放在承重為j 的背包中，可以取得的最大價值。Pi 表示第 i 件物品的價值。決策：為了背包中物品總價值最大化，第i 件物品應該放入背包中嗎？題目描述：有編號分別為 a,b,c,d,e 的五件物品，它們的重量分別是 2,2,6,5,4，它們的價值分別是 6,3,5,4,6，

11、現(xiàn)在給你個承重為 10 的背包，如何讓背包里裝入的物品具有最大的價值總和？naweval1234567891meightue0a26066991111122555b230336699911.01c65000666661101d54000666661100e460006666666這張表是至底向上，從左到右生成的。為了敘述方便，用e2 單元格表示 e 行 2 列的單元格，這個單元格的意義是用來表示只有物品 e 時，有個承重為 2 的背包，那么這個背包的最大價值是0，因為 e 物品的重量是 4，背包裝不了。對于 d2 單元格，表示只有物品 e，d 時,承重為 2 的背包 ,所能裝入的最大價值，仍然

12、是 0，因為物品 e,d 都不是這個背包能裝的。同理， c2=0 ，b2=3,a2=6 。對于承重為 8 的背包， a8=15, 是怎么得出的呢？根據 01 背包的狀態(tài)轉換方程，需要考察兩個值，一個是 fi-1,j, 對于這個例子來說就是b8 的值 9，另一個是 fi-1,j-Wi+Pi ；在這里，fi-1,j 表示我有一個承重為8 的背包，當只有物品b,c,d,e 四件可選時，這個背包能裝入的最大價值fi-1,j-Wi 表示我有一個承重為6 的背包（等于當前背包承重減去物品a 的重量），當只有物品b,c,d,e 四件可選時，這個背包能裝入的最大價值fi-1,j-Wi 就是指單元格b6,值為

13、9，Pi 指的是 a 物品的價值，即6.由于 fi-1,j-Wi+Pi = 9 + 6 = 15大于 fi-1,j = 9 ，所以物品 a 應該放入承重為8的背包以下是 actionscript3的代碼1. public function get01PackageAnswer(bagItems:Array,bagSize:int):Array2. 3. var bagMatrix:Array=;4. var i:int;5. var item:PackageItem;6. for(i=0;i<bagItems.length;i+)7. 8.bagMatrixi = 0;9. 10. fo

14、r(i=1;i<=bagSize;i+)11. 12. for(var j:int=0;j<bagItems.length;j+)13. 14.item = bagItemsj as PackageItem;15.if(item.weight > i)16.17./i 背包轉不下 item18.if(j=0)19.20.bagMatrixji= 0;21.22.else23.24.bagMatrixji=bagMatrixj-1i;25.26.27.else28.29./ 將 item 裝入背包后的價值總和30.var itemInBag:int;31.if(j=0)32.3

15、3.bagMatrixji= item.value;34.continue;35.36.else37.38.itemInBag =bagMatrixj-1i-item.weight+item.value;39.40.bagMatrixji = (bagMatrixj-1i > itemInBag ? bagMatrixj-1i : itemInBag)41.42. 43. 44. /find answer45. var answers:Array=;46. var curSize:int = bagSize;47. for(i=bagItems.length-1;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();57.break;58. 59. if(bagMatrixicurSize-bagMatrixi-1curSize-item.weight=item.value)60. 61.answers.push();62.curSiz