西電軟件學院算法實驗報告模板2份

word文檔精品文檔分享第二次驗一、問題：Matrix-chainproduct分析：此題是矩陣鏈乘問題，需要求出最優(yōu)括號化方案。即矩陣的乘法鏈上添加括號來改變運算順序以使矩陣鏈乘法的代降?？梢苑治鲈撴湷说囊粋€子段總結(jié)一結(jié)。假m[i,j]表示i*?*Aj的鏈

成需要進展的乘法次〔假j-ii*?*Aj分為兩段進展i*?*A〕*〔Ak+1*?*Aj〕可以得出m[i,j]的遞推公式可以得出，當i=j的時候，m[i,j]=0。當i<j的時候。k的取值X是i到j-1，對k的每一個取值都可以得到一個m[i,j]的值，取出最小值即時m[i,j]的最優(yōu)化方案。遞推公式如下：可以根據(jù)上式得到一個遞歸算法。此題即是求m[1,n]的值。用二維m存儲m[i,j]的值，用二維s來儲存應當分割的位。以此題中第一個矩陣a)<3,5,2,1,10>為例，可以得出如下矩陣：1word文檔精品文檔分享通過m數(shù)組可以得出最少的乘法次數(shù)，通過s數(shù)組可以輸出最優(yōu)方案。遇到的問題：在輸出s數(shù)組的結(jié)果的時候仍然需要遞歸調(diào)用，需要適宜的控制遞歸的條件?？偨Y(jié)：在矩陣鏈乘問題中可以看出，動態(tài)規(guī)劃結(jié)合遞歸的思想可以快捷的解決很多問題。此題中，重點是歸納出m[i,j]的遞推公式。二、問題：LongestCommonSubsequence分析：此題即是最長公共子序列問題。假設有序列A[m]和序列B[n]，顯然，對

于每一個[i,j]，都對應著一個公共子序列的長度。假設長度為，就可以得到一個二維數(shù)組c[m,n]。對于c[i,j]，當Ai=Bj的時候，問題就轉(zhuǎn)變?yōu)榍驛[1..i-1]和B[1..j-1]的公共子序列長度的問題，所以c[i，j]的長度就是c[i-1，j-1]+1;同理，當Ai!=Bj的時候，c[i,j]應該在c[i-1,j]與c[i,j-1]中取最大值。另外，當i或者j等于0的時候，顯然c的值為0。由上面所述，可以得到遞推公式如下：為了解決這個問題，還如要定義另一個數(shù)組用于存放c數(shù)組中每一個元素的來源。這個來源其實就反映了公共子串?？梢酝ㄟ^箭頭表示來源，相連的箭頭序列中指向左上方的箭頭最多的一串對應的就是最長公共子序列。比方對于題目中給出的第一個例子X:xzyzzyxY:zxyyzxz可以用一個矩陣表示計算的過程：2word文檔精品文檔分享遇到的問題：’是屬于‘’還是‘’會給結(jié)果帶來不同。在輸出子序列的時候，最長公共子序列可能不止一個，但是最終未能解決還是只能輸出一個?？偨Y(jié)：最長公共子序列問題可以利用動態(tài)規(guī)劃很好的解決。動態(tài)規(guī)劃的思想就是根據(jù)規(guī)律獲得推導公式，然后解決問題。三、問題：LongestCommonSubstring分析：最長公共子序列問題就是和最長公共子串問題差不多，就是當當Ai!=Bj的時候，對應的c[i，j]置為0。推導公式如下：最終c數(shù)組的最大值max對應的就是最長公共子串，只需要將從本位置向前述max-1個的子串即是所求子串?？偨Y(jié)：此題就是第二題的一種特殊的情況，即c數(shù)組中的值不能從左和上兩個方向獲取，其他根本一樣。在代碼上，只需要修改小局部代碼就可以實現(xiàn)該問題。四、問題：MaxSum分析：求和最大的子串。這個問題和第三題很像，不過這次不用二維數(shù)組而是使用兩個標記來標志所求子串的起始位置〔〕完畢位置〔maxe是，對于第i個元素，如果當前元素與目前選中的序列的sum小于0，那么這么序列不會被選擇，更新sumb與sume的值；如果sum仍然大于0，那么sum可以選中。比擬sum與maxsum>maxmaxb與maxe3word文檔精品文檔分享的值。遞推公式如下：遇到的問題：在全是負數(shù)時出現(xiàn)問題，后來講max的初始值設置為第一個元素的值后就能正常了?？偨Y(jié)：動態(tài)規(guī)劃能解決很多問題，找到遞推公式非常重要。五、問題：Shortestpathinmultistagegraphs.Findtheshortestpathfrom0to15forthefollowinggraph.分析：觀察此題圖的特點，發(fā)現(xiàn)可以將圖分解為7個局部，以此可以計算到每一個節(jié)點的最短的路徑。即可求出最終的最短路徑?？偨Y(jié)：結(jié)合此題中的特殊情況，可以采用適當?shù)姆椒▉硖幚怼?word文檔精品文檔分享第三次實驗一、問題：KnapsackProblem.Thereare5itemsthathaveavalueandweightlistbelow,theknapsackcancontainatmost100Lbs.Solvetheproblembothasfractionalknapsackand0/1knapsack.分析：此題是背包問題的兩個解法。對于局部背包來說比擬簡單，就是將單位價值大的物品優(yōu)先放置到背包中，這樣就能在背包中獲取最大的價值。但是對于0/1背包問題來說，就相對復雜了。可以通過貪心算法解決。經(jīng)過分析，我們轉(zhuǎn)化這個問題為將n件物品放置到容量為w的容器中。這里，每件物品只可能有一個狀態(tài)：放入/不放入，我們用0/1來對應。用v[i,w]來表示前i件物品選出重量不超過w的物品，并且構(gòu)成的最大的價值。那么，可以分析

