算法分析與設(shè)計論文-背包問題的算法設(shè)計策略對比與分析

1、算法設(shè)計與分析論文題 目0-1背包問題的算法設(shè)計謀略比照與分析專 業(yè) 班 級 學(xué) 號 姓 名 引言對于計算機科學(xué)來說，算法Algorithm的概念是至關(guān)重要的。算法是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢?biāo)準(zhǔn)的輸入，在有限時間內(nèi)獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度來衡量。算法可以理解為有根本運算及規(guī)定的運算順序所構(gòu)成的完整的解題步驟?；蛘呖闯砂凑找笤O(shè)計好的有限確實切的計算序列，并且這樣的步驟和序列可以解決一類問題。算法可以使用自然語言

2、、偽代碼、流程圖等多種不同的方法來描述。一個算法應(yīng)該具有以下五個重要的特征：有窮性：一個算法必須保證執(zhí)行有限步之后結(jié)束；確切性：算法的每一步驟必須有確切的定義； 輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定除了初始條件； 輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的； 可行性：算法原那么上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成。計算機科學(xué)家尼克勞斯-沃思曾著過一本著名的書?數(shù)據(jù)結(jié)構(gòu)十算法= 程序?，可見算法在計算機科學(xué)界與計算機應(yīng)用界的地位。1 算法復(fù)雜性分析的方法介紹算法的復(fù)雜性是算法效率的度

3、量，是評價算法優(yōu)劣的重要依據(jù)。一個算法的復(fù)雜性的上下表達(dá)在運行該算法所需要的計算機資源的多少上面，所需的資源越多，我們就說該算法的復(fù)雜性越高；反之，所需的資源越低，那么該算法的復(fù)雜性越低。 計算機的資源，最重要的是時間和空間即存儲器資源。因而，算法的復(fù)雜性有時間復(fù)雜性和空間復(fù)雜性之分。 不言而喻，對于任意給定的問題，設(shè)計出復(fù)雜性盡可能地的算法是我們在設(shè)計算法是追求的一個重要目標(biāo)；另一方面，當(dāng)給定的問題已有多種算法時，選擇其中復(fù)雜性最低者，是我們在選用算法適應(yīng)遵循的一個重要準(zhǔn)那么。因此，算法的復(fù)雜性分析對算法的設(shè)計或選用有著重要的指導(dǎo)意義和實用價值。 關(guān)于算法的復(fù)雜性，有兩個問題要弄清楚：用怎樣

4、的一個量來表達(dá)一個算法的復(fù)雜性；對于給定的一個算法，怎樣具體計算它的復(fù)雜性。讓我們從比擬兩對具體算法的效率開始。考慮問題1：不重復(fù)且已經(jīng)按從小到大排好的m個整數(shù)的數(shù)組A1.m為簡單起見。還設(shè)m=2 k，k是一個確定的非負(fù)整數(shù)。對于給定的整數(shù)c，要求尋找一個下標(biāo)i，使得Ai=c；假設(shè)找不到，那么返回一個0。問題1的一個簡單的算法是：從頭到尾掃描數(shù)組A。照此，或者掃到A的第i個分量，經(jīng)檢測滿足Ai=c；或者掃到A的最后一個分量，經(jīng)檢測仍不滿足Ai=c。我們用一個函數(shù)Search來表達(dá)這個算法：Function Search (c:integer):integer;Var J:integer; Be

5、ginJ:=1; 初始化在還沒有到達(dá)A的最后一個分量且等于c的分量還沒有找到時，查找下一個分量并且進(jìn)行檢測 While (Ai<c)and(j<m) do          j:=j+1; If Aj=c then search:=j 在數(shù)組A中找到等于c的分量，且此分量的下標(biāo)為j else Search:=0; 在數(shù)組中找不到等于c的分量End;容易看出，在最壞的情況下，這個算法要檢測A的所有m個分量才能判斷在A中找不到等于c的分量。解決問題1的另一個算法利用到條件中A已排好序的性質(zhì)。它首先拿A的中間

