0-1背包問題的算法決策分析

摘要：0-1背包問題是算法中的經典問題，現實中應用廣泛，它是屬于NP難問題。該文就0-1背包問題的三種策略：動態規劃、貪心算法、回溯和分支限界策略進行了分析。主要從三種策略的基本思想、求解方法包括主要關鍵代碼和算法時間復雜度幾個方面進行闡述，從而分析了當遇到具體問題，如何決策使用哪種策略解決問題。

關鍵詞：0-1背包問題;動態規劃;貪心算法;回溯法;分支限界法;時間復雜

中圖分類號：TP311.1

文獻標識碼：A

文章編號：1009-3044（2020）04-0259-02

收稿日期：2019-11-27

作者簡介：鄢莉（1978—），女，四川人，副教授，研究生，研究方向為計算機應用及算法。

Algorithmic Decision Analysis of 0-1 Knapsack Problem

YAN Li

（Panzhihua University，Panzhihua 6 17000，China

Abstract：In algorithm 0-1 knapsack problem is a classical problem.It is widely used in reality，which belongs to NP-hard problem.This paper discusses three strategies for 0-1 knapsack problem，as Dynamic Programming，Greedy Algorithm，Backtracking and Branch-and-Bound.Based on the basic ideas and solving methods，including the main key codes and the time complexity of the algorithm，this paper analyses how to use strategy to solve the specific problems.

complexity Key words：0-1 knapsack problem;dynamic programming;greedy algorithm;backtracking method;branch and bound method;time

背包問題（Knapsack problem）是由Merkel 和Hellman在1978年提出的，后來通過對其特點的研究，表明該問題是一個典型的NP-complete問題。它被廣泛應用在各種工業場合中，如資本預算、貨物裝載和存儲分配等問題，這些問題都可以轉化成0-1背包問題，因此研究0-1背包問題的求解方法具有非常重要的現實意義[1]。

0-1背包問題是一個經典算法，求解的方法非常多。從不同角度思考，就有不同的算法策略。常用的策略有：動態規劃法、貪心算法、回溯法和分支限界法。在實際應用中，我們應該如何決策選定哪一種策略，本文從此問題展開探索。

1 0-1背包問題的描述

文字描述：給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包容量是c。問：應如何選擇裝入背包中的物品，使得裝入背包中物品價值最大？對選入物品只有裝入和不裝入，不能裝，人多次，也不能只裝入物品的部分。

數學描述：給定c》0，w;》0，v;》0，1≤i≤n，要求找出一個

2 求絕對最優解的策略——動態規劃法

0-1背包問題要求解的是裝入背包中的物品價值最大。這是一個最優值，要解出絕對的最優解，動態規劃算法是一個很好的策略。

2.1 動態規劃法的基本思想

動態規劃法的核心思想就是：原問題的最優值由它的最小子問題的最優值逐步擴大規模，逐一求解，即由底向上的求問題的最優值;然后根據計算最優值的過程中保留一定的輔助數據，去構建問題的最優解。

由動態規劃法的核心思想可知，能由動態規劃法求解的問題必須包含兩個要素即：最優子結構性質和重疊子問題。最優子結構性質即是原問題的最優解包含了子問題的最優解。重疊子問題很好理解，即一個較小規模的子問題可以是很多比它規模較大問題的子問題，如果沒有這個性質，子問題是相互獨立的，我們可以采取更優的策略即分治策略求解。

2.2 0-1背包問題的動態規劃法求解

1）建立數學遞歸關系

子問題的最優值構建m（i，j）：是背包容量為j，可選擇物品為i，i+1，…n時背包的能裝入物品價值的最大值。當求解m（i，j）時，比它小的子問題m（i+1，j）已求解得到最優值。對于當前考慮的第i個物品，就有兩種情況：1）當前的背包容量j裝不下物品i，這時它的最優解就等同于m（i+1，j）;2）當前的j能裝下物品i，這時，我們就可以選擇裝入或者不裝入。不裝入等同于第一種情況;裝入那么背包當前價值就要在前一子問題（m（i+1，j-wi））的最優值上加上第i物品的價值。所以當前容量能裝下物品i，就會有兩個值，我們求的是當前背包價值最大，所以選擇兩個值中的較大者。

數學遞歸式可表達如下：

2）主要算法描述

int jMax=min（w[n]-1，c）;//c：背包當 前容量，n：物品的總個數

for（int j=0;j《=jMax;j++）m[n][i]=0;

for（int j=w[m];j《=c;j++）m[p]Ij]=v[n];

for（inti=n-1 ;i》 1;i—）{

jMax=min（w[i]-1，c）;

for（intj=0;j《=jMax;j++）m[i][i]=m[i+1][i];

for（int j=w[i];j《=c;j++）

m[i]lj]=max（m[i+1]i]，m[i+1][j-w[]+v[i]）;

if（m[]li]==m[i+1][j]）x[i]=0;/x[i]第i個物品裝還是不裝的解

elsex[i]=1;//0-不裝，1-裝

}

3）算法的時間復雜度分析

從上述主要算法描述可看出，動態規劃法的時間復雜度是O（nc）的計算時間。當背包的容量c很大時，算法的時間就較多。例如，當c》 2n時，算法的時間復雜度就變成了O（n2n）。如果當背包容量足夠大的時候，我們可以放棄動態規劃算法，而選擇貪心算法。