得出v[i,w]的遞推式。如果i=0或者v[I,w]=0;如果第i件物品的重量wi>w那么i不可能放入容器中；如果i能夠放入容器〔即wi<w〕那么在vi+v[i-1,w-wi]>v[i-1,w]時才可能會放入。關(guān)系式如下每一次都恰到好處的選擇了放或者不放一個物品。直到最后一個物品，我們得到的一定就是最好的結(jié)果總結(jié)：背包問題是一個典型的貪心算法的例子。在解決問題的時候可以將當前步驟做到最好，然后通過推導，有可能得到一個關(guān)系式，這樣就能使問題得到解決。在此題中，我們可以通過第i件物品是否應該放在容量的w的背包中進展分析，最終得到了一個遞推式。5word文檔精品文檔分享二、問題：Asimpleschedulingproblem.Wearegivenjobsj1,jn,allwithknownrunningtimest1,t2,tn,respectively.Wehaveasingleprocessor.Whatisthebestwaytoschedulethesejobsinordertominimizetheaveragecompletiontime.Assumethatitisanonpreemptivescheduling:onceajobisstarted,itmustruntocompletion.Thefollowingisaninstance。分析：這是一個線程調(diào)度問題，通過操作系統(tǒng)課程的學習，我們了解到應當采用短作業(yè)優(yōu)先的調(diào)度方式?？梢圆捎每焖倥判?qū)M程順序進展排序即可得到調(diào)度時間?？偨Y(jié)：在進程調(diào)度問題中，如果想獲取最短的平均周轉(zhuǎn)時間〔單線程〕應當使用短作業(yè)優(yōu)先的算法。三、問題：單源點最短路徑分析：此題中，因為路徑中存在負邊，所以應當使用bellman-ford算法。為了方便的使用該算法，需要首先創(chuàng)立適宜的邊的數(shù)據(jù)構(gòu)造。這樣，在遍歷邊的時候比擬快捷。首先需要初始化每一個節(jié)點的d值，源點的d值為0，其他點的d值的初始值為max〔一個足夠大的數(shù)〕。表示在初始時，源點到各點都不可達。然后，對每條邊進展松弛操作，進展|V|-1次松弛之后，可以得到結(jié)果。隨如果依然存在可松弛的節(jié)點的話，說明存在權(quán)重為負的環(huán)路。說明結(jié)果不存在?？偨Y(jié)：該算法并沒有在一開場就計算是否存在權(quán)值為負的環(huán)路。而是通過結(jié)果來分析，如果沒有負環(huán)路，一定能在松弛循環(huán)完畢后便不能繼續(xù)被松弛。由此，可以判斷是否存在最短路徑。所以，該算法不僅可以判斷一個圖是否存在最短路徑，還能得到最短路徑。四、問題：6word文檔精品文檔分享All-pairsshortestpaths分析：所有節(jié)點對的最短路徑問題，應當使用Johnson算法。Johnson算法需要用dijkstra和bellman-ford算法作為子程序。如果圖G=〔V,E〕中所有的邊權(quán)重都為非負值，可以通過在每一個節(jié)點使用dijkstra算法求出所有節(jié)點虹之間的最短路徑；如果該圖包含權(quán)值為負的邊，但是沒有權(quán)重為負的環(huán)路，那么只要計算一組新的非負權(quán)重值，然后使用同樣的方法即可?？偨Y(jié)：Johnson算法相當于是對dijkstra算法和bellman-ford算法的應用，結(jié)合這兩個算法，通過使用重新賦值權(quán)重來生成非負權(quán)重，最終得到所有節(jié)點對之間的最短路徑。7word文檔精品文檔分享第四次實驗一、題目：0/1KnapsackProblem.Thereare5itemsthathaveavalueandweightlistbelow,theknapsackcancontainatmost100Lbs.Solvetheproblemusingback-trackingalgorithmandtrytodrawthetreegenerated.分析：使用回溯法解決0/1背包問題?？梢杂靡粋€數(shù)組來記錄“選中〞物品的情況。首先，選擇第一件物品，如果超重的話不選擇該物品；如果沒有超重，繼續(xù)添加下一個物品，這樣選擇下去，最終一定可以選擇完全部的物品。計算目前選擇物品的totalValue值。繼續(xù)回溯，如果的到新的totalValue值，如果大于前一個值，那么更新該值，并且更新保存選擇的數(shù)組中?？偨Y(jié)：從8皇后問題可以發(fā)現(xiàn)回溯法的一般方法。經(jīng)過代入到這個問題中，發(fā)現(xiàn)確實可行?；厮莘ㄐ枰粋€合理的遞歸函數(shù)，這個函數(shù)的終止條件也需要認真的分析。比方這一題和8皇后問題都可以使用元素的個數(shù)作為一個完畢條件，另外還需要注意導致“回溯〞的位置。二、題目：Solvethe8-Queenproblemusingback-trackingalgorithm.分析：8皇后問題是回溯法的一個典型的例題。假設目前已經(jīng)在奇葩的前ii<8〕行放置了i和皇后并且位置合法。然后我們放置第j〔j=i+1〕個皇后，先將j放置在第一列，如果合法就放置第j+1個皇后；如果放置在當前列不合法，就將j皇后放置在第二列,,以此類推，如果全部不行，將會返回調(diào)用該函數(shù)的上一層函數(shù)。如果i的值等于，說明已經(jīng)完全擺放成功，就可以輸出結(jié)果，輸出后返回上一層調(diào)用，繼續(xù)查找其他的符合題意的皇后擺放?？偨Y(jié)：使用回溯法，能后很好的解決8皇后問題。在使用回溯法是，應當注意8word文檔精品文檔分享如何使用遞歸調(diào)用，尤其是遞歸調(diào)用的完畢條件。9word文檔精品文檔分享第2份算法導論上機實驗報告冊班級：1313012學號X：周家煒教師：X立勇10word文檔精品文檔分享11word文檔精品文檔分享實驗一排序算法題目一：1、題目描述：描述一個運行時間為θ(nlgn)算法，給定n個整數(shù)的集合S和另一個整數(shù)xS中是否存在兩個其和剛好為x的元素。、所用算法：1、運用歸并排序算法2、在已經(jīng)排好序的根底上，對其運用二分查找。、算法分析：〔時間復雜度為θ(nlgn)滿足題目要求的運行時間。歸并排序的分解局部是每次將數(shù)組劃分兩個局部，時間復雜度為1直到將數(shù)組分解成單個元素為止；解決局部是遞歸求解排序子序列；合并局部是將已經(jīng)排序的子序列進展合并得到所要的答案，時間復雜度為θ(lgn)?！拨?lgn)在題目要求的X圍內(nèi)，二分查找的條件為待查的數(shù)組為有序序列。算法的主要思想為設定兩個數(shù)，low指向最低元素，high指向最高元素，然后比擬數(shù)組中間的元素與待查元素進展比擬。如果待查元素小于中間元素，那么說明查找元素在數(shù)組的前半段；反之，如果待查元素大于中間元素，那么表明查找元素在數(shù)組的后半段。、結(jié)果截圖：12word文檔精品文檔分享5、總結(jié)：〔1〕在主函數(shù)中調(diào)用二分查找的時候，參數(shù)應該為]，從j+1開場遍歷而不是都是從第一個開場。〔〕遇到的困難為：由于程序語言規(guī)定數(shù)組的下標從0開場，而算法偽代碼要求從1，但是在編譯運行的時候會得不到想要的結(jié)果，出現(xiàn)數(shù)組下標訪問錯誤。采取的解決方案為：在開場定義數(shù)組的時候，將數(shù)組的大小定義為一個較大的數(shù)字，如1000。防止在運行時出現(xiàn)錯誤，但是造成了空間的浪費。較好的方案為使用動態(tài)數(shù)組，如malloc函數(shù)。13word文檔精品文檔分享題目二：1實現(xiàn)優(yōu)先級隊列，即需要支持以下操作：INSERT(S,x):把元素x插入到集合S中；MAXMUM(S):返回S中具有最大key的元素；EXTRACT-MAX(S):掉并返回S中的具有最大key的元素；INCREASE-KEY(S,x,k)元素x的關(guān)鍵字值增到k。2、所用算法：堆排序，運用堆來實現(xiàn)優(yōu)先隊列。3、算法分析：〔堆排序的時間復雜度是θ(nlgn),但是與歸并排序不同的是堆排序具有空間的原址性，任何時候都只需要常數(shù)個額外的元素空間存儲臨時數(shù)據(jù)。堆排序算法分為3個過程，MAX-HEAPIEY:調(diào)整堆以滿足小頂堆性質(zhì)，其時間復雜度為θ(lgn)；BUILD-MAXHEAP:從無序的輸入數(shù)據(jù)數(shù)組中構(gòu)造小頂堆，其時間復雜度為線性時間;HEAP-SORT:對數(shù)組進展原址排序，其時間復雜度為θ(nlgn)?！?〕在堆的根底上實現(xiàn)優(yōu)先隊列TMAXMUM、EXTRACT-MAXINCREASE-KE時間復雜度為θ)、結(jié)果截圖：14word文檔精品文檔分享5、總結(jié)：遇到的困難：沒有理解將一個序列轉(zhuǎn)換成小頂堆的過程，因此剛開場很難將偽代碼用c語言進展實現(xiàn)。從結(jié)果可以看出，在編寫MAX-EXSTRACT數(shù)的時候，當去掉第一個元素后，程序沒有調(diào)用MAX-HEAP進展調(diào)整堆，因此最后序列是無序狀態(tài)。題目三：1實現(xiàn)quick_sort算法，并且答復以下兩個問題：〔〕待排數(shù)組中的元素值都一樣的情況下，運用quick_sort需要進展多少次比擬？〔2〕對于n個元素的數(shù)組，運用quick_sort舉出需要進行比擬次數(shù)的上限和下限是多少？2、所用算法：快速排序算法15word文檔精品文檔分享3快速排序采用分治策略，時間復雜度為θ(nlgn),但是2),并且快速排序算法屬于原地排序，并不需要開辟