6、分量Am/2與c比擬，如果Am/2=c那么解已找到。如果Am/2>c，那么c只可能在A1,A2,.,Am/2-1之中，因而下一步只要在A1, A2, . ，Am/2-1中繼續(xù)查找；如果Am/2<c，那么c只可能在Am/2+1,Am/2+2,.,Am之中，因而下一步只要在Am/2+1,Am/2+2,.,Am中繼續(xù)查找。不管哪一種情形，都把下一步需要繼續(xù)查找的范圍縮小了一半。再拿這一半的子數(shù)組的中間分量與c比擬，重復(fù)上述步驟。照此重復(fù)下去，總有一個時候，或者找到一個i使得Ai=c，或者子數(shù)組為空即子數(shù)組下界大于上界。前一種情況找到了等于c的分量，后一種情況那么找不到。這個新算法因為有反

7、復(fù)把供查找的數(shù)組分成兩半，然后在其中一半繼續(xù)查找的特征，我們稱為二分查找算法。它可以用函數(shù)B_Search來表達(dá)：Function B_Search ( c: integer):integer;VarL,U,I：integer;U和L分別是要查找的數(shù)組的下標(biāo)的上界和下界Found：boolean;BeginL:=1; U:=m; 初始化數(shù)組下標(biāo)的上下界Found:=false; 當(dāng)前要查找的范圍是AL.AU。當(dāng)?shù)扔赾的分量還沒有找到且U>=L時，繼續(xù)查找While (not Found) and (U>=L) doBeginI:=(U+L) div 2;找數(shù)組的中間分量If c=A

8、I then Found:=Tureelse if c>AI then L:=I+1 else U:=I-1;End;If Found then B_Search:=1else B_Search:=0;End;容易理解，在最壞的情況下最多只要測A中的k+1(k=logm,這里的log以2為底，下同)個分量，就判斷c是否在A中。算法Search和B_Search解決的是同一個問題，但在最壞的情況下所給定的c不在A中，兩個算法所需要檢測的分量個數(shù)卻大不相同，前者要m=2 k個，后者只要k+1個?？梢娝惴˙_Search比算法Search高效得多。以上例子說明：解同一個問題，算法不同，那么計算

9、的工作量也不同，所需的計算時間隨之不同，即復(fù)雜性不同。上圖是運行這兩種算法的時間曲線。該圖說明，當(dāng)m適當(dāng)大m>m0時，算法B_Search比算法Search省時，而且當(dāng)m更大時，節(jié)省的時間急劇增加。不過，應(yīng)該指出：用實例的運行時間來度量算法的時間復(fù)雜性并不適宜，因為這個實例時間與運行該算法的實際計算機性能有關(guān)。換句話說，這個實例時間不單純反映算法的效率而是反映包括運行該算法的計算機在內(nèi)的綜合效率。我們引入算法復(fù)雜性的概念是為了比擬解決同一個問題的不同算法的效率，而不想去比擬運行該算法的計算機的性能。因而，不應(yīng)該取算法運行的實例時間作為算法復(fù)雜性的尺度。我們希望，盡量單純地反映作為算法精髓

10、的計算方法本身的效率，而且在不實際運行該算法的情況下就能分析出它所需要的時間和空間。算法的復(fù)雜性是算法運行所需要的計算機資源的量，需要的時間資源的量稱作時間復(fù)雜性，需要的空間即存儲器資源的量稱作空間復(fù)雜性。這個量應(yīng)該集中反映算法中所采用的方法的效率，而從運行該算法的實際計算機中抽象出來。換句話說，這個量應(yīng)該是只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A來表示算法要解問題的規(guī)模、算法的輸入和算法本身，用C表示算法的復(fù)雜性，那么應(yīng)該有：C =F(N,I,A)其中F(N,I,A)是N,I,A的一個確定的三元函數(shù)。如果把時間復(fù)雜性和空間復(fù)雜性分開，并分別用T和S來表示

11、，那么應(yīng)該有：T =T(N,I,A) (2.1)和 S =S(N,I,A) (2.2)通常，我們讓A隱含在復(fù)雜性函數(shù)名當(dāng)中，因而將2.1和2.2分別簡寫為T =T(N,I)和 S =S(N,I)由于時間復(fù)雜性和空間復(fù)雜性概念類同，計算方法相似，且空間復(fù)雜性分析相對地簡單些，所以下文將主要地討論時間復(fù)雜性。下面以T(N,I)為例，將復(fù)雜性函數(shù)具體化。根據(jù)T(N,I)的概念，它應(yīng)該是算法在一臺抽象的計算機上運行所需的時間。設(shè)此抽象的計算機所提供的元運算有k種，他們分別記為O1,O2 ,.,Ok；再設(shè)這些元運算每執(zhí)行一次所需要的時間分別為t1,t2,.,tk 。對于給定的算法A，設(shè)經(jīng)過統(tǒng)計，用到元運

