計算機算法分析與設計論文 背包問題的算法設計策略對比與分析

1、算法設計與分析課程考查論文背包問題的算法設計策略對比與分析0-1背包問題的算法設計策略對比與分析0 引言對于計算機科學來說，算法（Algorithm）的概念是至關重要的。算法是一系列解決問題的清晰指令，也就是說，能夠對一定規(guī)范的輸入，在有限時間內獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優(yōu)劣可以用空間復雜度與時間復雜度來衡量。算法可以理解為有基本運算及規(guī)定的運算順序所構成的完整的解題步驟?；蛘呖闯砂凑找笤O計好的有限的確切的計算序列，并且這樣的步驟和序列可以解決一類問題。算法可以使

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

3、的度量，是評價算法優(yōu)劣的重要依據。一個算法的復雜性的高低體現(xiàn)在運行該算法所需要的計算機資源的多少上面，所需的資源越多，我們就說該算法的復雜性越高；反之，所需的資源越低，則該算法的復雜性越低。 計算機的資源，最重要的是時間和空間（即存儲器）資源。因而，算法的復雜性有時間復雜性和空間復雜性之分。 不言而喻，對于任意給定的問題，設計出復雜性盡可能地的算法是我們在設計算法是追求的一個重要目標；另一方面，當給定的問題已有多種算法時，選擇其中復雜性最低者，是我們在選用算法適應遵循的一個重要準則。因此，算法的復雜性分析對算法的設計或選用有著重要的指導意義和實用價值。 關于算法的復雜性，有兩個問題要弄清楚：用

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

5、ar J:integer; BeginJ:=1; 初始化在還沒有到達A的最后一個分量且等于c的分量還沒有找到時，查找下一個分量并且進行檢測 While (Ai<c)and(j<m) do          j:=j+1; If Aj=c then search:=j 在數組A中找到等于c的分量，且此分量的下標為j else Search:=0; 在數組中找不到等于c的分量End;容易看出，在最壞的情況下，這個算法要檢測A的所有m個分量才能判斷在A中找不到等于c的分量。解決問題1的另一個算法利用到已知條件

6、中A已排好序的性質。它首先拿A的中間分量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ù)查找的范圍縮小了一半。再拿這一半的子數組的中間分量與c比較，重復上述步驟。照此重復下去，總有一個時候，或者找到一個i使得Ai=c，或者子數組為空（即子數組下界大于上界）。前一種情況找到了等于c的分量，后一種

7、情況則找不到。這個新算法因為有反復把供查找的數組分成兩半，然后在其中一半繼續(xù)查找的特征，我們稱為二分查找算法。它可以用函數B_Search來表達：Function B_Search ( c: integer):integer;VarL,U,I：integer;U和L分別是要查找的數組的下標的上界和下界Found：boolean;BeginL:=1; U:=m; 初始化數組下標的上下界Found:=false; 當前要查找的范圍是AL.AU。當等于c的分量還沒有找到且U>=L時，繼續(xù)查找While (not Found) and (U>=L) doBeginI:=(U+L) div

8、2;找數組的中間分量If c=AI 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中），兩個算法所需要檢測的分量個數卻大不相同，前者要m=2 k個，后者只要k+1個?？梢娝惴˙_Search比算法Search高效得多。以上例子說

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

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

11、函數。如果把時間復雜性和空間復雜性分開，并分別用T和S來表示，那么應該有：T =T(N,I,A) (2.1)和 S =S(N,I,A) (2.2)通常，我們讓A隱含在復雜性函數名當中，因而將（2.1）和（2.2）分別簡寫為T =T(N,I)和 S =S(N,I)由于時間復雜性和空間復雜性概念類同，計算方法相似，且空間復雜性分析相對地簡單些，所以下文將主要地討論時間復雜性。下面以T(N,I)為例，將復雜性函數具體化。根據T(N,I)的概念，它應該是算法在一臺抽象的計算機上運行所需的時間。設此抽象的計算機所提供的元運算有k種，他們分別記為O1,O2 ,.,Ok；再設這些元運算每執(zhí)行一次所需要的時間