最壞情況下為θ(nA[p..r]被劃分為兩個子數(shù)組A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每個元素都小于A[q],而A[q]也小于等于A[q+1..r]中的每個元素。而在實現(xiàn)的過程總是選擇將A[r]作為基準點進展劃分A[p..r]數(shù)組。、結(jié)果截圖：、總結(jié)：1〕中選取第一個或者最后一個為基準點時，當n個元素一樣的時候為最壞情況，比擬次數(shù)為n*(n-1)/2;(2)快速排序比2)。較次數(shù)最少為θ最大的比擬次數(shù)為θ(n16word文檔精品文檔分享題目四：、題目描述：運用分治的策略將兩個已經(jīng)排好序的序列中，找出第k大的元素，且要求時間復雜度為θ(lgm+lgn),其中m和n分別為兩個序列的長度。2、所用策略：分治策略3、算法分析：〔1〕分解：因為已經(jīng)是兩個獨立的的序列，所以不用進展分解。〔2〕解決：因為兩個序列為已經(jīng)排好的序列，因此不用分開進展排序?！?〕利用歸并排序中的merge函數(shù)，將這兩個序列分別看成是L[]和R[]兩個數(shù)組，通過開辟一個新的數(shù)組，將兩個數(shù)組合并成一個新的排好序的序列，在根據(jù)要求的k值，對新的數(shù)組進展取值。、結(jié)果截圖：17word文檔精品文檔分享、總結(jié)：〔1〕理解分治策略的三個步驟：分解、解決和合并對于具體問題的具體表現(xiàn)，要善于根據(jù)時間復雜度與所學的算法進展結(jié)合，找出可以利用的地方。實驗二動態(tài)規(guī)劃題目一：1、題目描述：用動態(tài)規(guī)劃實現(xiàn)矩陣鏈乘，保證相乘的次數(shù)最少。2、所用策略：動態(tài)規(guī)劃3、算法分析：〔1Ai..k與Ak+1..j的乘積，那么分別對Ai..k與Ak+1..j加括號的方式也一定是最優(yōu)的。〔2〕定義m[i,j]為計算矩陣Ai..j所需標量乘法次數(shù)的最小值，對于i=j時,矩陣鏈乘只包含唯一的矩陣因此不需要做任何標量乘法運算，所以m[i,i]=0;當i<j時利用最優(yōu)子構(gòu)造來計算m[i,j]。〔3〕矩陣鏈乘的遞歸式：〔4需要m數(shù)組記錄Ai..j最小相乘次數(shù)，18word文檔精品文檔分享s數(shù)組記錄構(gòu)造最優(yōu)解所需要的信息，其記錄的k值指出了AiAi+1Aj的最優(yōu)括號化方案的分割點應在AkAk+1之間。3)〔5〕矩陣鏈乘的時間復雜度為θ(n4、結(jié)果截圖：5、總結(jié)：m數(shù)組和s數(shù)組的時候需要構(gòu)建二維數(shù)組，而c語言中函數(shù)的參數(shù)列表中二維數(shù)組要指明數(shù)組大小，但是還沒有輸入信息的時候并沒有方法確定數(shù)組大小。采取的方案：由于此次的例子只有兩種情況，因此對于MATRIX_CHAIN_ORDE數(shù)和PRINT_OPTIMAL_PAREN數(shù)寫兩遍，大體的實現(xiàn)過程一樣，只是數(shù)組的大小有所改變。并沒有解決這個情況，造成代碼的冗余。19word文檔精品文檔分享題目二：1、題目描述：用動態(tài)規(guī)劃求以下字符串的最長公共子序列〔LCS〕2、所用策略：動態(tài)規(guī)劃3、算法分析：〔1〕最優(yōu)子構(gòu)造：令X=<x1,x2,..xm>和Y=<y1,y2,...,yn>為兩個序列，Z=<z1,z2,...,zk>為X和Y的任意LCS。1、如果那么zk=xm=yn且Zk-1是Xm-1和Yn-1的一個LCS.2xm≠yn,zk≠意味著Z是Xm-1和Y的一個LCS；3、如果xm≠yn,zk≠yn意味著Z是X和Yn-1的一個LCS。〔2〕定義一個b[i,j]指向表項對應計算c[i,j]時所選擇的子問題最優(yōu)解，過程返回表b和表c，c[m,n]保持X和Y的LCS長度?！?〕LCS的遞歸式為：〔4〕LCS的時間復雜度為θ(m+n),b表的空間復雜度為θ(mn)。4、結(jié)果截圖：20word文檔精品文檔分享5、總結(jié)：用動態(tài)規(guī)劃求取最長公共子序列的時候，要理解b數(shù)組的用途和使用。遇到的困難：編寫的代碼無法針對字符串大小未定情況下，進展求解LCS這導致了代碼的冗余。題目三：1、題目描述：用動態(tài)規(guī)劃求取以下字符串的最長公共子串。2、所用策略：動態(tài)規(guī)劃3、算法分析：〔1〕最優(yōu)子構(gòu)造：令X=<x1,x2,..xm>和Y=<y1,y2,...,yn>為兩個序列，Z=<z1,z2,...,zk>為X和Y的任意最長公共子串。1xm=yn,那么zk=xm=yn且Zk-1是Xm-1和Yn-1的一個最長公共子串、如果21word文檔精品文檔分享≠yn,zk≠xm意味著Z是Xm-1和Y的一個最長公共子串；3、如果xm≠yn,zk≠yn意味著Z是X和Yn-1的一個最長公共子串?！?〕定義L[i,j]為以x[i]和y[j]為結(jié)尾的一樣子串的最大長度。記錄著X和Y的最長公共子串的最大長度?！?〕最長公共子串的遞歸式：〔4〕最長公共子串的時間復雜度為θ)空間復雜度為θ(mn)4、結(jié)果截圖：5、總結(jié)：要同上述的最長公共子序列進展比照，區(qū)分他們的不同之處。也要理解用動態(tài)規(guī)劃求解時的一樣之處和不同之處。22word文檔精品文檔分享題目四：、題目描述：給定n個整數(shù)〔可能為負數(shù)〕組成的序，a[1],a[2]...a[n],求該序a[i]+a[i+1]...a[j]的子段和的最大值。、所用策略：動態(tài)規(guī)劃3、算法分析:(1)最優(yōu)子構(gòu)造：定義當所給整數(shù)全為負數(shù)的候最大子段和為那么最大子段和為≤i≤j≤n引入一個輔助數(shù)組動態(tài)規(guī)劃的分解分為(1)計算輔助數(shù)組的值計算輔助數(shù)組的最大值。輔助數(shù)組b[j]用來錄以j為尾的子段以及集合中的最大子段和。(3)最大子段和的遞歸：(4)最大子段和使用動態(tài)規(guī)劃進展計算的間雜為θ)4、結(jié)果截：23word文檔精品文檔分享5、總結(jié)：在求解集合的最大子段和的時候，要比照不同解決方法的不同之處，感受用動態(tài)規(guī)劃解決的便捷。題目五：1、題目描述：利用動態(tài)規(guī)劃求出多段圖中的最短路徑、所用策略：動態(tài)規(guī)劃、算法分析：〔〕可以由圖可知，圖中的頂點講圖劃分7個階段，分別了解每個階段可以有幾種可供選擇的店，引入f[k]表示狀態(tài)k到終點狀態(tài)的最短距離。最優(yōu)子構(gòu)造為：當前狀態(tài)的f[k]由上個狀態(tài)的f[k-1]和狀態(tài)k-1到狀態(tài)k的距離決定決策：當前狀態(tài)應在前一個狀24word文檔精品文檔分享態(tài)的根底上獲得。決策需要滿足規(guī)劃方程,規(guī)劃方程：f(k)表示狀態(tài)k到終點狀態(tài)的最短距離。〔〕多段圖最短路徑的遞歸式：4、結(jié)果截圖：無。5、總結(jié)：〔〕遇到的問題：無法將多段圖的每個階段點的狀態(tài)表示并記錄下來。并不了解如何將動態(tài)規(guī)劃與貪心算法的如迪杰斯特拉算法進展比照，真正從最優(yōu)子構(gòu)造將最短路徑表示出來。實驗三貪心算法題目一：1、題目描述：背包問題，即分別計算出在0-1背包和分數(shù)背包情況下的計算結(jié)果。2、所用策略：動態(tài)規(guī)劃和貪心策略3、算法分析：〔〕0-1背包問題：所選擇的的貪心策略為按照選擇單位重25word文檔精品文檔分享量價值最大的物品順序進展摘要。算法的步驟：設背包容量為，共有n個物品，物品重量存放在數(shù)組W[n]V[n]中，問題的解存放在數(shù)組X[n]中。第一步：改變數(shù)組和V的排列順序，使其按單位重量價值V[i]/W[i]X[n]初始化為；第二步初始化i=0，設計一個循環(huán)，循環(huán)終止條件為〔W[i]>C環(huán)體為將第i個物品放入背包：X[i]=1;C=C-W[i];i++；最后一步：將結(jié)果存入到X數(shù)組中?！?所選擇的的貪心策略為按照選擇單位重量價值最大的物品順序進展摘要。算法的步驟：設背包容量為，共有n個物品，物品重量存放在數(shù)組W[n]V[n]中，問題的解存放在數(shù)組X[n]中。第一步：改變數(shù)組和V的排列順序，使其按單位重量價值V[i]/W[i]X[n]初始化為；第二步初始化i=0，設計一個循環(huán)，循環(huán)終止條件為〔W[i]>C環(huán)體為將第i個物品放入背包：X[i]=1;C=C-W[i];i++；最后一步：將結(jié)果存入到X數(shù)組中X[i]=C/W[i]?！?是由于物品不允許分割，因此，無法保證最終能將背包裝滿，局部閑置的背包容量使背包的單位重量價值降低了?！?行摘要，其算法的時間復雜度為θ(nlgn)。4、結(jié)果截圖：26word文檔精品文檔分享5、總結(jié)：使用貪心策略解決0-1背包問題得出的結(jié)果并不是最優(yōu)解，這是由于所用的選擇策略不同。題目二：1給予工作編號為J1J2...Jn，所以工作的運行時間分別為T1，T2...TN。有一個單獨的處理假定它是一個非搶占式調(diào)度：一旦工作開場，它必須運行完成。2、所用策略：貪心策略3、算法分析：〔〕由于是非搶占式調(diào)度，所以應該盡量讓時間短的工作先做，然后再讓時間長的工作做。這里我們使用堆進展排序，建立一個小頂堆，然后每次拿出小頂堆上的最小元素，并使用sum中的公式就可以算出平均完成時間。堆排序的時間復雜度是O(nlgn)，其27word文檔精品文檔分享中BuildMinHeap的時間復雜度是O(n)，而BuildMinHeap()的時間復雜度是O(lgn)HeapExtractMin(N)的時間復雜度是O(lgn)。4、結(jié)果截圖：5、總結(jié)：由于前面對于堆排序和優(yōu)先隊列的T數(shù)的錯誤沒有解決，導致在調(diào)度中，需要每次去運行時間最短的工作時發(fā)生了錯誤。題目三：1、題目描述:以A為源點，求出以下圖的單源點最短路徑。2、所用算法：由于圖中存在負權(quán)值，所以Dijkstra算法無法使用，因此采用Bellman-Ford算法求取圖的單源點最短路徑。3、算法分析：28word文檔精品文檔分享〔〕Bellman-Ford算法通過對邊進展松弛操作來漸近地降低從源點A到每個結(jié)點的最短路徑的估計值，直到該估計值與實際的最短路徑權(quán)重?(A,v)一樣為止。該算法返回TRUE值當且僅當輸入圖中不包含可以從源結(jié)點到達的權(quán)重為負值的環(huán)路?！?〕Bellman-Ford算法的執(zhí)行步驟：1、初始化：將除源點外的所有頂點的最短距離估計值d[v]←∞,d[s]←2反復對邊集E中的每條邊進展松弛操作，使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離；〔運行|v|-1次〕3、檢驗負權(quán)回路：判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在false說明問題無解；否那么算法返回true，并且從源點可達的頂點v的最短距離保存在d[v]中?！病乘惴ㄟm用X圍和條件：1.單源最短路徑(從源點A到其它所有頂點v)；2.有向圖無向圖(無向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖)；3.邊權(quán)可正可負(如有負權(quán)回路輸出錯誤提示)?！病矪ell