背包問題的算法設(shè)計與分析研究

摘要：背包問題是算法設(shè)計分析中的經(jīng)典問題，本文采用貪婪法、動態(tài)規(guī)劃法及遞歸法三種方法分別對背包問題、0-1背包問題及簡單0-1背包問題進行算法設(shè)計和時間復(fù)雜度分析，給出具體算法設(shè)計和實現(xiàn)過程，并以具體實例詳細(xì)描述不同方法求解問題解時算法基本思想，總結(jié)三種方法實現(xiàn)的優(yōu)缺點并得出結(jié)論。

關(guān)鍵詞：背包問題；貪婪法；動態(tài)規(guī)劃法；時間復(fù)雜度

中圖分類號：TP311文獻標(biāo)識碼：A 文章編號：1009-3044(2008)25-1534-02

Study on Algorithm Design and Analysis of Knapsack Problem

SUN Hong-li

(Computer Science Department， Shangqiu Normal University， Shangqiu 476000， China)

Abstract: The knapsack problem is a classical question in the area of algorithm design and analysis， in this paper greedy method， the dynamic programming method and the recursion method are used separately to solve the knapsack problem， 0-1 knapsack problem and the simple 0-1 knapsack problem， and to design the algorithm， to discuss the time complexity. Algorithm design and realization process is given， and with example algorithm basic thought to describe different solution is introduced， and the conclusion is gotten by summarizing the goods and shortcoming of three methods.

Key words: knapsack problem; greedy method; dynamic programming method; time complexity

1 引言

算法是計算機科學(xué)的核心，也是程序設(shè)計的關(guān)鍵，對算法的研究是通過程序來實踐的，算法+數(shù)據(jù)結(jié)構(gòu)=程序，此經(jīng)典公式表明有了算法，加上合適的數(shù)據(jù)結(jié)構(gòu)，用高級語言進行實現(xiàn)就可以得到程序。那么要解決背包問題，首要的前提就是設(shè)計出好的算法，想求得背包問題的解，就要先設(shè)計出算法。本文采用三種方法來對背包問題進行算法設(shè)計，并分析其時間復(fù)雜度，進而得出結(jié)論。

2 背包問題描述

背包問題是整數(shù)規(guī)劃中的一類特殊問題，在現(xiàn)實生活中具有廣泛應(yīng)用，如能提出求解此問題的有效算法，則具有很好的經(jīng)濟價值和決策價值，如物流公司的貨物發(fā)配問題，集裝箱的運載問題，如何才能獲得最大利潤。

問題的一般描述是：旅行者背包登山，背包的最大承重為M，現(xiàn)有n個物品可供選擇裝入背包，第i個物品重量為wi，價值為pi，假定物品i的一部分xi（0≤xi≤1）放入背包，獲得價值為xipi，由于背包最大承重為M，要求裝入物品總質(zhì)量不過超過M，問旅行者應(yīng)該如何選擇物品裝入背包，使得裝入物品的價值總和達到最大值。

背包問題的數(shù)學(xué)描述如下：要求找到一個n元向量(x1，x2，…xn)，在滿足約束條件：■情況下，使得目標(biāo)函數(shù)max∑xipi，其中，1≤i≤n;M>0;wi>0;pi>0。滿足約束條件的任何向量都是一個可行解，而使得目標(biāo)函數(shù)達到最大的那個可行解則為最優(yōu)解。

3 局部優(yōu)先策略的貪婪法求解背包問題

采用貪婪法求解問題的最優(yōu)解核心是選擇合適的優(yōu)化測度，下面以一個背包問題的具體實例來說明求解思想。已知：n=3，w=(10，25，30)，p=(60，50，90)，M=30，求如何裝包可得到最大價值。