12、算Oi的次數(shù)為ei，i=1,2,.,k ，很明顯，對于每一個i，1<=i<=k，ei是N和I的函數(shù)，即ei=ei(N,I)。那么有：(2.3)其中ti，i=1,2,.,k,是與N,I無關(guān)的常數(shù)。顯然，我們不可能對規(guī)模N的每一種合法的輸入I都去統(tǒng)計ei(N,I),i=1,2,k。因此T(N,I)的表達(dá)式還得進(jìn)一步簡化，或者說，我們只能在規(guī)模為N的某些或某類有代表性的合法輸入中統(tǒng)計相應(yīng)的ei , i=1,2,k，評價時間復(fù)雜性。下面只考慮三種情況的復(fù)雜性，即最壞情況、最好情況和平均情況下的時間復(fù)雜性，并分別記為Tmax(N )、Tmin(N)和Tavg(N )。在數(shù)學(xué)上有：(2.4)(

13、2.5)(2.6)其中，DN是規(guī)模為N的合法輸入的集合；I *是DN中一個使T(N,I *)到達(dá)Tmax(N)的合法輸入，是DN中一個使T(N,)到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I 的概率。以上三種情況下的時間復(fù)雜性各從某一個角度來反映算法的效率，各有各的用處，也各有各的局限性。但實踐說明可操作性最好的且最有實際價值的是最壞情況下的時間復(fù)雜性。下面我們將把對時間復(fù)雜性分析的主要興趣放在這種情形上。一般來說，最好情況和最壞情況的時間復(fù)雜性是很難計量的，原因是對于問題的任意確定的規(guī)模N到達(dá)了Tmax(N)的合法輸入難以確定，而規(guī)模N的每一個輸入的概率也難以預(yù)測或確定。

14、我們有時也按平均情況計量時間復(fù)雜性，但那時在對P(I)做了一些人為的假設(shè)比方等概率之后才進(jìn)行的。所做的假設(shè)是否符合實際總是缺乏根據(jù)。因此，在最好情況和平均情況下的時間復(fù)雜性分析還僅僅是停留在理論上。2 常見的算法分析設(shè)計謀略介紹我們一般常見的幾種算法分析設(shè)計謀略主要有：動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法。接下來我主要介紹一下這幾種算法。動態(tài)規(guī)劃程序設(shè)計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計算那樣，具有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動態(tài)規(guī)劃程序設(shè)計往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動

15、態(tài)規(guī)劃的設(shè)計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時，除了要對根本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對假設(shè)干有代表性的問題的動態(tài)規(guī)劃算法進(jìn)行分析、討論，逐漸學(xué)會并掌握這一設(shè)計方法。動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似，其根本思想也是將待求解問題分解成假設(shè)干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的

16、是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨立的。假設(shè)用分治法來解這類問題，那么分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很屢次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以防止大量的重復(fù)計算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的根本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。在編程中常用解決最長公共子序列問題、矩陣連乘問題、凸多邊形最優(yōu)三角剖分問題、電路布線等問題。1.2 貪心算法所謂貪心算法又稱貪婪算法是指，在對問題

17、求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。貪心算法的根本思路：a.建立數(shù)學(xué)模型來描述問題。b.把求解的問題分成假設(shè)干個子問題。c.對每一子問題求解，得到子問題的局部最優(yōu)解。d.把子問題的解局部最優(yōu)解合成原來解問題的一個解。實現(xiàn)該算法的過程： a.從問題的某一初始解出發(fā)；b.while 能朝給定總目標(biāo)前進(jìn)一步 doc.求出可行解的一個解元素；d.由所有解元素組合成問題的一個可行解。e.下面是一個可以試用貪心算法解的

18、題目，貪心解確實不錯，可惜不是最優(yōu)解。1.3 回溯法回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，那么跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否那么，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組

