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

關(guān)鍵詞：0-1背包問題;動(dòng)態(tài)規(guī)劃;貪心算法;回溯法;分支限界法;時(shí)間復(fù)雜

中圖分類號(hào)：TP311.1

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）04-0259-02

收稿日期：2019-11-27

作者簡(jiǎn)介：鄢莉（1978—），女，四川人，副教授，研究生，研究方向?yàn)橛?jì)算機(jī)應(yīng)用及算法。

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年提出的，后來通過對(duì)其特點(diǎn)的研究，表明該問題是一個(gè)典型的NP-complete問題。它被廣泛應(yīng)用在各種工業(yè)場(chǎng)合中，如資本預(yù)算、貨物裝載和存儲(chǔ)分配等問題，這些問題都可以轉(zhuǎn)化成0-1背包問題，因此研究0-1背包問題的求解方法具有非常重要的現(xiàn)實(shí)意義[1]。

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

1 0-1背包問題的描述

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

數(shù)學(xué)描述：給定c》0，w;》0，v;》0，1≤i≤n，要求找出一個(gè)

2 求絕對(duì)最優(yōu)解的策略——?jiǎng)討B(tài)規(guī)劃法

0-1背包問題要求解的是裝入背包中的物品價(jià)值最大。這是一個(gè)最優(yōu)值，要解出絕對(duì)的最優(yōu)解，動(dòng)態(tài)規(guī)劃算法是一個(gè)很好的策略。

2.1 動(dòng)態(tài)規(guī)劃法的基本思想

動(dòng)態(tài)規(guī)劃法的核心思想就是：原問題的最優(yōu)值由它的最小子問題的最優(yōu)值逐步擴(kuò)大規(guī)模，逐一求解，即由底向上的求問題的最優(yōu)值;然后根據(jù)計(jì)算最優(yōu)值的過程中保留一定的輔助數(shù)據(jù)，去構(gòu)建問題的最優(yōu)解。

由動(dòng)態(tài)規(guī)劃法的核心思想可知，能由動(dòng)態(tài)規(guī)劃法求解的問題必須包含兩個(gè)要素即：最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題。最優(yōu)子結(jié)構(gòu)性質(zhì)即是原問題的最優(yōu)解包含了子問題的最優(yōu)解。重疊子問題很好理解，即一個(gè)較小規(guī)模的子問題可以是很多比它規(guī)模較大問題的子問題，如果沒有這個(gè)性質(zhì)，子問題是相互獨(dú)立的，我們可以采取更優(yōu)的策略即分治策略求解。

2.2 0-1背包問題的動(dòng)態(tài)規(guī)劃法求解

1）建立數(shù)學(xué)遞歸關(guān)系

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

數(shù)學(xué)遞歸式可表達(dá)如下：

2）主要算法描述

int jMax=min（w[n]-1，c）;//c：背包當(dāng) 前容量，n：物品的總個(gè)數(shù)

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個(gè)物品裝還是不裝的解

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

}

3）算法的時(shí)間復(fù)雜度分析

從上述主要算法描述可看出，動(dòng)態(tài)規(guī)劃法的時(shí)間復(fù)雜度是O（nc）的計(jì)算時(shí)間。當(dāng)背包的容量c很大時(shí)，算法的時(shí)間就較多。例如，當(dāng)c》 2n時(shí)，算法的時(shí)間復(fù)雜度就變成了O（n2n）。如果當(dāng)背包容量足夠大的時(shí)候，我們可以放棄動(dòng)態(tài)規(guī)劃算法，而選擇貪心算法。

3 求近似最優(yōu)解的策略——貪心算法

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

3.1 貪心算法的基本思想

根據(jù)所求問題，尋找一個(gè)貪心點(diǎn)，首先按照這個(gè)點(diǎn)對(duì)事物進(jìn)行排序。然后一次線型時(shí)間掃描，依次選擇事件，直到條件不滿足，結(jié)束。

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

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

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

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

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

floatc=M;//背包容量c

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

If（w[i]》c）break;//如果當(dāng)前物品裝不下了，就跳出循環(huán)

xi]=1;//裝入物品

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

}

3.3 算法的時(shí)間復(fù)雜度分析

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

4 回溯法和分支限界法

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

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

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

（2）確定易于搜索的解空間結(jié)構(gòu);

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

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

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

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

Backtrack （inti）//i：當(dāng)前遍歷樹的層數(shù)

{ if（i》n）{ //當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)，得到一個(gè)當(dāng)前最優(yōu)值

bestp=cp;

return ;}

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

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

cp+=p間];//ep：當(dāng)前已裝入物品的價(jià)值

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

CW-=w[i];

cp-=p問;}

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

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

}

4.3 算法的時(shí)間復(fù)雜度分析

遍歷二叉樹時(shí)，最壞情況是每一個(gè)分支節(jié)點(diǎn)和葉子節(jié)點(diǎn)都要訪問，物品為n時(shí)，二叉樹的深度為n，節(jié)點(diǎn)數(shù)共2n-1個(gè)。所以最壞的情況算法的時(shí)間復(fù)雜度是0（2n）。實(shí)際上，因?yàn)樵诒闅v樹的時(shí)候，會(huì)用到剪枝函數(shù)，即減去不滿足條件的和不能得到最優(yōu)解的子樹，從而大大縮小了訪問節(jié)點(diǎn)的個(gè)數(shù)。有時(shí)，給出的特定實(shí)例時(shí)，回溯法和分支限界法的具體運(yùn)算時(shí)間會(huì)小于動(dòng)態(tài)規(guī)劃算法。

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

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

參考文獻(xiàn)：

[1]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2007.

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

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

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

[通聯(lián)編輯：代影]