李軍民，傅云鳳

(西安科技大學(xué)計算機學(xué)院，陜西西安 710054)

0-1背包問題［1］是一個典型的NP難問題，可作為許多工業(yè)場合的應(yīng)用模型，如資本預(yù)算、貨物裝載和存儲分配問題等。對該問題的求解，既具有理論價值又具有實際意義。目前已有的求解方法可分為兩大類，一類是精確算法，如動態(tài)規(guī)劃算法［2］、回溯法［3］、分支限界法［4］;另一類是近似算法，如貪婪法［5］、蟻群算法［6］和遺傳算法［7］。本文對文獻(xiàn)［8］中的動態(tài)規(guī)劃改進(jìn)算法進(jìn)行分析，此算法存在不足之處:其空間資源浪費較大。為了克服這一缺點，本文提出了采用動態(tài)鏈表存儲數(shù)據(jù)的實現(xiàn)方式改進(jìn)此算法，從而達(dá)到改善其空間復(fù)雜度的目的。

1 問題描述

給定n種物品和一個背包，對n種物品進(jìn)行編號 1，2，…，n，物品 i的重量 wi，其價值 pi，背包容量為 c，給定c ＞ 0，wi＞ 0，pi＞ 0，1≤i≤n，要求找出一個 n 元向量(x1，x2，…，xn)，xi∈ {0，1}，使得達(dá)到最大。

2 求解0－1背包問題的動態(tài)規(guī)劃算法

2.1 0－1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)

根據(jù)0－1背包問題的描述，其具有最優(yōu)子結(jié)構(gòu)和重疊子問題性質(zhì)。最優(yōu)子結(jié)構(gòu)即:設(shè)(x1，x2，…，xn)是0－1背包問題的最優(yōu)解，則(x2，x3，…，xn)是子問題(從物品2至物品n中選取，裝入背包)的最優(yōu)解。

2.2 規(guī)劃數(shù)學(xué)模型

設(shè)m(i，j)是背包容量為j時，可選物品是i，i+1，…，n時0－1背包問題的最優(yōu)值。則可建立遞歸關(guān)系式

3 一種動態(tài)規(guī)劃法的改進(jìn)算法分析

3.1 該動態(tài)規(guī)劃改進(jìn)算法的思路

由m(i，j)的遞歸式可知，在一般情況下，對每一個確定的i，函數(shù)m(i，j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)［8］。跳躍點［9］是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i，j)由全部跳躍點唯一確定，因此，針對每一個i值，只記錄m(i，j)的跳躍點(j，m(i，j))也可求出背包問題的最優(yōu)解和最優(yōu)值。

該算法對于每一個確定的i采用表c［i］來記錄函數(shù)m(i，j)的全部跳躍點。c［i］可依據(jù)式(1)和式(2)遞歸的由c［i+1］得到，初始時令c［n+1］={(0，0)}。函數(shù)m(i，j)的全部跳躍點是函數(shù)m(i+1，j)的跳躍點集c［i+1］和函數(shù)m(i+1，j－ wi)+pi的跳躍點集d［i+1］的并集，d［i+1］由c［i+1］來確定，公式如下

設(shè)(a，b)和(c，d)是 c［i+1］∪ d［i+1］中的兩個跳躍點，當(dāng)c≥a且d＜b時，(c，d)受控于(a，b)，將(c，d)刪除。因此，在由 c［i+1］計算c［i］的過程中，先由 c［i+1］計算 d［i+1］，再合并 c［i+1］和 d［i+1］，并清除受控點得到 c［i］。

3.2 該動態(tài)規(guī)劃改進(jìn)算法的分析

此算法采用二維數(shù)組c［］［2］記錄跳躍點的坐標(biāo)值(j，m(i，j))，從而實現(xiàn)表 c［i］對跳躍點的記錄。此算法的空間復(fù)雜度在于跳躍點集(j，m(i，j))(1≤i≤n，0≤j≤c)存儲所占用的空間，因此其空間復(fù)雜度為

此算法對于每一次求得的跳躍點集c［i］(1≤i≤n)都記錄于二維數(shù)組c［］［2］中，跳躍點集c［i+1］和c［i］存在相同的跳躍點，這些相同的跳躍點需要重復(fù)記錄于數(shù)組中，且使用靜態(tài)數(shù)組，事先需要定義較大的數(shù)組來避免溢出的發(fā)生，這樣使得空間資源浪費較大。

