陳 艷，文曉棠，鐘廣玲

（廣州華商學(xué)院數(shù)據(jù)科學(xué)學(xué)院，廣州 510520）

0 引言

0-1 背包問題是一個(gè)經(jīng)典的組合優(yōu)化問題，它涉及到在一個(gè)給定容量的背包中選擇一些物品，使得這些物品的總價(jià)值最大。該問題常常被應(yīng)用于資源分配、物流管理等領(lǐng)域，并且在計(jì)算機(jī)科學(xué)和數(shù)學(xué)中具有重要的理論價(jià)值。本文將采用深入淺出的方式，結(jié)合實(shí)例詳細(xì)介紹如何使用動(dòng)態(tài)規(guī)劃、貪心算法以及分支限界法來解決0-1背包問題，并對(duì)各種方法的優(yōu)缺點(diǎn)進(jìn)行比較。

1 問題概述

0-1 背包問題描述為：有一個(gè)容量為C的背包，可以放入背包的物品有n種，每種物品的體積和價(jià)值分別為vi和pi。在不超過背包容量的前提下，怎樣選擇放入背包中的物品，以使得放入背包中的物品的價(jià)值和最大？需要注意的是，對(duì)于每種物品，只有兩種選擇，要么放入背包，要么不放入背包，因此稱為0-1背包問題。

問題的數(shù)學(xué)模型如下：

輸入：n個(gè)物品的集合O，每個(gè)物品有兩個(gè)屬性vi和pi，分別表示物品的體積和價(jià)值；背包容量為C。

輸出：求解一個(gè)物品的子集S?O，使得。

2 動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃法與分治法類似，其基本思想都是將待求解問題分解成若干個(gè)子問題，然后從這些子問題的解得到原問題的解。動(dòng)態(tài)規(guī)劃法通過建立狀態(tài)轉(zhuǎn)移方程，也稱遞推式，來反映大問題和子問題之間的依賴關(guān)系，通過這種依賴關(guān)系來實(shí)現(xiàn)子問題的解組合成原問題的解［1］。

用動(dòng)態(tài)規(guī)劃法求解的問題一般具有兩個(gè)特征：①最優(yōu)子結(jié)構(gòu)的性質(zhì)。原問題的解可以通過子問題的解組合而成，這樣的性質(zhì)就稱為最優(yōu)子結(jié)構(gòu)性質(zhì)［2］。比如在分治法中，歸并排序通過合并算法將兩個(gè)子問題的解合并為原問題的解，因此分治法具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。比如在動(dòng)態(tài)規(guī)劃法中，求最大子數(shù)組問題的解是通過D[i]=D[i- 1]+X[i]或者D[i]=X[i]得到，即通過狀態(tài)轉(zhuǎn)移方程得到，因此動(dòng)態(tài)規(guī)劃法也具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。動(dòng)態(tài)規(guī)劃法的最優(yōu)子結(jié)構(gòu)的性質(zhì)體現(xiàn)在狀態(tài)轉(zhuǎn)移方程上，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)的分析也是該問題是否能用動(dòng)態(tài)規(guī)劃求解的關(guān)鍵步驟。②重疊子問題的性質(zhì)。一個(gè)大問題，通過分解后得到的子問題，通常存在公共的子問題，這樣的性質(zhì)稱為重疊子問題的性質(zhì)。比如斐波那契數(shù)列，求第5項(xiàng)需要通過第4 項(xiàng)和第3 項(xiàng)來得到，求第4 項(xiàng)需要通過第3 項(xiàng)和第2 項(xiàng)來得到，則求第5 項(xiàng)和求第4項(xiàng)都包含求第3項(xiàng)這個(gè)公共的子問題，故斐波那契數(shù)列具有重疊子問題性質(zhì)。解決求解重疊子問題的效率問題，是動(dòng)態(tài)規(guī)劃算法的關(guān)鍵。

