求解0—1背包問題算法研究

摘要：本文主要概述了求解0-1背包問題的兩大類算法：精確算法和近似算法，并分析了這些算法的優(yōu)缺點(diǎn)，并提出了求解該問題的算法發(fā)展趨勢。

關(guān)鍵詞：0-1背包問題；精確算法；近似算法

中圖分類號：TP312 文獻(xiàn)識別碼：A 文章編號：1001-828X（2017）010-0-03

The Study of the 0-1 Knapsack Problem Algorithm

Abstract： This paper mainly summarizes the solving 0-1 knapsack problem algorithm of two categories： accurate and approximate algorithms， and analyzes the advantages and disadvantages of these algorithms， and put forward the development trend of algorithms to solve the problem.

Keywords： 0-1 knapsack problem， precise algorithm， approximate algorithm

Dantzig[1]在20世紀(jì)50年代首次提出了背包問題（Knapsack problem，簡稱KP），在文獻(xiàn)[2]中，闡述了該問題是一個NP-難問題，在背包問題中，我們很難設(shè)計(jì)出多項(xiàng)式時間算法，除非P=NP。0-1背包問題就是，給定一個容量為的背包和件具有價值的物品，在不超過背包容量的前提下，選擇若干物品放入背包，使得裝入背包的物品總價值最大。同時給出一種放置物品的方案。

背包問題就有普遍的應(yīng)用背景，在日常的許多實(shí)踐中如：材料切割、資源有效分配問題、資金估算的問題、運(yùn)輸過程的貨倉裝載等起著很大的作用，許多的組合優(yōu)化問題都可以簡化為背包問題，背包問題的各種解法也可用來解決組合優(yōu)化問題，因此對0-1背包問題的解法進(jìn)行深入的研究具有重大的意義。

一、0-1背包問題數(shù)學(xué)模型

在組合優(yōu)化領(lǐng)域中，背包問題是一個典型的NP-難問題。在材料切割、資源有效分配問題、資金估算的問題、運(yùn)輸過程的貨倉裝載等領(lǐng)域有重大的作用。0-1背包問題可以描述為：給定一個容量為C的背包和n件物品，物品i的重量為wi，價值為pi，0-1背包問題的數(shù)學(xué)模型可以轉(zhuǎn)化為：

模型中，xi為0-1變量，當(dāng)物品被選入背包時，xi=1，否則，物品沒被選如背包，xi=0。

背包問題引起了很多學(xué)者的不斷探究，目前，求解0-1背包問題的算法大致上可以分為精確算法和近似算法兩大類，其中枚舉法、分支定界法、回溯法、圖論法、動態(tài)規(guī)劃法等屬于精確算法，這些算法的時間復(fù)雜度都偏大，導(dǎo)致其實(shí)用性受到限制。近似算法有貪婪算法、模擬退火算法、遺傳算法、螞蟻算法等，雖然近似算法在時間上占有優(yōu)勢，但是該算法只能夠得到問題的近似解，解的質(zhì)量大幅度下降。本文將針對幾種常用的0-1背包問題的解法進(jìn)行闡述。

二、求解0-1背包問題常用算法研究

（一）求解0-1背包問題的精確算法

1.枚舉法

枚舉法也稱為窮舉法，該算法的基本思路是，針對具體問題特性，首先將該問題的所有可行解一一列舉出來，同時在窮舉的過程中，驗(yàn)證每個可行解是否為問題的最優(yōu)解，若是，我們就保留該解，否則遺棄它。

用枚舉法解決0-1背包問題，首先，我們必須一一列舉出件物品全部的子集，再尋找全部可行的子集（物品總重量不超出背包本身所能承受重量的子集），然后對這些子集進(jìn)行驗(yàn)證，計(jì)算出各個可行子集的總重量以及對應(yīng)的價值和，分析比較求出價值最大的子集。用枚舉法求解0-1背包問題，首先需要窮舉出所有可行解，然后在判斷是否為最優(yōu)解，算法最后一定可以得到全局最優(yōu)解。對于有n件物品的背包問題，不管產(chǎn)生子集的計(jì)算方法的效率有多高，枚舉法始終會造成一個O（2n）的算法，當(dāng)n很大時，顯然該方法的時間復(fù)雜度太大。

2.回溯法