4 利用動態(tài)鏈表記錄跳躍點改進(jìn)上述算法

為了克服上述算法求解0－1背包問題的不足，本文采用動態(tài)鏈表結(jié)構(gòu)存儲跳躍點集，來減輕空間資源的浪費，其算法介紹如下。

4.1 改進(jìn)算法的思路

1)對每一個確定的i，仍用一個表c［i］來存儲函數(shù)m(i，j)的全部跳躍點(j，m(i，j))(0 ≤j≤c)，但采用動態(tài)鏈表結(jié)構(gòu)實現(xiàn)表c［i］對跳躍點集的記錄。

2)由式(1)和式(3)可知，跳躍點集c［i］可由表 c［i+1］和表 d［i+1］確定，表 d［i+1］可由c［i+1］確定。初始時，令c［n+1］={(0，0)}，新建一個鏈表結(jié)點，其重量和價值均為0，以此來實現(xiàn)對跳躍點(0，0)的記錄。

3)由式(3)求跳躍點集d［i+1］時，設(shè)置一個布爾型變量，標(biāo)識表d［i+1］中每次求得的點是否受控。將上述判斷受控點的標(biāo)準(zhǔn)改為:設(shè)??(a，b)∈c［i+1］，??(c，d)∈d［i+1］，當(dāng)a ＞ c，b≤ d 或 a=c，b ＜ d 時，(a，b)受控于(c，d);當(dāng) c≥ a，d ≤ b時，(c，d)受控于(a，b)。每次求得表d［i+1］中的一個點時，判斷其是否為受控點，若不為受控點，將其加入鏈表;否則，舍棄;同時查看表c［i+1］中的點是否受控，若受控，則標(biāo)記其為新增受控點。

4)在求得跳躍點集d［i+1］后，遍歷整個鏈表，若鏈表中的結(jié)點被標(biāo)記為新增受控點，則標(biāo)記該結(jié)點已受控。遍歷鏈表結(jié)束時，沒有標(biāo)記為已受控的跳躍點集就是 c［i］。這樣就由表 c［i+1］和表 d［i+1］求得表 c［i］。

5)按照上述方法，可遞歸地求出表c［1］，它記錄了m(1，j)的全部跳躍點。由于鏈表中記錄的跳躍點不是按照m(i，j)值由小到大的順序排列的，需要遍歷鏈表尋求價值最大的結(jié)點，該結(jié)點的價值即為最優(yōu)值。

6)構(gòu)造最優(yōu)解，其步驟為:

Step1 初始時，令i=1，y初始化為式(5)中求得的價值最大的結(jié)點的重量值j0，m初始化為該結(jié)點的價值m(1，j0)。