動(dòng)態(tài)規(guī)劃算法的基本思想的核心，就是解決重疊子問題重復(fù)計(jì)算的問題［3］。動(dòng)態(tài)規(guī)劃算法對(duì)分解出的每個(gè)子問題只計(jì)算一次，不管該子問題是否以后被用到，都將其結(jié)果保存到一張表中，從而避免每次遇到各個(gè)子問題時(shí)重新計(jì)算答案?；谶@樣的一種思想，相對(duì)于遞歸算法而言，動(dòng)態(tài)規(guī)劃法大大提高了問題的求解效率。應(yīng)用動(dòng)態(tài)規(guī)劃算法的求解過程，實(shí)際上就是填表的過程，把相關(guān)表填完，問題的最優(yōu)解就在表中的某個(gè)位置，可能是最后一個(gè)位置，也可能是中間的某個(gè)位置。動(dòng)態(tài)規(guī)劃算法求解問題的順序去掉了遞歸算法的自頂向下分解的過程，只保留了自底向上不斷求解子問題的過程，每個(gè)子問題的解都對(duì)應(yīng)地存儲(chǔ)在表中的某個(gè)單元格中。所以，動(dòng)態(tài)規(guī)劃法求解問題的基本步驟就是圍繞著填什么表，怎么填，填完之后怎么在表中找最優(yōu)解的過程來分析的。

動(dòng)態(tài)規(guī)劃法求解問題的基本步驟分為四步：

第一步：子問題的定義和表示。

通過分析問題的結(jié)構(gòu)特點(diǎn)來定義子問題，找到合適的狀態(tài)來描述子問題，并通過定義的狀態(tài)來表示原問題。主要任務(wù)是確定用來存放子問題解的表的樣式，如一維表還是二維表或者三維表，等等，并確定原問題的表示。

第二步：狀態(tài)轉(zhuǎn)移方程（遞推式）的建立。

分析子問題之間解的依賴關(guān)系，以此來建立狀態(tài)轉(zhuǎn)移方程。因此此步的關(guān)鍵問題是證明問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)得以證明，則問題解之間的依賴關(guān)系也就隨之得到了。動(dòng)態(tài)規(guī)劃法求解問題，最關(guān)鍵的就是建立狀態(tài)轉(zhuǎn)移方程，這一步驟解決了，后面的問題水到渠成。

第三步：填表順序的確定。

在狀態(tài)轉(zhuǎn)移方程中，根據(jù)問題和子問題之間的依賴關(guān)系來確定填表順序，即子問題的求解順序。具體的確定方法可以將相關(guān)的子問題在表中的位置標(biāo)識(shí)出來，通過待求解的子問題和求解依賴的子問題在表中的位置關(guān)系來分析填表的順序。有的問題填表的順序?yàn)閺淖蟮接遥械臑閺挠业阶?，有的從上到下，不同的問題根據(jù)其特征不同填表順序也不同。填表順序確定后，就能在此步確定原問題的解在表中的位置，可能填的最后一個(gè)元素即為原問題的解，也可能解存在于表中的某一個(gè)需要通過一定策略得到的位置，比如表中元素的最大值即為原問題的解。

第四步：最優(yōu)方案的追蹤。

在第三步進(jìn)行的填表過程中，通常是需要通過一定的決策來填表，比如選最大值或最小值等。做的決策是最優(yōu)解對(duì)應(yīng)的最優(yōu)方案獲取的直接依據(jù)，因此，在對(duì)子問題的解填表的過程中，可以順便把相應(yīng)的決策記錄下來，如也用一張表來記錄。根據(jù)決策表，采用回溯的方式來尋找最優(yōu)解對(duì)應(yīng)的最優(yōu)方案。這一步，根據(jù)問題的具體要求，如果只需要求解最優(yōu)解，不需要求出最優(yōu)方案，則可以省略。