3 求近似最優解的策略——貪心算法

貪心算法每次所做的選擇，不是從整體最優進行考慮，而是僅考慮當前局部最優的選擇。當然，我們希望能得到最優解，這時，就必須要能證明此問題具有貪心選擇性質和最優子結構性質。雖然不是所有問題都可以用貪心法求得最優解，但是就很多問題，當規模足夠大時，由它計算出來的結果卻是最優解的很好近似解。

3.1 貪心算法的基本思想

根據所求問題，尋找一個貪心點，首先按照這個點對事物進行排序。然后一次線型時間掃描，依次選擇事件，直到條件不滿足，結束。

3.2 0-1背包問題的貪心算法求解

當背包和所裝物品的重量不在一個重量級時，如背包容量遠遠大于要選擇物品的重量，又或者把背包換成一輛卡車，這時貪心算法是絕好的方法。根據貪心法的基本思想，我們首先將物品按照其單位重量價值遞減排序，然后按照單位重量價值由高到低逐一的選擇物品并裝入，直到裝不下。

貪心算法求解0-1背包問題的主要代碼如下：

Sort（n，v，w）;//按單位重量價值排序

for（inti=1;i《=n;i++）x[i]=0;

floatc=M;//背包容量c

for（i=1;i《=n;i++）{ //逐一遍歷已排序的物品

If（w[i]》c）break;//如果當前物品裝不下了，就跳出循環

xi]=1;//裝入物品

c-=w[i];//求得當前背包的剩余容量

}

3.3 算法的時間復雜度分析

貪心算法求解問題時，排序時間復雜度是O（nlogn），貪心選擇的時間耗費是0（n），所以，貪心算法求解0-1背包問題的時間復雜度是O（nlogn）。

4 回溯法和分支限界法

回溯法有“通用的解題法”之稱，用它可以系統的搜索一個問題的所有解或任一解[1]?；厮莘ê头种藿绶ㄋ鼈冇泻芏嘞嗨浦?，都是將問題的解空間組織成一棵樹，然后遍歷樹。不同的是回溯法按照深度優先遍歷，分支限界則按照廣度優先的方式遍歷。

4.1 回溯法和分支限界法解題通常包含以下三個步驟：

（1）針對所給問題，定義問題的解空間;

（2）確定易于搜索的解空間結構;

（3）以深度（廣度）方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索[1]。

4.2 0-1背包問題的回溯法和分支限界法求解

回溯法和分支限界法求解0-1背包問題時，首先將解空間.組織成一滿二叉樹。對某一物品裝可構建成左子樹，解的取值為1，不裝可構建成右子樹，解的取值為0。所以解空間樹是深度為n的滿二叉樹。具體求解算法以回溯法為例。

回溯法求解0-1背包問題的主要代碼如下：

Backtrack （inti）//i：當前遍歷樹的層數

{ if（i》n）{ //當前節點是葉子節點，得到一個當前最優值

bestp=cp;

return ;}

if（cw+w[i]《=c）{ //背包當前容量能裝入物品i

cw +=w[i];//cw：當前已裝入物品的重量

cp+=p間];//ep：當前已裝入物品的價值

Backtrack（i+1）;//深入遞歸訪問左子樹

CW-=w[i];

cp-=p問;}

If（Bound （i+1）》bestp）//如果右子樹中可能存在最優解

Backtrack（i+1）;//則深入遞歸訪問右子樹

}

4.3 算法的時間復雜度分析

遍歷二叉樹時，最壞情況是每一個分支節點和葉子節點都要訪問，物品為n時，二叉樹的深度為n，節點數共2n-1個。所以最壞的情況算法的時間復雜度是0（2n）。實際上，因為在遍歷樹的時候，會用到剪枝函數，即減去不滿足條件的和不能得到最優解的子樹，從而大大縮小了訪問節點的個數。有時，給出的特定實例時，回溯法和分支限界法的具體運算時間會小于動態規劃算法。

5 如何決策0-1背包問題選擇何種策略

“條條大道通羅馬”，0-1背包問題常用求解方法就有上訴四種策略，每一種策略都各自有優缺點，怎么決策呢？總的來說當我們要求問題所有解時，可選擇回溯法或者分支限界法;要求問題絕對最優值時可選擇動態規劃法，當然也可以用回溯法和分支限界法;如果背包容量遠遠高于物品重量時，我們可以用貪心法求解接近最優解的近似解。當我們面對不同問題時，就要具體問題具體分析，找到既能滿足條件又能提高效率的最佳方案。

參考文獻：

[1]王曉東.計算機算法設計與分析[M].北京：電子工業出版社，2007.

[2]王文東，武海妮.求解0-1背包問題的算法分析[J].信息與電腦：理論版，2018（9）：68-70.

[3]劉朝霞.求解0-1背包問題的兩種算法設計[J].陰山學刊：自然科學版，2014，28（3）：5-8.

[4]劉文強，周波，馬海峰，等.算法分析與設計課程中0-1背包問題的探討[J].高師理科學刊，2018，38（6）：82-85.

[通聯編輯：代影]