摘要：0-1背包問題是經(jīng)典的NP問題。該文對0-1背包問題的回溯算法進行了分析，用C#實現(xiàn)該算法。

關鍵詞：0-1背包；回溯

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）36-0076-02

The B_tracking Algorithm of 0-1 Knapsack Problem Based on C#

CHEN Zi-li

（Fujian Chuanzheng Communications College， Fuzhou 350007， China）

Abstract： The 0-1knapsack problem is a classic NP problem. In this paper， the 0-1 knapsack problem and its algorithm is analyzed， the algorithms is based on B_tracking algorithm. And carry out the algorithms in the C#.

Key words： 0-1 Knapsack； b_tracking algorithm

1 0-1背包思想

0-1背包問題的思想：如果n個物品的重量和價值分別為[wi>0]和[pi>0]，背包的大小設置成[ci>0]，應該怎樣往背包中放置物品可以達到最大值或者最佳裝載方式？[5]

在實際進行裝包操作時，規(guī)定每種物品只能載入一次，而且每種物品只能執(zhí)行載入或者不載入操作，則把該問題叫做0-1背包問題。

給定[wi]>0，c>0，[vi]>0，[1≤i≤n]，尋求一個n元0-1向量[（x1，x2，...，xn），xi∈{0，1}，][1≤i≤n]，使得[i=1nwixi≤c]，而且[i=1nvixi]是最值。

[maxi=1nvixi] [i=1nwixi≤cxi∈{0.1}，1≤i≤n]

2 幾種解法的比較

2.1 回溯法

回溯法就是為問題聲明一個解集合，這個集合存在一個可能是最優(yōu)的解。遞歸回溯法算法思想非常簡單，能夠?qū)λ阉骺臻g進行遍歷，必然可以找到背包問題的最優(yōu)解，缺點是背包問題解集合將隨著物品數(shù)量n的變大以2的幾何級數(shù)增長，當n大到一定程度上，要遍歷搜索空間需耗費大量的時間和資源，因此當物件數(shù)過多的時候，就很難依靠回溯法來求解。

2.2 動態(tài)規(guī)劃算法

動態(tài)規(guī)劃指的是把復雜的多階段問題分解成相對簡單的單階段問題。對于背包問題可以用窮舉法對子過程進行求解，并且決策的搜索范圍會因為條件的增多而變小，這樣求解也更簡單。

2.3 貪心算法

貪心方法的使用可以降低求解時計算的復雜度。貪心算法不是片面追求最優(yōu)解，因此不理會所有情況，所以不象回溯法那樣進行遍歷，一般情況下，就以目前情形最為最優(yōu)的 。

2.4 分枝限界法

分枝界限與回溯法拓展E節(jié)點的方法不一樣，為另一種全面地遍歷解集合的方法，按這種算法，任何活節(jié)點只可能一次改變?yōu)镋節(jié)點。當某節(jié)點一旦改變成E節(jié)點，會同時產(chǎn)生一些新節(jié)點（也就是分枝），新產(chǎn)生的節(jié)點是從原節(jié)點跳轉(zhuǎn)一步實現(xiàn)的。產(chǎn)生的新節(jié)點里，只留下有希望得到行得通解的節(jié)點，添加到活節(jié)點表，剩下的拋棄。接著從活節(jié)點表里挑選節(jié)點再進行拓展，最后就可以得到最后解，并且活動表清空了。

3 回溯算法

回溯法為一種在問題的結果空間樹T上查詢問題答案的算法。回溯法在全部解的結果空間樹中，依照深度優(yōu)先的方法，從根節(jié)點開始查詢結果空間樹。算法搜索至結果空間樹的每個節(jié)點時，先看看是不是不存在結果。假設確定不存在，那么忽略該子樹，繼續(xù)向其父節(jié)點進行回溯，反之，使用該子樹，仍然以深度優(yōu)先的方法進行查詢。當回溯法來尋找結果時，一定要回溯到頂點，并且，頂點節(jié)點的全部子樹都查找完才停止。這樣，按照深度優(yōu)先的策略全面查詢問題的結果的算法叫做回溯法，可以解決組合數(shù)很多的情況。

假設選取回溯法來解決0-1背包問題，可以用在采取子集數(shù)表示0-1背包問題的結果集合。執(zhí)行查找結果空間樹時，如果左節(jié)點是能用的節(jié)點，查找行為轉(zhuǎn)到它的左子樹。那什么時候進入右邊的子樹查找呢？那就是只有在右邊子樹里有希望找找最優(yōu)解的時候，才轉(zhuǎn)到右邊子樹查詢。要不然就把右子樹刪除。此過程由上界函數(shù)來完成。假定r是現(xiàn)在還沒有使用的剩下物品總價值，cp是現(xiàn)在已有的價值，yestp為目前最優(yōu)的價值。那么在cp+r<=yestp時，允許刪除右邊子樹。尋找右邊子樹里上屆解的一種更先進的方法是把剩下物品按照它的價值/單位重量進行排定順序，順序載入物品，直到載不進去時，再載入這物品的局部實現(xiàn)載滿背包。這樣，價值等于右邊子樹的上界解。