動(dòng)態(tài)規(guī)劃是解決0-1 背包問題的經(jīng)典算法，它通過構(gòu)建問題的狀態(tài)轉(zhuǎn)移方程（遞推式），從而求解出最優(yōu)解。采用二維數(shù)組DP 來存儲(chǔ)每個(gè)子問題的最優(yōu)解，其中第i行j列DP[i，j] 表示：對(duì)前i個(gè)物品，容量為j的背包能夠裝下的最大價(jià)值。對(duì)于每個(gè)物品，考慮放或者不放兩種情況，即可推導(dǎo)出狀態(tài)轉(zhuǎn)移方程，由此推算出問題的最優(yōu)解。按照此思路，根據(jù)動(dòng)態(tài)規(guī)劃算法求解問題的基本步驟，設(shè)計(jì)如下：

（1）子問題的定義和表示。

原問題的子問題定義為：對(duì)前i個(gè)物品，當(dāng)背包容量為j時(shí)，在不超過背包容量限制的前提下，使得放入背包中的物品的價(jià)值最大。此問題和原問題是性質(zhì)相同，規(guī)模變小的相同問題，故為原問題的子問題。對(duì)子問題，表示如下：

定義DP[i，j]：在前i個(gè)商品中做出選擇，背包容量為j時(shí)放入背包中商品的最大總價(jià)值。

（2）狀態(tài)轉(zhuǎn)移方程（遞推式）的建立。

狀態(tài)轉(zhuǎn)移方程意味著，在考慮第i個(gè)物品時(shí)，我們可以選擇放或者不放，分別求兩種情況的最優(yōu)解，然后再看哪種情況求得的價(jià)值最大，則其就是問題的解。如果選擇放第i個(gè)物品，那么此時(shí)背包的容量就減少了vi，并且能夠獲得的價(jià)值增加了pi，此時(shí)只要把前i-1 個(gè)物品在背包容量為j-vi時(shí)的最優(yōu)解求出來，加上i件物品的價(jià)值貢獻(xiàn)，就可得到此情況的最優(yōu)解，即求DP[i- 1,j-vi]+pi。如果選擇不放第i個(gè)物品，那么此時(shí)背包的容量依然是j，則此問題轉(zhuǎn)換為求解前i-1 個(gè)物品，背包容量為j時(shí)的子問題的最優(yōu)解問題，即求DP[i- 1,j]。兩種情況取大值即為原問題的解。

根據(jù)遞推關(guān)系的分析，DP 實(shí)際上是一張二維表，表規(guī)模為n+ 1行、C+ 1列。第0行表示沒有物品的情況，第0 列表示沒有背包的情況，這兩類情況能放入背包中的物品的總價(jià)值和都為0，故可以都初始化為0，如圖1所示。

圖1 DP表的樣式

（3）填表順序的確定。

根據(jù)上述分析，求解0-1背包問題實(shí)際上就是要完成上述DP 的計(jì)算問題。根據(jù)狀態(tài)轉(zhuǎn)移方程，在表中分別表示出DP[i,j]和求解它依賴的兩個(gè)子問題DP[i- 1,j]和DP[i- 1,j-vi]，如圖2所示。

圖2 子問題之間的位置關(guān)系

根據(jù)圖中子問題間的位置關(guān)系可知，要求DP[i,j]，則需先求出其上一行的DP[i- 1,j]和DP[i- 1,j-vi]，由此不難看出，DP 的整個(gè)計(jì)算順序?yàn)閺淖蟮接?，從上到下，一行一行地填，且最后一個(gè)元素DP[n,C]為原問題的解，如圖3所示。

圖3 原問題的解的位置

（4）最優(yōu)方案的追蹤。

根據(jù)狀態(tài)轉(zhuǎn)移方程可知，求DP[i,j]的過程實(shí)際上就是對(duì)i號(hào)物品選還是不選進(jìn)行決策的過程，因此在填每個(gè)DP[i,j]時(shí)，把做出的決策記錄下來，可以依據(jù)此決策推出最優(yōu)解對(duì)應(yīng)的最優(yōu)方案，見下式：

在Dec 表中倒敘判斷是否選擇商品，如圖4所示。

圖4 Dec表

假設(shè)有個(gè)背包，容量C= 7，有5 件可選擇的物品，各物品的價(jià)值和體積見表1。

表1 物品清單

上述問題最優(yōu)解為22，最優(yōu)方案為S={5,4,1}，即選擇5 號(hào)、4 號(hào)和1 號(hào)物品放入背包中，此時(shí)放入背包中的物品的總體積為7。