19、合數(shù)較大的問題?；厮莘ǖ母舅枷耄捍_定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點根結(jié)點出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的活結(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱深方向移動，那么當(dāng)前擴展結(jié)點就成為死結(jié)點。換句話說，這個結(jié)點不再是一個活結(jié)點。此時，應(yīng)往回移動回溯至最近的一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點時為止。用回溯法解題的一般步驟：1針對所給問題，定

20、義問題的解空間； 2確定易于搜索的解空間結(jié)構(gòu)； 3以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)防止無效搜索。1.4 分支限界法分支定界 (branch and bound) 搜索法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同，分支定界算法采用廣度優(yōu)先或最小消耗優(yōu)先的方法搜索解空間樹，并且，在分支定界算法中，每一個活結(jié)點只有一次時機成為擴展結(jié)點。分支定界法的思想是：首先確定目標(biāo)值的上下界，邊搜索邊減掉搜索樹的某些支，提高搜索效率。解題步驟：1在問題的邊帶權(quán)的解空間樹中進(jìn)行廣度優(yōu)先搜索 2找一個葉結(jié)點使其對應(yīng)路徑的權(quán)最小(最大)3當(dāng)搜索到達(dá)一個擴展結(jié)點時,一次性擴展它的所有兒

21、子4將滿足約束條件且最小消耗函數(shù)£目標(biāo)函數(shù)限界的兒子,插入活結(jié)點表中5從活結(jié)點表中取下一結(jié)點同樣擴展6直到找到所需的解或活動結(jié)點表為空為止3 0-1背包問題的幾種算法背包問題是一類具有廣泛的實際應(yīng)用背景的經(jīng)典NP-hard組合優(yōu)化問題，在解決大量的復(fù)雜組合優(yōu)化問題時，它常常作為一個子問題出現(xiàn)，從實際觀點看，許多問題可以用背包問題來描述，如裝箱問題，貨倉裝載，預(yù)算控制，存儲分配，工程選擇決策等等，都是典型的應(yīng)用例子。隨著網(wǎng)絡(luò)技術(shù)的不斷開展，背包公鑰密碼在電子商務(wù)中的公鑰設(shè)計中也起著重要的作用。然而當(dāng)問題的規(guī)模較大時，得到最優(yōu)解是極其困難的。因此，借鑒前人的研究成果，開展對解決復(fù)雜組合優(yōu)

22、化問題的算法研究或改良是一項十分優(yōu)異的工作。Dantzing 在20世紀(jì)50年代首先進(jìn)行了開創(chuàng)性的研究，利用貪心算法求得了0-1背包問題最優(yōu)解的上屆。1974年，horowitz和salmi利用分支限界法解答了背包問題，并提出了背包問題的可分性，指出了求解該問題的一條新途徑。隨后，Balas和Zemel提出了背包問題的“核思想，是背包問題的呀牛獲得了較大進(jìn)展。上世紀(jì)九十年代以后，隨著生物仿生技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速開展，各種模擬生物物理規(guī)律的并行近似算法不斷涌現(xiàn)，例如遺傳算法已經(jīng)在 0-1背包問題上得到了較好的應(yīng)用，螞蟻算法、粒子群等仿生算法也在組合優(yōu)化問題中得到了很好的應(yīng)用。綜上所述，傳統(tǒng)求解該

23、問題的方法可以概括為精確算法和近似算法，其中精確算法有動態(tài)規(guī)劃法、回溯法、分支限界法等，近似算法有遺傳算法、貪婪法、粒子群算法、蟻群算法等，由于精確算法的時間復(fù)雜性和空間復(fù)雜性等缺點，近年來利用近似算法求解背包問題成為重點。因此此處對精確算法只做簡單的描述，對幾種近似算法那么較為詳細(xì)的說明了它們的思想和在背包問題中的運用。除了以上幾種常見的算法，最近幾年又出現(xiàn)了知識進(jìn)化算法、二進(jìn)制差異演化算法等新的算法解決背包問題，本文也對它們做一個簡介。最后提出了將知識發(fā)現(xiàn)的方法引入遺傳算法中來解決背包問題，擬提高單存遺傳算法的搜索效率和解的質(zhì)量。3.1 0-1背包問題描述一個旅行者有一個最多能裝C公斤重量