分析：如果從剩余的物品中每次都選取當(dāng)前價值最大的來裝入的話，利用價值優(yōu)先測度，不能保證獲得最優(yōu)解，也就是說如果優(yōu)化側(cè)度的選取只考慮價值是不行的；如果每次都選擇背包耗費最小的物品裝入的話，利用質(zhì)量最小作為優(yōu)化測度，同樣也不能保證得到最優(yōu)解，只考慮質(zhì)量同樣無法得到最優(yōu)解；最后我們同時考慮價值和質(zhì)量，以單位質(zhì)量價值大的物品首先裝入，以此作為優(yōu)化測度，就可以保證背包問題獲得最優(yōu)解。上面的例子求解結(jié)果如下：最大價值為120，解向量為（1，0，2/3）。其求解過程可以簡單概括如下，首先對所有物品的單位質(zhì)量價值按非升序排列，然后一個個考慮物品，裝入物品后要修正背包的當(dāng)前承重及已獲得價值，如果背包的當(dāng)前承重不足以裝入整個物品時，可以裝入物品的一部分保證背包裝滿而獲得最大價值。由此利用局部最優(yōu)策略求解背包問題得到的局部最優(yōu)解肯定是全局最優(yōu)解。

采用貪婪法局部優(yōu)先策略算法時間復(fù)雜度是T(n)=O(n2)。首先我們對物品單位質(zhì)量的價值非升序排列，采用冒泡法實現(xiàn)，執(zhí)行時間為T1(n)=(n-1)+(n-2)+…+1=n(n+1)/2；從排好序的物品中選取加入解向量，最大執(zhí)行n次T2(n)=O(n)，故貪婪法總的時間耗費為：T(n)=T1(n)+T2(n)=O(n2)。

如果對背包問題進行擴展，再裝入物品時只允許全裝或者不裝，不允許裝入物品的部分，也就是xi=1或者xi=0。此時成為0-1背包問題。那么對0-1背包問題，貪婪法可以求得最優(yōu)解嗎？

答案是否定的，還以上面的實例說明，采用貪婪法求的解向量為（1，0，0），最大價值為60，很明顯，（0，0，1）優(yōu)于前者，最大價值為90。要求0-1背包問題的最優(yōu)解就需要采用全新的算法思想，下面具體說明。

4 最優(yōu)化原理的動態(tài)規(guī)劃法求解0-1背包問題

動態(tài)規(guī)劃法的核心基礎(chǔ)是最優(yōu)化原理，它把已知問題分為很多子問題，按順序求解子問題，在每一種情況下，列出各種情況的局部解，按條件從中選取那些最有可能產(chǎn)生最佳的結(jié)果舍棄其余。前一子問題為后面子問題提供信息，而減少計算量，最后一個子問題的解即為問題解。采用此方法求解0-1背包問題的主要步驟如下：

①分析最優(yōu)解的結(jié)構(gòu)：最有子結(jié)構(gòu)性質(zhì)；

②建立遞歸方程；

③計算最優(yōu)值；

④構(gòu)造最優(yōu)解。

下面用動態(tài)規(guī)劃法求解0-1背包問題。首先此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。簡單說明如下：設(shè)(y1，y2，…，yn)是最優(yōu)解，則(y2， …，yn)是對應(yīng)子問題的一個最優(yōu)解：max■ pixi，■

采用反證法說明：假設(shè)(y2， …，yn)不是對應(yīng)子問題的最優(yōu)解，那么必定存在最優(yōu)解，令 (z2，…，zn)是對應(yīng)子問題的一個最優(yōu)解。由上述假設(shè)得到， ■zipi> ■yipi，并且w1y1+ ■ziwi≤M在■zipi> ■yipi兩邊同時加上p1y1，得到 ■zipi+p1y1> ■yipi+p1y1，合并w1y1+ ■ziwi≤M，可得出(y1，z2，…，zn)優(yōu)于(y1，y2，…，yn)，推出矛盾，也即假設(shè)不成立。符合最優(yōu)子結(jié)構(gòu)性質(zhì)。