12、分別為t1,t2,.,tk 。對于給定的算法A，設經過統(tǒng)計，用到元運算Oi的次數為ei，i=1,2,.,k ，很明顯，對于每一個i，1<=i<=k，ei是N和I的函數，即ei=ei(N,I)。那么有：(2.3)其中ti，i=1,2,.,k,是與N,I無關的常數。顯然，我們不可能對規(guī)模N的每一種合法的輸入I都去統(tǒng)計ei(N,I),i=1,2,k。因此T(N,I)的表達式還得進一步簡化，或者說，我們只能在規(guī)模為N的某些或某類有代表性的合法輸入中統(tǒng)計相應的ei , i=1,2,k，評價時間復雜性。下面只考慮三種情況的復雜性，即最壞情況、最好情況和平均情況下的時間復雜性，并分別記為Tmax

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

14、N)的合法輸入難以確定，而規(guī)模N的每一個輸入的概率也難以預測或確定。我們有時也按平均情況計量時間復雜性，但那時在對P(I)做了一些人為的假設（比如等概率）之后才進行的。所做的假設是否符合實際總是缺乏根據。因此，在最好情況和平均情況下的時間復雜性分析還僅僅是停留在理論上。1.3復雜性的漸近性態(tài)及其階隨著經濟的發(fā)展、社會的進步、科學研究的深入，要求用計算機解決的問題越來越復雜，規(guī)模越來越大。但是，如果對這類問題的算法進行分析用的是第二段所提供的方法，把所有的元運算都考慮進去，精打細算，那么，由于問題的規(guī)模很大且結構復雜，算法分析的工作量之大、步驟之繁將令人難以承受。因此，人們提出了對于規(guī)模充分大、