24、的背包，n個重量和價值分別為ci>0和pi>0(i=1,2,，n)的物品，選擇哪些物品裝入背包，可使在背包的容量限制之內(nèi)所裝物品的價值最大，這就是背包問題。0-1背包特點是：每種物品都僅有一件，可以選擇放入或不放。0-1背包問題:給定n種物品和一個背包。物品i的重量是Wi,其價值為Vi,背包的容量為C。應(yīng)如何選擇裝入背包的物品,使得裝入背包中物品的總價值最大? 在選擇裝入背包的物品時,對每種物品i只有兩種選擇,即裝入背包為1或不裝入背包為0。不能將物品i裝入背包屢次,也不能只裝入局部的物品i。021背包問題的主要特點是在選擇物品i裝入背包時,每種物品僅有一件,可以選擇放或不放。動態(tài)

25、規(guī)劃算法的根本思想是把原問題分解成一系列子問題,然后從這些子問題中求出原問題的解。對一個負(fù)重能力為m的背包,如果選擇裝入一個第i種物品,那么原背包問題就轉(zhuǎn)化為負(fù)重能力為m2w的子背包問題。由于動態(tài)規(guī)劃算法求解過程中反復(fù)出現(xiàn)子問題,且對每次重復(fù)出現(xiàn)的子問題都要重新解一次,這需要多花費不少時間,因此動態(tài)規(guī)劃算法的時間復(fù)雜度為O ( n* m) ,其中n為物體的個數(shù),m為背包負(fù)重。動態(tài)規(guī)劃是用空間換時間的一種方法的抽象。其關(guān)鍵是發(fā)現(xiàn)子問題和記錄其結(jié)果。然后利用這些結(jié)果減輕運算量。因為背包的最終最大容量未知，所以，我們得從1到M一個一個的試，比方，剛開始任選N件物品中的一個，看對應(yīng)的M的背包，能不能放

26、進(jìn)去，如果能放進(jìn)去，并且還有多少空間，那么，多出來的空間能放N-1物品中的最大價值，怎么能保證總選那么是最大價值呢，看下表：測試數(shù)據(jù)：10,33,44,55,6最大容量M物品個數(shù)Nj=0-m103C0123456789物品大小W物品價值p編號00000000034i=110004444444451-n 2200045559995633000456691011cij數(shù)組保存了1,2,3號物品依次選擇后的最大價值。從以上最大價值的構(gòu)造過程中可以看出。f(n,m)=maxf(n-1,m), f(n-1,m-wn)+P(n,m)這就是書本上寫的動態(tài)規(guī)劃方程.用回溯法求解0-1背包問題的算法思路是按照物

27、品的單位價值從大到小排序,計算當(dāng)前節(jié)點的上界,搜索左子樹。只有當(dāng)右子樹包含可行解時才搜索右子樹。剪去右子樹的條件是當(dāng)前價值加上剩余物品的總價值小于當(dāng)前的最優(yōu)總價值時,不需搜索右子樹,可將右子樹剪去?；厮莘ㄓ靡欢ǖ募糁M(jìn)行優(yōu)化,算法的時間復(fù)雜度為O ( n3 2n ) , n為物品個數(shù)。3.4 貪心算法在求解0-1背包問題時,對貪心算法可以使用一些策略, 使其得到的解更接近最優(yōu)解。具體方案如下:(1) 價值優(yōu)先策略:從剩余的物品中,選取價值最大的可以裝入背包的物品。此時,價值最大的優(yōu)先被裝入背包,然后裝入下一個價值最大的物品,直到不能再裝入剩下的物品為止。(2) 重量優(yōu)先策略:從剩余的物品中選取重量最小的物品裝入背包中,這種策略一般不能得到最優(yōu)解。(3) 單位價值優(yōu)先策略:根據(jù)價值/重量的比值,按照每一次選取剩下的物品中比值最大的物品裝入背包,直到不能再裝入為止。以上三種策略都不能保證得到最優(yōu)解,但三種策略相比擬而言,第三種策略與最優(yōu)解相差較小。如果可以選擇物品的一局部,用單位價值策略可以保證得到最優(yōu)解。在貪心算法時間復(fù)雜度的估算中,由于需要對重量或價值或兩者的比值進(jìn)行排序，所以貪心算法的時間復(fù)雜度為O(n*logn)。在解0-1背包問題的優(yōu)先隊列式分支限