求解0—1背包問(wèn)題算法研究

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

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

中圖分類(lèi)號(hào)：TP312 文獻(xiàn)識(shí)別碼：A 文章編號(hào)：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年代首次提出了背包問(wèn)題（Knapsack problem，簡(jiǎn)稱(chēng)KP），在文獻(xiàn)[2]中，闡述了該問(wèn)題是一個(gè)NP-難問(wèn)題，在背包問(wèn)題中，我們很難設(shè)計(jì)出多項(xiàng)式時(shí)間算法，除非P=NP。0-1背包問(wèn)題就是，給定一個(gè)容量為的背包和件具有價(jià)值的物品，在不超過(guò)背包容量的前提下，選擇若干物品放入背包，使得裝入背包的物品總價(jià)值最大。同時(shí)給出一種放置物品的方案。

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

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

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

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

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

二、求解0-1背包問(wèn)題常用算法研究

（一）求解0-1背包問(wèn)題的精確算法

1.枚舉法

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

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

2.回溯法

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

用回溯法求解0-1背包問(wèn)題的一般步驟：

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）初始化迭代條件：

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

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

（二）求解0-1背包問(wèn)題的近似算法

1.貪婪算法

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

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

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

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

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

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

2.模擬退火算法

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

模擬退火算法求解0-1背包問(wèn)題的步驟：

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

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

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

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

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

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

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

3.遺傳算法

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

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

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

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

目前，通過(guò)結(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)了算法的搜索能力差、收斂速度慢等問(wèn)題。

四、結(jié)語(yǔ)

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

參考文獻(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)雯飛，吳子瑩，楊波.背包問(wèn)題的動(dòng)態(tài)規(guī)劃改進(jìn)算法[J].中南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2016，32（4）：101-105.

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

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

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

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

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

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

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