回溯法又稱為試探法，它是一種按照深度優(yōu)先策略進(jìn)行系統(tǒng)地搜索問題最優(yōu)解的方法?；厮莘ǖ幕舅枷胧?，對于給定問題，先定義解空間以及解空間的結(jié)構(gòu)（典型的結(jié)構(gòu)是樹或圖），然后解空間狀態(tài)樹中從根節(jié)點(diǎn)出發(fā)按照深度優(yōu)先策略進(jìn)行搜索。在搜索至任意結(jié)點(diǎn)時，總是先進(jìn)行判斷，該結(jié)點(diǎn)是否包含問題的可行解，若包含問題的可行解就繼續(xù)進(jìn)入該子樹搜索，否則，進(jìn)行相應(yīng)的剪枝。按照此方法逐層向上回溯，直到搜索完整個解空間，找到問題的最優(yōu)解。

用回溯法求解0-1背包問題的一般步驟：

（1）定義解空間：0-1背包問題的解可以用n維的向量X={（x1，x2，…，xn）|xi=0或1，i=1，2，…，n}來表示，其中每個分量xi是一個0-1決策變量，xi=1就表示第i件物品被裝入背包，否則xi=2就表示第件物品不被裝入背包。

（2）確定解空間的結(jié)構(gòu)：對于給定的n件物品，我們有序的考慮每個物品是否被選入背包中，以便枚舉出全部的狀況，從而可以用一顆高度為n的完全二叉樹（如圖一）來表示背包問題的解空間，從根節(jié)點(diǎn)到葉子的每一條路徑就對應(yīng)解空間的一個解向量。

（3）搜索解空間：從根節(jié)點(diǎn)利用深度優(yōu)先策略來搜索狀態(tài)空間樹，只要左節(jié)點(diǎn)是可行解就一直沿著左節(jié)點(diǎn)向下搜索，對于右節(jié)點(diǎn)，定義界限函數(shù)判斷右子樹是否包含問題的最優(yōu)解，從而實(shí)行相應(yīng)的剪枝，避免無效搜索，重復(fù)此步驟，直到空間狀態(tài)樹被搜索完，找到問題的最優(yōu)解。

回溯法在解決0-1背包問題時，利用深度優(yōu)先的策略進(jìn)行搜索解空間樹，在左子樹是可行的情況下，一直進(jìn)入左子樹搜索，否則考慮右子樹搜索，定義了界限函數(shù)，只有右子樹滿足該界限函數(shù)，即可能包含最優(yōu)解時才進(jìn)入右子樹進(jìn)行搜索，否則進(jìn)行剪枝，這樣大大減少了節(jié)點(diǎn)的個數(shù)，加快了搜索速度。但是，在糟糕的情況下，有O（2n）個右子樹結(jié)點(diǎn)需要計(jì)算界限函數(shù)，由于界限函數(shù)的時間復(fù)雜度是O（n），因此回溯法求解0-1背包問題時間復(fù)雜度為O（n×2n）。

3.動態(tài)規(guī)劃

20世紀(jì)50年代，動態(tài)規(guī)劃算法首次由R.E.Bellman等提出，它是一種將多階段決策轉(zhuǎn)化為單階段決策求解問題的辦法?；静襟E是：

（1）尋找最優(yōu)解的本質(zhì)，構(gòu)造它的結(jié)構(gòu)特性；

（2）遞歸的去定義最優(yōu)值；

（3）自底向上的去求最優(yōu)值；

（4）依據(jù)算出來的最優(yōu)值所得的信息去構(gòu)造一個最優(yōu)解。

如果X=（x1，x2，…，xn）是0-1背包問題的最優(yōu)解，則（x1，x2，…，xn）是子問題：，的最優(yōu)解。0-1背包問題具有最優(yōu)化原理，因此該問題可以用動態(tài)規(guī)劃來求解。

動態(tài)規(guī)劃法求解0-1背包問題的一般步驟：

（1）建立規(guī)劃模型：設(shè)子問題是m（i，j），它表示前個物品放到背包容量為時所能獲得的最大價值。

（2）初始化迭代條件：

（3）建立狀態(tài)轉(zhuǎn)移方程：根據(jù)0-1背包問題滿足最優(yōu)子結(jié)構(gòu)的性質(zhì)，建立如下狀態(tài)轉(zhuǎn)移方程：