按上述分析過程得到本例子的DP 表如圖5所示，從DP表中可知原問題的最優(yōu)解為22。

圖5 案例DP

最優(yōu)方案的追蹤過程如圖6所示，得到最優(yōu)解22對(duì)應(yīng)的最優(yōu)方案為{5,4,1}，即選擇5號(hào)、4號(hào)和1號(hào)商品放入背包中。

圖6 最優(yōu)方案的追蹤

根據(jù)上述分析，設(shè)計(jì)算法DPknapsack(n,p,v,C)的偽代碼如下：

該算法用兩層循環(huán)來實(shí)現(xiàn)，循環(huán)的規(guī)模分別為n和C，故算法的復(fù)雜度為O(n*C)。

3 回溯法

回溯法是一種基于深度優(yōu)先搜索的算法，也稱為回溯搜索法，它是一種搜索的方式，常用于解決組合問題、子集問題、棋盤問題等。其核心思想是通過試錯(cuò)的搜索方式，逐步構(gòu)造可行解，并在發(fā)現(xiàn)不符合要求的情況下回溯到上一步，重新選擇其他可能的路徑［4］。

通常，回溯法可以使用遞歸函數(shù)來實(shí)現(xiàn)，但它不是單純的遞歸算法。遞歸函數(shù)中包含兩個(gè)關(guān)鍵部分：一個(gè)是生成可行解的過程，即對(duì)當(dāng)前狀態(tài)進(jìn)行擴(kuò)展；另一個(gè)是判斷該狀態(tài)是否滿足條件，對(duì)應(yīng)分支是否有進(jìn)行下去的意義，即剪枝的過程［5］。具體步驟如下：

第一步：定義解空間，用樹來表示解空間。解空間表示所有可行的解的集合。定義解空間，并確定搜索解空間的結(jié)構(gòu)樹，即解空間樹。

第二步：定義約束函數(shù)和限界函數(shù)。定義約束函數(shù)和限界函數(shù)的目的是通過這兩種策略避免無效搜索，提高回溯法的搜索效率。約束函數(shù)的作用是在擴(kuò)展結(jié)點(diǎn)處減去不滿足約束的子樹，限界函數(shù)的作用是剪去得不到最優(yōu)解的子樹。因此這兩類函數(shù)都稱為剪枝函數(shù)。

第三步：以深度優(yōu)先的方式搜索解空間樹。在搜索的過程中通過兩個(gè)剪枝函數(shù)來避免無效搜索。對(duì)解空間樹的每個(gè)節(jié)點(diǎn)上的搜索具體過程為：當(dāng)前節(jié)點(diǎn)為活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向擴(kuò)展出一個(gè)新的結(jié)點(diǎn)來，并判斷約束條件或限界函數(shù)。如果此處不滿足約束條件或者限界函數(shù)，則剪枝，即此結(jié)點(diǎn)稱為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的活結(jié)點(diǎn)處，并使這個(gè)結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。回溯法以這種方式遞歸地在解空間樹中搜索，直至找到所要求的解或解空間樹中已無活結(jié)點(diǎn)為止。

假設(shè)有個(gè)背包，容量C= 30，有3件可選擇的物品，各物品的價(jià)值和體積以及按照單位體積的價(jià)值比排好序，見表2。

表2 物品清單

按照上述求解步驟，對(duì)此問題的求解過程如下：

（1）定義解空間，用樹來表示解空間。

該問題解空間為｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝，解空間樹如圖7所示。

圖7 解空間樹

（2）定義約束函數(shù)和限界函數(shù)。

定義約束函數(shù)c（i）=cv（i-1）+vi，cv（i-1）表示前i-1個(gè)物品中已經(jīng)放入背包的物品的體積，則c（i）表示當(dāng)前放入背包中的物品的體積，任何結(jié)點(diǎn)上必須滿足cv（i）≤C的約束條件，否則剪枝。