根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)可以推出遞歸方程。引入符號v(i，j)表示i個物品當(dāng)前背包承重為j時可以獲得的最大價值，要求得i個物品可以獲得最大價值要考慮第i個物品質(zhì)量和當(dāng)前背包承重大小關(guān)系，背包可以容納第i個物品的話，有裝入和不裝兩種情況，表示為v(i-1，j-wi)和v(i-1，j)，如果第i個物品質(zhì)量大于背包當(dāng)前承重，則只有不裝，即v(i-1，j)。由此可以得出關(guān)于解的遞歸方程如下：

■

根據(jù)遞歸方程，可以求得0-1背包問題的最大價值和解向量，還以上面的實例說明求解過程。

■

故得到：v(1，30)=60;v(2，30)=60;v(3，30)=90；X=（0，0，1），從這個求解過程可得動態(tài)規(guī)劃法肯定可以得到0-1背包問題的最優(yōu)解。

動態(tài)規(guī)劃法算法執(zhí)行時間為n*a*b次循環(huán)，每次循環(huán)都要執(zhí)行比較運算，算法完成所需總是件為cn2，故時間復(fù)雜度為

T(n)=O(n3)。

如果對0-1背包問題的求解目標(biāo)進行限制，求如何裝包可以使得裝入物品的重量總和恰好是M。那么問題就不再是最優(yōu)化問題，稱為簡單的0-1背包問題。顯然，用貪婪法或動態(tài)規(guī)劃法都無法求得此問題的解向量，這時需要用到遞歸法來求解。

5 遞歸法求解簡單0-1背包問題

簡單0-1背包問題可以描述為：現(xiàn)有n個物品，第i個物品質(zhì)量為wi，有一個可容物品最大質(zhì)量為M的背包，如何從n件物品中選取出若干件裝入使得放入背包的質(zhì)量之和正好為M。

由于0-1背包問題對第i件物品要么裝入，要么不裝，故問題可能有解，也可能無解。采用布爾函數(shù)表示問題。Knap(i，j)其中i表示物品個數(shù)，j表示背包當(dāng)前容量。如果問題有解函數(shù)值為true，否則為1。

先取第n個物品裝入，如果wn=M，knap(n，M)=true；

如果wn1，knap(n，M)= knap(n-1，M-wn)有解可行，否則轉(zhuǎn)化為knap(n，M)= knap(n-1，M)；

如果wn1，knap(n，M)= knap(n-1，M)。

遞歸算法的執(zhí)行時間是那n2次調(diào)用，每次調(diào)用完成一次比較和一次棧運算，算法完成總時間是2n2，時間復(fù)雜度為T(n)O(n2)。

6 結(jié)論

這三種算法都在c語言環(huán)境下得到驗證，運行結(jié)果證明了算法設(shè)計是可行的，正確的。通過對背包問題、0-1背包問題與簡單0-1背包問題的算法設(shè)計及時間復(fù)雜度分析可以看出，無論采用貪婪法還是動態(tài)規(guī)劃法，都是在已知約束條件下求解最大值建立數(shù)學(xué)模型算法實現(xiàn)的過程；但算法具體實現(xiàn)和數(shù)據(jù)結(jié)構(gòu)的建立要用到遞歸和棧操作。比較貪婪法和動態(tài)規(guī)劃法，前者的時間復(fù)雜度低于后者，從耗費上而言優(yōu)于后者，但后者的實現(xiàn)算法可讀性要優(yōu)于前者。

參考文獻：

[1] M.H.Alsuwaiyel.算法設(shè)計技巧與分析[M].北京:電子工業(yè)出版社，2004.

[2] 任瑞證，嚴(yán)蔚敏.整數(shù)背包問題的應(yīng)用及其算法研究[J].小型微型計算機系統(tǒng)，2001，22(2):204-206.

[3] 劉西奎，李艷，許進.背包問題的遺傳算法求解研究[J].華中科技大學(xué)學(xué)報（自然科學(xué)版），2002，30(6):89-90.