動態(tài)規(guī)劃是求解0-1背包問題的一種常用算法，算法的原理以及思路清楚明了，實(shí)施起來比較簡單。算法的時間復(fù)雜度為O（nC），但是在規(guī)模較大的問題上動態(tài)規(guī)劃算法并不理想，它在求解規(guī)劃較大的背包問題上還是存在著困難，針對動態(tài)規(guī)劃算法的也出現(xiàn)了一些改進(jìn)算法，文獻(xiàn)[3]他們通過改進(jìn)動態(tài)規(guī)劃算法的狀態(tài)表示從而減少狀態(tài)個數(shù)的計(jì)算，以此提高算法的時間效率。

（二）求解0-1背包問題的近似算法

1.貪婪算法

貪婪算法是一種啟發(fā)式算法，采用自頂向下的迭代方法相繼做出貪心選擇。算法在迭代過程中的每一步選擇在當(dāng)前狀態(tài)看來是最優(yōu)的選擇，卻沒有從全局最優(yōu)考慮。該算法試圖通過每步的局部最優(yōu)得到全局最優(yōu)解。但是該算法并不總能夠得到問題的最優(yōu)解。

選取價值最大者、選取重量最小者、選取單位價值最大者（價值密度最大者）是求解0-1背包問題常用的三種貪心策略。本文采用價值密度（價值重量比）最大的貪婪策略，求解 0-1 背包問題的過程如下：

①分別求出給定的n件物品的價值密度（價值重量比），

②按照n件物品的價值密度，進(jìn)行降序排列

③從價值密度最大的物品開始，按照步驟②中物品的排序依次做出貪心選擇，若當(dāng)前物品的重量小于背包剩余的容量，則將該物品放入背包，并對該物品進(jìn)行標(biāo)記（表明已經(jīng)被選中放入包中），重復(fù)該步驟，直到物品的重量大于背包剩余的容量無法再裝入物品為止。

貪婪算法在第二步將物品按照價值密度大小進(jìn)行降序排列花費(fèi)了主要的時間，因此貪心算法的時間復(fù)雜度為O（nlogn）。

2.模擬退火算法

模擬退火（Simulated Annealing，SA）是一種基于蒙特卡羅迭代求解策略的啟發(fā)式隨機(jī)尋優(yōu)算法，它來源于固體退火原理，從某個較高的初始溫度出發(fā)，隨著溫度參數(shù)的不斷下降，同時，結(jié)合概率突跳特性，在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即使處于局部最優(yōu)解，也能夠概率性地跳出并最終收斂到全局最優(yōu)解。

模擬退火算法求解0-1背包問題的步驟：

（1）構(gòu)建0-1背包問題的解空間，選擇算法迭代初始解。0-1背包問題的解空間，因?yàn)槌跏冀鈱λ惴ㄗ罱K所得的結(jié)果影響不大，一般我們選擇（0，0，…，0）為初始解。

（2）新解的構(gòu)造。構(gòu)造新解一般有三種情況，①隨機(jī)選取物品i，若不在背包中則將其裝入；②隨機(jī)選取物品i，若不在背包中將其放入，同時從背包中隨機(jī)取出物品j；③隨機(jī)選取物品i，若在包中則將其取出，同時隨機(jī)放入物品j。

（3）針對新解的構(gòu)造計(jì)算目標(biāo)函數(shù)差（背包的價值差）和重量差。目標(biāo)函數(shù)差為：

相應(yīng)的背包的重量差：

（4）接受策略。該算法采用了擴(kuò)充的蒙特卡洛準(zhǔn)則：

其中為當(dāng)前狀態(tài)下背包重量，為溫度控制參數(shù)。

模擬退火算法中的溫度控制參數(shù)控制著優(yōu)化方向，向目標(biāo)逼近，同時以概率來接收劣質(zhì)解，有效的避免陷入局部最優(yōu)，從而最終趨于全局最優(yōu)解。

3.遺傳算法

遺傳算法是借鑒生物進(jìn)化法則而形成的一種自適應(yīng)全局化概率搜索算法。它從初始種群開始，經(jīng)過選擇、交叉、變異操作生成新的種群，由此更新種群直到滿足終止條件，從而完成最優(yōu)解的自適應(yīng)搜索。一般計(jì)算步驟如下：