定義限界函數(shù)B（i）=cp（i-1）+r（i），cp（i-1）表示已經(jīng)放入背包中物品的價(jià)值，r（i）表示背包剩余容量可以存放的理想最大價(jià)值。r（i）可以通過貪心法的思想來求解，將物品按價(jià)值體積比的降序排序，優(yōu)先選擇比值高的物品，直到把整個(gè)背包撐滿的理想狀態(tài)可以存放的最大價(jià)值，則B（i）表示當(dāng)前狀態(tài)下將背包撐滿能放入物品的理想最大價(jià)值，如果用bp表示當(dāng)前記錄的最大組合的價(jià)值和，則如果B（i）≤bp，此分支沒有繼續(xù)下去的意義，故而剪枝。

（3）以深度優(yōu)先的方式搜索解空間樹。

根據(jù)上述的分析，定義cv表示當(dāng)前放入背包中的物品的體積，cp表示當(dāng)前放入背包中物品的價(jià)值和，bp表示當(dāng)前記錄的最優(yōu)組合的價(jià)值和，r表示還未做出選擇的剩余物品的價(jià)值和。得到問題的帶剪枝的以深度優(yōu)先方式搜索的解空間樹，如圖8所示。

圖8 帶剪枝的解空間樹

從圖8 可知，第3 層結(jié)點(diǎn)（1, 1, 0）、結(jié)點(diǎn)（0,0,0）和第4層結(jié)點(diǎn)（1,0,1）都因?yàn)榧s束條件或者限界函數(shù)執(zhí)行了剪枝，算法在執(zhí)行的過程中，執(zhí)行的分支數(shù)量大幅下降，由此算法的復(fù)雜度也得到大幅提升。完整的搜索過程為A→B→E→K→C→F→L。

算法BTknapsack（n,p,v,C）偽代碼如下：

算法backtrack(i,cv,cp)偽代碼如下：

回溯部分通過調(diào)用backtrack（i,cv,cp）函數(shù)來實(shí)現(xiàn)。該函數(shù)包含三個(gè)參數(shù)：當(dāng)前考慮到第幾個(gè)物品（即狀態(tài)），已選擇的物品總體積和總價(jià)值。如果所有物品都已經(jīng)考慮過，或者當(dāng)前已選物品體積達(dá)到背包容量，則更新最大價(jià)值并返回。如果cp+r小于等于bp，說明把背包撐滿的理想狀態(tài)能裝入的最大價(jià)值已經(jīng)不大于當(dāng)前的最大價(jià)值，則該分支沒有繼續(xù)下去的必要，因此直接返回，即剪枝。否則，對(duì)于第i個(gè)物品，可以有兩種選擇：選或不選。如果不選第i個(gè)物品，則直接遞歸調(diào)用backtrack（i+1,cv,cp）；如果選第i個(gè)物品，則需要判斷當(dāng)前已選物品總體積是否小于等于背包容量，如果是，則遞歸調(diào)用backtrack（i+1,cv+v［i］,cp+p［i］）。

4 分支限界法

分支限界法是一種求解最優(yōu)化問題的常用算法，它基于將問題空間劃分為一個(gè)個(gè)子集，每個(gè)子集對(duì)應(yīng)一個(gè)可行解，通過比較不同可行解的目標(biāo)函數(shù)值來逐步縮小搜索范圍，最終找到全局最優(yōu)解。分支限界法和回溯法類似，求解策略都是在問題的解空間上搜索問題解。但分支限界法與回溯法有著不同的求解目標(biāo)?；厮莘ǖ那蠼饽繕?biāo)是在約束條件的限制下，把解空間樹中滿足條件的所有解都找出來，而分支限界法的求解目標(biāo)則是在約束條件的限制下，找到滿足條件的一個(gè)解，即在某種意義下的一個(gè)最優(yōu)解［5］。

