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

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

關鍵詞：0-1背包問題；精確算法；近似算法

中圖分類號：TP312 文獻識別碼：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世紀50年代首次提出了背包問題（Knapsack problem，簡稱KP），在文獻[2]中，闡述了該問題是一個NP-難問題，在背包問題中，我們很難設計出多項式時間算法，除非P=NP。0-1背包問題就是，給定一個容量為的背包和件具有價值的物品，在不超過背包容量的前提下，選擇若干物品放入背包，使得裝入背包的物品總價值最大。同時給出一種放置物品的方案。

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

一、0-1背包問題數學模型

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

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

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

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

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

1.枚舉法

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

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

2.回溯法

回溯法又稱為試探法，它是一種按照深度優先策略進行系統地搜索問題最優解的方法。回溯法的基本思想是，對于給定問題，先定義解空間以及解空間的結構（典型的結構是樹或圖），然后解空間狀態樹中從根節點出發按照深度優先策略進行搜索。在搜索至任意結點時，總是先進行判斷，該結點是否包含問題的可行解，若包含問題的可行解就繼續進入該子樹搜索，否則，進行相應的剪枝。按照此方法逐層向上回溯，直到搜索完整個解空間，找到問題的最優解。

用回溯法求解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）確定解空間的結構：對于給定的n件物品，我們有序的考慮每個物品是否被選入背包中，以便枚舉出全部的狀況，從而可以用一顆高度為n的完全二叉樹（如圖一）來表示背包問題的解空間，從根節點到葉子的每一條路徑就對應解空間的一個解向量。

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

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

3.動態規劃

20世紀50年代，動態規劃算法首次由R.E.Bellman等提出，它是一種將多階段決策轉化為單階段決策求解問題的辦法。基本步驟是：

（1）尋找最優解的本質，構造它的結構特性；

（2）遞歸的去定義最優值；

（3）自底向上的去求最優值；

（4）依據算出來的最優值所得的信息去構造一個最優解。

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

動態規劃法求解0-1背包問題的一般步驟：

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

（2）初始化迭代條件：

（3）建立狀態轉移方程：根據0-1背包問題滿足最優子結構的性質，建立如下狀態轉移方程：

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

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

1.貪婪算法

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

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

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

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

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

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

2.模擬退火算法

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

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

（1）構建0-1背包問題的解空間，選擇算法迭代初始解。0-1背包問題的解空間，因為初始解對算法最終所得的結果影響不大，一般我們選擇（0，0，…，0）為初始解。

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

（3）針對新解的構造計算目標函數差（背包的價值差）和重量差。目標函數差為：

相應的背包的重量差：

（4）接受策略。該算法采用了擴充的蒙特卡洛準則：

其中為當前狀態下背包重量，為溫度控制參數。

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

3.遺傳算法

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

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

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

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

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

四、結語

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

參考文獻：

[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]藍雯飛，吳子瑩，楊波.背包問題的動態規劃改進算法[J].中南民族大學學報：自然科學版，2016，32（4）：101-105.

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

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

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

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

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

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

基金項目：2017年度廣西高校中青年教師基礎能力提升項目，項目編號：2017KY0712。