15、結構又十分復雜的問題的求解算法，其復雜性分析應如何簡化的問題。我們先要引入復雜性漸近性態(tài)的概念。設T(N)是在第二段中所定義的關于算法A的復雜性函數。一般說來，當N單調增加且趨于時,T(N)也將單調增加趨于。對于T(N)，如果存在T(N)，使得當N時有：(T(N )-T(N )/T(N ) 0那么，我們就說T(N)是T(N)當N時的漸近性態(tài)，或叫T(N)為算法A當N的漸近復雜性而與T(N)相區(qū)別，因為在數學上，T(N)是T(N)當N時的漸近表達式。直觀上，T(N)是T(N)中略去低階項所留下的主項。所以它無疑比T(N)來得簡單。比如當T(N)=3N 2+4Nlog2N +7時，T(N)的一個答

16、案是3N 2，因為這時有：顯然3N 2比3N 2 +4Nlog2N +7簡單得多。由于當N時T(N)漸近于T(N)，我們有理由用T(N)來替代T(N)作為算法A在N時的復雜性的度量。而且由于于T(N)明顯地比T(N)簡單，這種替代明顯地是對復雜性分析的一種簡化。進一步，考慮到分析算法的復雜性的目的在于比較求解同一間題的兩個不同算法的效率，而當要比較的兩個算法的漸近復雜性的階不相同時，只要能確定出各自的階，就可以判定哪一個算法的效率高。換句話說，這時的漸近復雜性分析只要關心T(N)的階就夠了，不必關心包含在T(N)中的常數因子。所以，我們常常又對T(N)的分析進-步簡化，即假設算法中用到的所有不

17、同的元運算各執(zhí)行一次，所需要的時間都是一個單位時間。綜上所述，我們已經給出了簡化算法復雜性分析的方法和步驟，即只要考察當問題的規(guī)模充分大時，算法復雜性在漸近意義下的階。與此簡化的復雜性分析方法相配套，需要引入五個漸近意義下的記號：、和。以下設f(N)和g(N)是定義在正數集上的正函數。如果存在正的常數C和自然數N0，使得當NN0時有f(N)Cg(N)。則稱函數f(N)當N充分大時上有界，且g(N)是它的一個上界，記為f(N)=(g(N)。這時我們還說f(N)的階不高于g(N)的階。舉幾個例子：(1)因為對所有的N1有3N4N，我們有3N =(N)；(2)因為當N1時有N+10241025N，我

18、們有N +1024=(N)；(3)因為當N10時有2N 2+11N -103N 2，我們有2N 2+11N -10=(N 2)；(4)因為對所有N1有N 2N 3，我們有N2=(N 3)；(5)作為一個反例N 3(N 2)。因為若不然，則存在正的常數C和自然數N0，使得當NN0時有N3C N 2，即NC 。顯然當取N =max(N0,C+l)時這個不等式不成立，所以N3(N 2)。按照大的定義，容易證明它有如下運算規(guī)則：(f)+(g)=(max(f,g)； (f)+ (g)=(f +g)； (f)·(g)= (f·g)； 如果g(N)= (f(N)，則(f)+ (g)= (

19、f)； (Cf(N)= (f(N)，其中C是一個正的常數； f =(f)； 1.4復雜性漸近階的重要性計算機的設計和制造技術在突飛猛進，一代又一代的計算機的計算速度和存儲容量在直線增長。有的人因此認為不必要再去苦苦地追求高效率的算法，從而不必要再去無謂地進行復雜性的分析。他們以為低效的算法可以由高速的計算機來彌補，以為在可接受的一定時間內用低效的算法完不成的任務，只要移植到高速的計算機上就能完成。這是一種錯覺。造成這種錯覺的原因是他們沒看到：隨著經濟的發(fā)展、社會的進步、科學研究的深入，要求計算機解決的問題越來越復雜、規(guī)模越來越大，也呈線性增長之勢；而問題復雜程度和規(guī)模的線性增長導致的時耗的增長

20、和空間需求的增長，對低效算法來說，都是超線性的，決非計算機速度和容量的線性增長帶來的時耗減少和存儲空間的擴大所能抵銷。事實上，我們只要對效率上有代表性的幾個檔次的算法作些簡單的分析對比就能明白這一點。我們還是以時間效率為例。設A1,A2,和A6。是求解同一間題的6個不同的算法，它們的漸近時間復雜性分別為N，NlogN，N 2，N 3，2N，N!。讓這六種算法各在C1和C2兩臺計算機上運行，并設計算機C2的計算速度是計算機C1的10倍。在可接受的一段時間內，設在C1上算法Ai可能求解的問題的規(guī)模為N1i，而在C2上可能求解的問題的規(guī)模為N2i，那么，我們就應該有Ti(N2i)=10Ti(N1i)

21、，其中Ti(N)是算法Ai漸近的時間復雜性，i=1,2,6。分別解出N2i和N1i的關系，可列成下表：表1-1算法與漸近時間復雜性的關系算法漸進時間復雜性T(N)在C1上可解的規(guī)模N1在C2上可解的規(guī)模N2N1和N2的關系A1NN11N21N21=10N11A2NlogNN12N22N2210N12A3N2N13N23A4N3N14N24A52NN15N25N25 =N15+log10A6N!N16N26N26 =N16+小的常數從表1-1的最后一列可以清楚地看到，對于高效的算法A1，計算機的計算速度增長10倍，可求解的規(guī)模同步增長10倍；對于A2，可求解的問題的規(guī)模的增長與計算機的計算速度的

22、增長接近同步；但對于低效的算法A3，情況就大不相同，計算機的計算速度增長10倍只換取可求解的問題的規(guī)模增加log10。當問題的規(guī)模充分大時，這個增加的數字是微不足道的。換句話說，對于低效的算法，計算機的計算速度成倍乃至數10倍地增長基本上不帶來求解規(guī)模的增益。因此，對于低效算法要擴大解題規(guī)模，不能寄希望于移植算法到高速的計算機上，而應該把著眼點放在算法的改進上。從表1-l的最后一列我們還看到，限制求解問題規(guī)模的關鍵因素是算法漸近復雜性的階，對于表中的前四種算法，其漸近的時間復雜性與規(guī)模N的一個確定的冪同階，相應地，計算機的計算速度的乘法增長帶來的是求解問題的規(guī)模的乘法增長，只是隨著冪次的提高，

23、規(guī)模增長的倍數在降低。我們把漸近復雜性與規(guī)模N的冪同階的這類算法稱為多項式算法。對于表中的后兩種算法，其漸近的時間復雜性與規(guī)模N的一個指數函數同階，相應地計算機的計算速度的乘法增長只帶來求解問題規(guī)模的加法增長。我們把漸近復雜性與規(guī)模N的指數同階的這類算法稱為指數型算法。多項式算法和指數型算法是在效率上有質的區(qū)別的兩類算法。這兩類算法的區(qū)別的內在原因是算法漸近復雜性的階的區(qū)別?？梢?，算法的漸近復雜性的階對于算法的效率有著決定性的意義。所以在討論算法的復雜性時基本上都只關心它的漸近階。多項式算法是有效的算法。絕大多數的問題都有多項式算法。但也有一些問題還未找到多項式算法，只找到指數型算法。我們在討

24、論算法復雜性的漸近階的重要性的同時，有兩條要記住：“復雜性的漸近階比較低的算法比復雜性的漸近階比較高的算法有效”這個結論，只是在問題的求解規(guī)模充分大時才成立。比如算法A4比A5有效只是在N 3<2N，即Nc 時才成立。其中c是方程N 3=2N的解。當N <c時，A5反而比A4有效。所以對于規(guī)模小的問題，不要盲目地選用復雜性階比較低的算法。其原因一方面是如上所說，復雜性階比較低的算法在規(guī)模小時不一定比復雜性階比較高的算法更有效；另方面，在規(guī)模小時，決定工作效率的可能不是算法的效率而是算法的簡單性，哪一種算法簡單，實現(xiàn)起來快，就選用那一種算法。 當要比較的兩個算法的漸近復雜性的階相同時

25、，必須進一步考察漸近復雜性表達式中常數因子才能判別它們誰好誰差。顯然常數因子小的優(yōu)于常數因子大的算法。比如漸近復雜性為N1ogN/l00的算法顯然比漸近復雜性為l00NlogN的算法來得有效。2 常見的算法分析設計策略介紹我們一般常見的幾種算法分析設計策略主要有：動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法。接下來我主要介紹一下這幾種算法。1.1動態(tài)規(guī)劃動態(tài)規(guī)劃程序設計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數值計算那樣，具有一個標準的數學表達式和明確清晰的解題方法。動態(tài)規(guī)劃程序設計往往是針對一種最優(yōu)化問題，由于各種問題的性質不同，確定最優(yōu)解的條件也互不相同

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

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

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

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

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

31、問題，定義問題的解空間； （2）確定易于搜索的解空間結構； （3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。1.4 分支限界法分支定界 (branch and bound) 搜索法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同，分支定界算法采用廣度優(yōu)先或最小耗費優(yōu)先的方法搜索解空間樹，并且，在分支定界算法中，每一個活結點只有一次機會成為擴展結點。分支定界法的思想是：首先確定目標值的上下界，邊搜索邊減掉搜索樹的某些支，提高搜索效率。解題步驟：（1）在問題的邊帶權的解空間樹中進行廣度優(yōu)先搜索 （2）找一個葉結點使其對應路徑的權最小(最大)（3）當搜索到達一個擴展

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

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

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

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

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

37、如，剛開始任選N件物品中的一個，看對應的M的背包，能不能放進去，如果能放進去，并且還有多少空間，則，多出來的空間能放N-1物品中的最大價值，怎么能保證總選則是最大價值呢，看下表：測試數據：10,33,44,55,6最大容量M物品個數Nj=0-m103C0123456789物品大小W物品價值p編號00000000034i=110004444444451-n 2200045559995633000456691011cij數組保存了1,2,3號物品依次選擇后的最大價值。這個最大價值是怎么得來的呢?從背包容量為0開始,1號物品先試,0,1,2,的容量都不能放.所以置0,背包容量為3則里面放4.這樣,這

38、一排背包容量為4,5,6,.10的時候，最佳方案都是放4.假如1號物品放入背包.則再看2號物品.當背包容量為3的時候，最佳方案還是上一排的最價方案c為4.而背包容量為5的時候，則最佳方案為自己的重量5.背包容量為7的時候，很顯然是5加上一個值了。加誰?很顯然是7-4=3的時候.上一排c3的最佳方案是4.所以?？偟淖罴逊桨甘?+4為9.這樣.一排一排推下去。最右下放的數據就是最大的價值了。(注意第3排的背包容量為7的時候,最佳方案不是本身的6.而是上一排的9.說明這時候3號物品沒有被選.選的是1,2號物品.所以得9。從以上最大價值的構造過程中可以看出。f(n,m)=maxf(n-1,m), f(

39、n-1,m-wn)+P(n,m)這就是書本上寫的動態(tài)規(guī)劃方程.下面是一種實現(xiàn)過程： #include<iostream>using namespace std;int c10100;/*對應每種情況的最大價值*/int knapsack(int m,int n) int i,j,w10,p10; for(i=1;i<n+1;i+) cin>>wi>>pi; for(i=0;i<10;i+) for(j=0;j<100;j+) cij=0;/*初始化數組*/ for(i=1;i<n+1;i+) for(j=1;j<m+1;j+)

40、if(wi<=j) /*如果當前物品的容量小于背包容量*/ if(pi+ci-1j-wi>ci-1j) /*如果本物品的價值加上背包剩下的空間能放的物品的價值*/ /*大于上一次選擇的最佳方案則更新cij*/ cij=pi+ci-1j-wi; else cij=ci-1j; else cij=ci-1j; cout<<"背包中放著重量如下的物品："<<endl; /*確定選取了哪幾個物品*/ i=n;j=m; while(i>=0)&&(j>=0) if(pi+ci-1j-wi>ci-1j)&&a

41、mp;(i-1>=0)&&(j-wi>=0) cout<<wi<<" " j=j-wi; i=i-1; else i=i-1; cout<<endl; return(cnm);void main() int m,n; cout<<"輸入總背包容量：" cin>>m; cout<<endl; cout<<"輸入背包最多可放的物品個數：" cin>>n; cout<<endl; cout<<&

42、quot;輸入每一組數據:"<<endl; cout<<"背包所能容納的最大價值為："<<knapsack(m,n)<<endl;3.3回溯法用回溯法求解0-1背包問題的算法思路是按照物品的單位價值從大到小排序,計算當前節(jié)點的上界,搜索左子樹。只有當右子樹包含可行解時才搜索右子樹。剪去右子樹的條件是當前價值加上剩余物品的總價值小于當前的最優(yōu)總價值時,不需搜索右子樹,可將右子樹剪去?；厮莘ㄓ靡欢ǖ募糁M行優(yōu)化,算法的時間復雜度為O ( n3 2n ) , n為物品個數。下面是一種實現(xiàn)過程： #include<io

43、stream> using namespace std; class Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m<=n;m+) cout<<bestxm<<" " cout<<endl; ; private: int Bound(int i); void Backtrack(int i); int c;/背包容量 int n; /物品數 int *w;/物品重量數組 int *p;/物品價值數組 i

44、nt cw;/當前重量 int cp;/當前價值 int bestp;/當前最優(yōu)值 int *bestx;/當前最優(yōu)解 int *x;/當前解 ; int Knap:Bound(int i) /計算上界 int cleft=c-cw;/剩余容量 int b=cp; /以物品單位重量價值遞減序裝入物品 while(i<=n&&wi<=cleft) cleft-=wi; b+=pi; i+; /裝滿背包 if(i<=n) b+=pi/wi*cleft; return b; void Knap:Backtrack(int i) if(i>n) if(bestp

45、<cp) for(int j=1;j<=n;j+) bestxj=xj; bestp=cp; return; if(cw+wi<=c) /搜索左子樹 xi=1; cw+=wi; cp+=pi; Backtrack(i+1); cw-=wi; cp-=pi; if(Bound(i+1)>bestp)/搜索右子樹 xi=0; Backtrack(i+1); class Object friend int Knapsack(int p,int w,int c,int n); public: int operator<=(Object a)const return (d&

46、gt;=a.d); private: int ID; float d; ; int Knapsack(int p,int w,int c,int n) /為Knap:Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new Objectn; for(i=1;i<=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W<=c) return P;/裝入所有物品 /依物品單位重量排序 float f; for( i=0;i<n;i+) for(int j=i;j<n;j+)

47、 if(Qi.d<Qj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K; K.p = new intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new intn+1; K.x0=0; K.bestx0=0; for( i=1;i<=n;i+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1); K.print(); delete Q; delete K.w; dele

48、te K.p; return K.bestp; void main() int *p; int *w; int c=0; int n=0; int i=0; cout<<"請輸入背包個數："<<endl; cin>>n; p=new intn+1; w=new intn+1; p0=0; w0=0; cout<<"請輸入個背包的價值："<<endl; for(i=1;i<=n;i+) cin>>pi; cout<<"請輸入個背包的重量："<

49、<endl; for(i=1;i<=n;i+) cin>>wi; cout<<"請輸入背包容量："<<endl; cin>>c; cout<<Knapsack(p,w,c,n)<<endl; 3.4 貪心算法在求解0-1背包問題時,對貪心算法可以使用一些策略, 使其得到的解更接近最優(yōu)解。具體方案如下:(1) 價值優(yōu)先策略:從剩余的物品中,選取價值最大的可以裝入背包的物品。此時,價值最大的優(yōu)先被裝入背包,然后裝入下一個價值最大的物品,直到不能再裝入剩下的物品為止。(2) 重量優(yōu)先策略:從剩余的

50、物品中選取重量最小的物品裝入背包中,這種策略一般不能得到最優(yōu)解。(3) 單位價值優(yōu)先策略:根據價值/重量的比值,按照每一次選取剩下的物品中比值最大的物品裝入背包,直到不能再裝入為止。以上三種策略都不能保證得到最優(yōu)解,但三種策略相比較而言,第三種策略與最優(yōu)解相差較小。如果可以選擇物品的一部分,用單位價值策略可以保證得到最優(yōu)解。在貪心算法時間復雜度的估算中,由于需要對重量或價值或兩者的比值進行排序，所以貪心算法的時間復雜度為O(n*logn)。下面是一種實現(xiàn)過程： #include <iostream.h>#include <math.h>#include <stri

51、ng.h>#include "time.h"#include "windows.h"#include <stdlib.h>#include <stdio.h>#define num 100void bagloading(int x,float p,float w,float c,int n) /x取值為0或1，xi=1當且僅當背包i背裝載； /p是物品價值； /w是物品重量； /c表示背包的容量； /n表示物品的件數； float t,k,pwnum; int i,j,m,kk; for(i=0;i<n;i+) pwi=pi/wi; /對各個點的坐標按由大到小進行排序(使用改進的冒泡排序) m=n-1; while (m>0) kk=0; for(j=0;j<m;j+) if (pwj<pwj+1) t=pj; pj=pj+1; pj+1=t; k=wj; wj=wj+1; wj+1=k; kk=j; m=kk; /按p/w次序從大到小選擇物品 i=0; while(i<n