由于求解目標(biāo)的差異，導(dǎo)致分支限界法與回溯法在解空間樹中搜索問題解的方式也不相同。由上文可知回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。按照廣度優(yōu)先的搜索策略，分支限界法的搜索策略，每個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)，一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性生成其所有的兒子結(jié)點(diǎn)（分支）。這些兒子結(jié)點(diǎn)中，不可行解或者非最優(yōu)解的兒子結(jié)點(diǎn)被舍棄（剪枝），其余兒子結(jié)點(diǎn)加入活結(jié)點(diǎn)表（隊(duì)列）中，然后再從當(dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界函數(shù)），并根據(jù)函數(shù)值從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。這種方法稱為分支限界法。

從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同策略導(dǎo)致不同的分支限界法。最常見的有以下兩種方式。

（1）隊(duì)列式（FIFO）分支限界法。

隊(duì)列式分支限界法將活結(jié)點(diǎn)表組織成一個(gè)隊(duì)列，并按隊(duì)列的先進(jìn)先出原則選取下一個(gè)結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。

（2）優(yōu)先隊(duì)列式分支限界法。

優(yōu)先隊(duì)列式的分支限界法將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列，并按優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。

優(yōu)先隊(duì)列中的結(jié)點(diǎn)優(yōu)先級(jí)常用一個(gè)表示該結(jié)點(diǎn)耗費(fèi)或收益的函數(shù)來表示，即如果擴(kuò)展該結(jié)點(diǎn)，通過該函數(shù)來計(jì)算會(huì)帶來多大的效益，以此來決定結(jié)點(diǎn)的優(yōu)先級(jí)。函數(shù)值的確定通常采用堆來實(shí)現(xiàn)。

和回溯法類似，分支限界法求解問題的基本步驟如下：

第一步：定義解空間，用樹來表示解空間。解空間表示所有可行的解的集合，集合中一定包含問題的最優(yōu)解。定義解空間，并確定搜索解空間的結(jié)構(gòu)樹，即解空間樹。

第二步：定義約束函數(shù)和限界函數(shù)，統(tǒng)稱為剪枝函數(shù)。定義約束函數(shù)和限界函數(shù)的目的是通過這兩種策略來決定在擴(kuò)展中哪些兒子節(jié)點(diǎn)被舍棄（剪枝），不被舍棄的兒子結(jié)點(diǎn)加入到隊(duì)列中。

第三步：以廣度優(yōu)先的方式搜索解空間樹。在搜索的過程中和回溯法一樣，通過兩個(gè)剪枝函數(shù)來避免無效搜索。如果采用隊(duì)列式（FIFO）分支限界法，則不被舍棄的兒子結(jié)點(diǎn)依次加入隊(duì)列，以先進(jìn)先出的順序?qū)Y(jié)點(diǎn)進(jìn)行擴(kuò)展。如果采用優(yōu)先隊(duì)列式分支限界法，則按照某種策略求解每個(gè)兒子結(jié)點(diǎn)的優(yōu)先級(jí)對(duì)隊(duì)列進(jìn)行排序，每次擴(kuò)展隊(duì)列中優(yōu)先級(jí)最高的結(jié)點(diǎn)。

分支限界法也是一種常見的求解0-1背包問題的算法，它通過將問題分解成子問題并逐步減小搜索空間來尋找最優(yōu)解。具體地，可以先將所有物品按照單位重量的價(jià)值從大到小排序，然后從排好序的物品列表中依次選擇物品放入背包中。同時(shí)，維護(hù)一個(gè)上界和一個(gè)下界，以便剪枝減少搜索空間。繼續(xù)以表2中的物品清單為例來分析分支限界法求解0-1背包問題，具體步驟如下：

（1）定義解空間，用樹來表示解空間。

此步驟和回溯法完全相同，此處不再贅述。

（2）定義約束函數(shù)和限界函數(shù)，統(tǒng)稱為剪枝函數(shù)。

此步驟和回溯法完全相同，此處不再贅述。

（3）以廣度優(yōu)先的方式搜索解空間樹。