從上面的算法流程，我們可以看出遺傳算法是從串集而不是單個初始解開始迭代求最優(yōu)解，因此搜索覆蓋面積大，利于全局最優(yōu)解的獲得，同時，算法采用傳統(tǒng)的二進(jìn)制編碼，僅用適應(yīng)度函數(shù)評估個體等這使得遺傳算法實(shí)現(xiàn)比較簡單。但是遺傳算法存在過早收斂、算法精度、可行性缺乏定量分析方法，進(jìn)化后期多樣性降低等問題；隨著背包規(guī)模的擴(kuò)大，常因陷入局部最優(yōu)解使得求解質(zhì)量不高。

三、求解0-1背包問題的其他算法以及改進(jìn)算法

除了上面介紹的幾種算法外，求解0-1背包問題的算法還有許多如：蟻群算法、粒子群優(yōu)化算法、禁忌搜索算法、演化算法[4]、二進(jìn)制狼群算法[5]、DNA算法等。

目前，通過結(jié)合各算法的優(yōu)缺點(diǎn)出現(xiàn)了許多混合算法。文獻(xiàn)[6]中，將貪婪法和遺傳法結(jié)合提出了改進(jìn)的排擠遺傳算法。文獻(xiàn)[7]將模擬退火思想引入遺傳算法，有效的克服了遺傳算法易于陷入局部最優(yōu)解的缺點(diǎn)。在文獻(xiàn)[8]中將粒子群優(yōu)化算法中引入粒子速度權(quán)重值自適應(yīng)調(diào)整策略，有效的改進(jìn)了算法的搜索能力差、收斂速度慢等問題。

四、結(jié)語

從本文的闡述我們可以看出，盡管求解0-1背包問題的算法有很多，但是若背包問題規(guī)模過大的話，這些算法在時間或空間的復(fù)雜度上還是相當(dāng)大的，應(yīng)用起來還存在著一定的局限性。所以我們需要對現(xiàn)有的算法進(jìn)行理論上更深刻的研究，從而對算法進(jìn)行改進(jìn)與完善。同時繼續(xù)研究多種算法的混合優(yōu)化算法，結(jié)合其他學(xué)科，提出新的更優(yōu)算法。而我們也可以從對背包問題解法的研究中得到更多的啟發(fā)，從而能更好的理解其它組合優(yōu)化問題的解法，推動組合最優(yōu)化問題的解法研究。

參考文獻(xiàn)：

[1]G.B.Danztig. Dsiceret Variable Extremum Problems[J]. Operations Research， 1957 （5）： 266-277.

[2]M R Garey， D S Johnson. Computers and Intractability： A Guide to the Theory of NP-Completeness[J]. San Francisco： W H Freeman and Co， 1979.

[3]藍(lán)雯飛，吳子瑩，楊波.背包問題的動態(tài)規(guī)劃改進(jìn)算法[J].中南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2016，32（4）：101-105.

[4]王熙照，賀毅朝.求解背包問題的演化算法[J].軟件學(xué)報(bào)，2017，28（1）：1-16.

[5]吳虎勝，張鳳鳴，戰(zhàn)仁軍，汪送，張超.求解0-1背包問題的二進(jìn)制狼群算法[J].系統(tǒng)工程與電子系統(tǒng)，2014，36（8）：1660-1666.

[6]劉文濤，胡家寶.求解 0-1 背包問題的改進(jìn)排擠遺傳算法[J].計(jì)算機(jī)工程與設(shè)計(jì)， 2011，32（6）.

[7]張盛意，蔡之華，占志剛.基于改進(jìn)模擬退火的遺傳算法求解 0-1 背包問題[J]. 微電子學(xué)與計(jì)算機(jī)，2011，28（2）：61-64.

[8]蔡敏.背包問題求解的建模及性能分析[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào)：自然科學(xué)漢文版，2016，45（1），13-16.

作者簡介：田秀芹（1988-），女，河南鹿邑人，助教，理學(xué)碩士，主要從事稀疏優(yōu)化研究。

基金項(xiàng)目：2017年度廣西高校中青年教師基礎(chǔ)能力提升項(xiàng)目，項(xiàng)目編號：2017KY0712。