要使上界函數(shù)的計算更方便，不妨讓物品按照重量價值進行降序排序。執(zhí)行的時候，由函數(shù)fanwei來尋找最新節(jié)點的上界。只有在要進入右邊子樹時，才計算上界函數(shù)fanwei，由此判斷是不是要將右子樹刪除。轉(zhuǎn)到左子樹時不要查找上界，這時候上界和基類節(jié)點的上界是一樣的。

4 算法實現(xiàn)

int n；//物品數(shù)量

double c；//背包容量

double[] v=new double[100]；//各個物品的價值

double[] w=new double[100]；//各個物品的重量

double cw = 0.0；//當前背包重量

double cp = 0.0；//當前背包中物品價值

double yestp = 0.0；//當前最優(yōu)價值

double[] perp=new double[100]；//單位物品價值排序后

int[] order=new int[100]；//物品編號

int[] put= new int[100]；//設置是否裝入

//按單位價值排序

public void knapsack（）

{ int i，j；

int temporder = 0；

double temp = 0.0；

for（i=1；i<=n；i++）

perp[i]=v[i]/w[i]；

for（i=1；i<=n-1；i++）

{ for（j=i+1；j<=n；j++）

if（perp[i]

{temp = perp[i]；

perp[i]=perp[i]；

perp[j]=temp；

temporder=order[i]；

order[i]=order[j]；

order[j]=temporder；

temp = v[i]；

v[i]=v[j]；

v[j]=temp；

temp=w[i]；

w[i]=w[j]；

w[j]=temp； }}}

//回溯函數(shù)

public void b_track（int i）

{ double fanwei（int i）；

if（i>n）

{ yestp = cp；

return； }

if（cw+w[i]<=c）

{ cw=cw+w[i]；

cp= cp+v[i]；

put[i]=1；

b_track（i+1）；

cw=cw-w[i]；

cp=cp-v[i]； }

if（fanwei（i+1）>yestp）//符合條件搜索右子數(shù)

b_track（i+1）； }

//計算上界函數(shù)

public double fanwei（int i）

{double leftw= c-cw；

double b = cp；

while（i<=n && w[i]<=leftw）

{ leftw-=w[i]；

b+=v[i]；

i++；}

if（i<=n）

b+=v[i]/w[i]*leftw；

return b； }

static void Main（string[] args）

{int i；

Console.WriteLine（"請輸入物品的數(shù)量和容量："）；

n=Convert.ToInt32（Console.ReadLine（））；

c= Convert.ToDouble（Console.ReadLine（））；

Console.WriteLine （"請輸入物品的重量和價值："）；

for（i=1；i<=n；i++）

{ Console.WriteLine （"第{0}個物品的重量："，i）；

w[i]=Convert.ToDouble（Console.ReadLine（））；

Console.WriteLine （"價值是："）；

v[i]=Convert.ToDouble（Console.ReadLine（））；

order[i]=i； }

knapsack（）；

b_track（1）；

Console.WriteLine （"最有價值為："+yestp）；

Console.WriteLine （"需要裝入的物品編號是："）；

for（i=1；i<=n；i++）

{if（put[i]==1）

printf（"%d "，order[i]）； }

return 0； }

5 測試

在VS2010下對該算法進行測試 ，例如背包的最大容量c=10，要放入的物品個數(shù)n=5，重量w={2，6，2，5，4}，價值v={5，6，3，4，6}。

輸出結果： 1 0 1 0 1

背包的總價值：15

背包的總重量：8

6 算法分析

因為尋找上界函數(shù)fanwei需要O（n）時間，當復雜度最壞時有O（2n）個右邊派生節(jié)點需要求解上界函數(shù)，因此，用回溯法來計算0-1背包問題的時間復雜度是O（n2n）?；厮莘艿玫?-1背包的最優(yōu)解。另一方面回溯法是以樹當成基礎的算法，所以其空間開銷很多。

參考文獻：

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

[2] 賀毅朝， 田海燕. 基于動態(tài)規(guī)劃法求解動態(tài)0-1背包問題[J].計算機科學，2012 ，39（7）：237-241..

[3] 徐穎. 回溯法在0-1背包問題中的應用[J].軟件導刊，2008（12）.

[4] 黃鴻華. 基于Visual C++的0-1背包問題的分枝限界算法[J].電腦與電信，2014（10）.

[5] 陳自力， 潘燕燕. 基于Visual C++的0-1背包問題的動態(tài)規(guī)劃算法[J].電腦知識與技術，2007（9）.