定義約束函數(shù)c（i）=cv（i-1）+vi，定義限界函數(shù)B（i）=cp（i-1）+r（i），兩個(gè)函數(shù)的定義同回溯法，此處不再贅述。限界函數(shù)B（i）的意義除了作為剪枝的依據(jù)，B（i）的值還作為結(jié)點(diǎn)的優(yōu)先級(jí)的值來決定在優(yōu)先隊(duì)列中是否下一次擴(kuò)展該結(jié)點(diǎn)。如果優(yōu)先級(jí)最高，則擴(kuò)展此結(jié)點(diǎn)，反之以優(yōu)先級(jí)的降序存放在優(yōu)先隊(duì)列中待擴(kuò)展。通過隊(duì)列中結(jié)點(diǎn)優(yōu)先級(jí)的設(shè)置，可以使得搜索的過程朝著目標(biāo)快速地逼近，簡化了搜索過程，提高了效率。搜索過程的總方式是廣度優(yōu)先，考慮B（i）的值為優(yōu)先級(jí)作為下一次擴(kuò)展結(jié)點(diǎn)選取的依據(jù)，因此，搜索的過程是基于廣度優(yōu)先但又不完全是傳統(tǒng)意義的廣度優(yōu)先搜索法。在圖8 中，優(yōu)先隊(duì)列的分支限界法的搜索過程為A→B→C→E→K→F→L。優(yōu)先隊(duì)列的搜索算法，以從當(dāng)前節(jié)點(diǎn)出發(fā)最理想的價(jià)值為優(yōu)先級(jí)，使得搜索過程能以最快的速度找到最優(yōu)解，后面結(jié)點(diǎn)的擴(kuò)展因當(dāng)前的bp值而發(fā)生剪枝，從而提升了算法的執(zhí)行效率。

根據(jù)上述分析，設(shè)計(jì)算法BBknapsack（n,p,v,C）的偽代碼如下：

通過wt＜=C約束條件來實(shí)現(xiàn)左枝的剪枝，通過限界up＞=bestp來實(shí)現(xiàn)右枝的剪枝，每個(gè)活結(jié)點(diǎn)擴(kuò)展出來的新結(jié)點(diǎn)，根據(jù)其優(yōu)先級(jí)up，加入到優(yōu)先隊(duì)列中，每次都選擇優(yōu)先級(jí)最高的結(jié)點(diǎn)來進(jìn)行擴(kuò)展。

5 算法對(duì)比實(shí)驗(yàn)

為了比較三種算法的性能，先用簡單的測試數(shù)據(jù)，令v={2,3,4,5},p={3,4,5,6}分別對(duì)C的值取8（最差情況）、取10（平均情況）和取12（最好情況）進(jìn)行測試，測試結(jié)果表明，三種情況執(zhí)行效率最高的為回溯法，執(zhí)行時(shí)間基本都在0.03 ms 左右，其次是動(dòng)態(tài)規(guī)劃法，執(zhí)行時(shí)間在0.3 ms 左右，性能最差的為分支限界法，執(zhí)行時(shí)間在1.5 ms左右。

為了比較大數(shù)據(jù)下三種算法的性能，分兩類數(shù)據(jù)進(jìn)行測試。一類固定n的大小為100，隨機(jī)生成100 個(gè)物品，每個(gè)物品的體積和價(jià)值在1～100 之間取值。對(duì)于從30～3000000 不同規(guī)模的背包容量，分別使用動(dòng)態(tài)規(guī)劃法、回溯法和分支限界法來求解，并計(jì)算求解時(shí)間，實(shí)驗(yàn)結(jié)果見表3。另一類固定背包容量的大小為300，隨機(jī)生成n的規(guī)模為10～1000000 個(gè)物品，每個(gè)物品的體積和價(jià)值在1～100 之間取值。對(duì)于不同規(guī)模的物品數(shù)量，分別用三種算法求解，并計(jì)算求解時(shí)間，實(shí)驗(yàn)結(jié)果見表4。

表3 物品規(guī)模固定實(shí)驗(yàn)結(jié)果

表4 背包容量固定實(shí)驗(yàn)結(jié)果

對(duì)上述兩表生成對(duì)比圖形，如圖9 和圖10所示。

圖9 不同背包容量性能比較

圖10 不同物品數(shù)量性能比較

