基于C#的0—1背包問(wèn)題的回溯算法

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

關(guān)鍵詞：0-1背包；回溯

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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背包問(wèn)題的思想：如果n個(gè)物品的重量和價(jià)值分別為[wi>0]和[pi>0]，背包的大小設(shè)置成[ci>0]，應(yīng)該怎樣往背包中放置物品可以達(dá)到最大值或者最佳裝載方式？[5]

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

給定[wi]>0，c>0，[vi]>0，[1≤i≤n]，尋求一個(gè)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 回溯法

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

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

動(dòng)態(tài)規(guī)劃指的是把復(fù)雜的多階段問(wèn)題分解成相對(duì)簡(jiǎn)單的單階段問(wèn)題。對(duì)于背包問(wèn)題可以用窮舉法對(duì)子過(guò)程進(jìn)行求解，并且決策的搜索范圍會(huì)因?yàn)闂l件的增多而變小，這樣求解也更簡(jiǎn)單。

2.3 貪心算法

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

2.4 分枝限界法

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

3 回溯算法

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

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

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

4 算法實(shí)現(xiàn)

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

double c；//背包容量

double[] v=new double[100]；//各個(gè)物品的價(jià)值

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

double cw = 0.0；//當(dāng)前背包重量

double cp = 0.0；//當(dāng)前背包中物品價(jià)值

double yestp = 0.0；//當(dāng)前最優(yōu)價(jià)值

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

int[] order=new int[100]；//物品編號(hào)

int[] put= new int[100]；//設(shè)置是否裝入

//按單位價(jià)值排序

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）； }

//計(jì)算上界函數(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（"請(qǐng)輸入物品的數(shù)量和容量："）；

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

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

Console.WriteLine （"請(qǐng)輸入物品的重量和價(jià)值："）；

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

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

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

Console.WriteLine （"價(jià)值是："）；

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

order[i]=i； }

knapsack（）；

b_track（1）；

Console.WriteLine （"最有價(jià)值為："+yestp）；

Console.WriteLine （"需要裝入的物品編號(hào)是："）；

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

{if（put[i]==1）

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

return 0； }

5 測(cè)試

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

輸出結(jié)果： 1 0 1 0 1

背包的總價(jià)值：15

背包的總重量：8

6 算法分析

因?yàn)閷ふ疑辖绾瘮?shù)fanwei需要O（n）時(shí)間，當(dāng)復(fù)雜度最壞時(shí)有O（2n）個(gè)右邊派生節(jié)點(diǎn)需要求解上界函數(shù)，因此，用回溯法來(lái)計(jì)算0-1背包問(wèn)題的時(shí)間復(fù)雜度是O（n2n）。回溯法能得到0-1背包的最優(yōu)解。另一方面回溯法是以樹(shù)當(dāng)成基礎(chǔ)的算法，所以其空間開(kāi)銷很多。

參考文獻(xiàn)：

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

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

[3] 徐穎. 回溯法在0-1背包問(wèn)題中的應(yīng)用[J].軟件導(dǎo)刊，2008（12）.

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

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