Step 2 遍歷鏈表中的所有結(jié)點(j，m(i，j))(1 ≤ i≤ n，0 ≤ j≤ c)，如果 ?(j'，m(i'，j'))使 j'+wi=y，m(i'，j')+pi=m 成立，則 xi=1，y=j'，m=m(i'，j');否則 xi=0;然后令 i++。

Step 3 重復(fù)Step2，直至i＞n為止。

4.2 改進(jìn)算法的分析

此改進(jìn)算法采用動態(tài)鏈表記錄跳躍點集，其空間復(fù)雜度在于跳躍點集的存儲。但是，不需要重復(fù)記錄已存在的跳躍點，只需將每次求得的新增跳躍點加入，又每次求得的跳躍點個數(shù)不超過2i，故最終求得的跳躍點總數(shù)不超過2n。因此，空間復(fù)雜度為O(2n)。

該方法遞歸地求出跳躍點集c［1］，不需要重復(fù)記錄已存在的跳躍點。所以不存在同一跳躍點的重復(fù)記錄問題，且采用動態(tài)鏈表結(jié)構(gòu)記錄跳躍點，大大節(jié)省了空間資源，彌補了采用二維數(shù)組記錄跳躍點這種動態(tài)規(guī)劃改進(jìn)算法的不足。

5 算法測試實例

有5種物品和一個背包，背包容量為100，裝入的物品不可分割，求取此0－1背包問題的最優(yōu)解和最優(yōu)值。每種物品的重量和價值如表1所示。

動態(tài)規(guī)劃法、二維數(shù)組記錄跳躍點的動態(tài)規(guī)劃改進(jìn)算法和動態(tài)鏈表記錄跳躍點的動態(tài)規(guī)劃改進(jìn)算法，采用i記錄物品編號，利用數(shù)組w［n］記錄物品重量，數(shù)組p［n］記錄物品價值，bestp記錄最優(yōu)值，x［n］記錄最優(yōu)解。3種方法解決本例中的0－1背包問題的運行結(jié)果對比如表2所示。程序運行時間以秒為單位，n值較小時，3種方法的程序運行時間幾乎沒有差異;當(dāng)n值取100時，動態(tài)鏈表記錄跳躍點的動態(tài)規(guī)劃改進(jìn)法的運行時間較前兩種方法在十分位出現(xiàn)差異。

表1 背包問題信息表Tab．1 Information sheet of knapsack problem

表2 3種方法解決0－1背包問題的運行結(jié)果比較Tab．2 Comparison of computational results of three methods solving 0 －1 knapsack problem

表2表明，采用上述3種方法，該0－1背包問題的最優(yōu)解、最優(yōu)值和裝入背包的重量均相同，進(jìn)而表明動態(tài)鏈表結(jié)構(gòu)記錄跳躍點集的動態(tài)規(guī)劃改進(jìn)算法的有效性。通過空間復(fù)雜度的對比，驗證了動態(tài)鏈表結(jié)構(gòu)記錄跳躍點集的實現(xiàn)方式在降低空間復(fù)雜度方面的優(yōu)越性。

動態(tài)規(guī)劃法的空間復(fù)雜度在于記錄函數(shù)m(i，j)的值，空間復(fù)雜度為 Ω(nc)。二維數(shù)組存儲跳躍點的動態(tài)規(guī)劃改進(jìn)法的空間復(fù)雜度為，動態(tài)鏈表記錄跳躍點的動態(tài)規(guī)劃改進(jìn)法的空間復(fù)雜度為O(2n)。前兩種方法均采用二維數(shù)組存儲數(shù)據(jù)，為了避免溢出情況的發(fā)生，需要預(yù)先定義較大的存儲空間。隨著n值的增大，且在c值較大的情況下，動態(tài)鏈表結(jié)構(gòu)記錄跳躍點集的實現(xiàn)方式在降低空間復(fù)雜度方面的優(yōu)越性越明顯。

6 結(jié)語

本文基于動態(tài)規(guī)劃法的一種改進(jìn)策略，進(jìn)行算法分析，進(jìn)而提出其改進(jìn)算法，改善了原算法的空間復(fù)雜度。通過實例驗證了該改進(jìn)算法的有效性，且證實其空間復(fù)雜度的優(yōu)越性。隨著n值的增大，且在c較大的情況下，此改進(jìn)算法的空間復(fù)雜度優(yōu)越性越明顯;但是，它的程序運行時間較前兩種方法要長一些。為了使該改進(jìn)算法的應(yīng)用價值更好地發(fā)揮出來，今后，將嘗試?yán)迷摳倪M(jìn)算法的思想解決其他問題。

［1］ 王曉東.計算機算法設(shè)計與分析［M］.北京:電子工業(yè)出版社，2012，2.

［2］ 唐敏，劉冠蓉.用動態(tài)規(guī)劃法和貪心法解決背包問題［J］.軟件導(dǎo)刊，2007(5):111-113.

［3］ 劉繼，夏定純.用動態(tài)規(guī)劃法與回溯法實現(xiàn)0-1背包問題的比較［J］.科技信息，2010(19):458.

［4］ 趙鑫.0/1背包問題分支限界法在C++程序?qū)崿F(xiàn)中的難點解析［J］.產(chǎn)業(yè)與科技論壇，2012(3):69-70.

［5］ 蔣力，武坤.0-1背包問題貪婪算法應(yīng)用研究［J］.計算機與數(shù)學(xué)工程，2007(6):32-33.

［6］ 秦玲，白云.解0-1背包問題的蟻群算法［J］.計算機工程，2006(6):212-214.

［7］ 王莉，紹定宏.基于遺傳算法的0/1背包問題求解［J］.計算機仿真，2006(3):154-156.

［8］ 呂聰穎，趙剛彬.求解0-1背包問題的動態(tài)規(guī)劃分析［J］.南陽理工學(xué)院學(xué)報，2011(2):17-21.

［9］ LEVITIN A.算法設(shè)計與分析基礎(chǔ)［M］.北京:清華大學(xué)出版社，2004.