結(jié)合上述圖和表可以看出，三種算法在求解0-1 背包問題時(shí)的性能差異較大。具體來說，回溯法比較穩(wěn)定，不論物品數(shù)量和背包容量發(fā)生什么變化，其求解問題的時(shí)間基本都在3 ms 以內(nèi)。回溯法的執(zhí)行時(shí)間對(duì)背包容量的增加不敏感，對(duì)物品數(shù)量的增加執(zhí)行時(shí)間有小幅上漲。而動(dòng)態(tài)規(guī)劃法，固定物品的數(shù)量，不同的背包容量，求解問題的時(shí)間從0.54 ms 增長到1542 ms，隨著背包容量的增加，當(dāng)增加到30000時(shí)，算法性能直線下降。固定背包容量大小，不同的物品數(shù)量規(guī)模，動(dòng)態(tài)規(guī)劃的性能表現(xiàn)和固定物品數(shù)量類似。原因是動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是填規(guī)模為n×C的表，算法執(zhí)行時(shí)間和填表的規(guī)模有關(guān)。分支限界法的性能介于動(dòng)態(tài)規(guī)劃和回溯法之間，和回溯法類似，算法對(duì)背包容量的變化不敏感，對(duì)物品數(shù)量的增加敏感，且和回溯法相比，隨著物品數(shù)量的增加，分支限界法的執(zhí)行時(shí)間增長明顯。分支限界法的性能和回溯法比不具優(yōu)勢的主要原因在于應(yīng)用優(yōu)先隊(duì)列存儲(chǔ)結(jié)點(diǎn)，優(yōu)先隊(duì)列的應(yīng)用有較大的時(shí)間消耗。

總體而言，性能上回溯法具有絕對(duì)優(yōu)勢，當(dāng)問題規(guī)模（物品數(shù)量和背包容量）較小時(shí)，動(dòng)態(tài)規(guī)劃優(yōu)于分支限界；當(dāng)問題規(guī)模較大時(shí)，分支限界優(yōu)勢明顯。究其原因，回溯法和分支限界法雖然本質(zhì)是窮舉，但當(dāng)物品數(shù)量或背包容量很大時(shí)，通過剪枝的優(yōu)化，大大減少了子問題執(zhí)行的數(shù)量，算法性能得到極大提高。但反觀動(dòng)態(tài)規(guī)劃算法，不論問題規(guī)模和背包容量多大，都要將其所有子問題求解，當(dāng)問題規(guī)模小、背包容量小時(shí)，子問題的數(shù)量不大，整個(gè)問題求解時(shí)間短，但當(dāng)問題規(guī)模和背包容量達(dá)到一定規(guī)模時(shí)，待求解的子問題數(shù)量也同時(shí)達(dá)到相當(dāng)?shù)囊?guī)模，求解這些子問題所需要的時(shí)間自然也就具有較大規(guī)模。因此，在實(shí)際應(yīng)用中，對(duì)規(guī)模較小的問題，推薦使用動(dòng)態(tài)規(guī)劃法，當(dāng)問題規(guī)模較大或者背包容量較大時(shí)，則推薦使用回溯法來求解。當(dāng)采用有效的排序算法和優(yōu)先隊(duì)列時(shí)，分支限界法也是一個(gè)不錯(cuò)的選擇。

6 結(jié)語

綜上所述，動(dòng)態(tài)規(guī)劃、回溯法和分支限界法是三種常見的求解0-1背包問題的方法。動(dòng)態(tài)規(guī)劃算法具有良好的理論保證，當(dāng)問題規(guī)模不大時(shí)可以在較短的時(shí)間內(nèi)求解出全局最優(yōu)解?；厮莘ê头种藿绶ㄊ且环N基于搜索的高效算法，因其本質(zhì)是窮舉，且是帶剪枝的優(yōu)化窮舉，故可以在合理的時(shí)間內(nèi)找到全局最優(yōu)解。在實(shí)際應(yīng)用中，我們需要根據(jù)問題特點(diǎn)和求解需求來靈活選擇算法，并盡可能利用并行化和分布式計(jì)算等技術(shù)來提高求解效率。