基于Visual C++的0-1背包問題的分枝限界算法

黃鴻華

（福建船政交通職業(yè)學(xué)院，福建 福州 350007）

基于Visual C++的0-1背包問題的分枝限界算法

黃鴻華

（福建船政交通職業(yè)學(xué)院，福建 福州 350007）

0-1背包問題是經(jīng)典的NP問題。本文對(duì)0-1背包問題的分枝限界算法進(jìn)行了分析，用Visual C++實(shí)現(xiàn)該算法。

0-1背包；分枝限界

1．0-1背包問題

0-1背包問題是：把n個(gè)物品裝入一個(gè)背包，已知物品的總重量及其價(jià)值分別為wi＞0和pi＞0，背包的容量假定設(shè)為ci＞0，選擇哪些物品裝入背包可以使得在背包的容量約束限制之內(nèi)所裝物品的價(jià)值最大？

在選擇裝入背包的物品時(shí)，對(duì)每一種物品i只能選擇全部裝入背包或全部不裝入背包。因此該問題稱為0-1背包問題[1]。

給定c＞0，wi＞0，vi＞0，1≤i≤n，要求找出一個(gè)n元0-1向量(x1，x2，…，xn)，xi∈{0，1}，1≤i≤n，使得而且達(dá)到最大。0-1背包問題是一個(gè)特殊的整數(shù)規(guī)劃問題：

2．幾種解法的比較

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

動(dòng)態(tài)規(guī)劃可以把困難的多階段決策變換為一系列相互聯(lián)系比較容易的單階段問題。對(duì)于背包問題可以對(duì)子過程用枚舉法求解，而且約束條件越多，決策的搜索范圍越小，求解也越容易。

2．2 回溯法

回溯法需要為問題定義一個(gè)解空間，這個(gè)解空間必須至少包含問題的一個(gè)解（可能是最優(yōu)的）。遞歸回溯法算法思想非常簡單，并且能夠遍歷搜索空間，一定能夠找到背包問題的最優(yōu)解；但是背包問題的解空間將隨著物件數(shù)n的增大以2的n次方級(jí)增長，當(dāng)n大到一定程度上，要遍歷搜索空間需耗費(fèi)大量的時(shí)間和資源，因此當(dāng)物件數(shù)過多的時(shí)候，用回溯法解決背包問題將變得很困難。

2．3 貪心算法

使用貪心方法求解時(shí)計(jì)算的復(fù)雜度降低了很多。貪心算法是一種不要求最優(yōu)解，只希望得到較為滿意解的方法。貪心算法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，它不進(jìn)行遍歷回溯，不會(huì)考慮所有可能的情況，所以貪心算法大大節(jié)約了時(shí)間。但有時(shí)實(shí)際有解，而使用該算法則不能找到解。

2．4 分枝限界法

分枝界限是另一種系統(tǒng)地搜索解空間的方法，與回溯法擴(kuò)充E節(jié)點(diǎn)的方式不同，分枝限界法每個(gè)活節(jié)點(diǎn)變成E節(jié)點(diǎn)的機(jī)會(huì)有且僅有一次。一個(gè)節(jié)點(diǎn)一旦變?yōu)镋節(jié)點(diǎn)時(shí)，則生成一些新節(jié)點(diǎn)（即分枝），這些新節(jié)點(diǎn)只需從原節(jié)點(diǎn)移動(dòng)一步達(dá)到。在生成的新節(jié)點(diǎn)中，僅保留可能導(dǎo)出可行解的節(jié)點(diǎn)，加入到活節(jié)點(diǎn)表，其余的丟棄。然后從活節(jié)點(diǎn)表中選擇節(jié)點(diǎn)再進(jìn)行擴(kuò)充，直到找到最終解或活動(dòng)表為空。

下面介紹我的0-1背包問題的求解。

3．解決0-1背包問題

我們將分枝限界法與貪心算法相結(jié)合來解決0-1背包問題。使用分枝限界法搜索解空間，使用貪心算法來構(gòu)造上界函數(shù)，這個(gè)上界函數(shù)的作用在于確定分枝限界算法中活節(jié)點(diǎn)的優(yōu)先級(jí)。

分枝限界算法在搜索到達(dá)葉節(jié)點(diǎn)之前，也不知道最優(yōu)解是什么。在這里，我們根據(jù)上界函數(shù)的值確定優(yōu)先級(jí)，用一個(gè)最大堆來實(shí)現(xiàn)活節(jié)點(diǎn)的優(yōu)先隊(duì)列，這樣一旦有一個(gè)葉節(jié)點(diǎn)成為擴(kuò)展節(jié)點(diǎn)，就表明已經(jīng)找到了最優(yōu)解。

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

上界函數(shù)

template＜class Typew，class Typep＞

Typep Knap＜Typew，Typep＞：：Bound(int i) {

Typew cleft=c-cw；

Typep b=cp；

while(i＜=n&&w[i]＜=cleft){//n表示物品總數(shù)，cleft為剩余空間

cleft-=w[i]；//w[i]表示i所占空間

b+=p[i]；//p[i]表示i的價(jià)值

i++；

}

if(i＜=n)b+=p[i]/w[i]*cleft；//裝填剩余容量裝滿背包

return b；//b為上界函數(shù)

}

分枝限界搜索過程

template＜class Typew，class Typep＞

Typep Knap＜Typew，Typep＞：： MaxKnapsack()

{

H=new MaxHeap＜HeapNode＜Typep，Typew＞＞( MAXHEAP)；

bestx=new int[n+1]；

int i=1；

E=0；

cw=cp=0；

Typep bestp=0；

Typep up=Bound(1)；

while(i!=n+1){//非葉結(jié)點(diǎn)

Typew wt=cw+w[i]；//檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子節(jié)點(diǎn)

if(wt＜=c){//左兒子結(jié)點(diǎn)為可行節(jié)點(diǎn)

if(cp+p[i]＞bestp)bestp=cp+p[i]；

AddLiveNode(up，cp+p[i]，cw+w[i]，true，i+1)；

}

up=Bound(i+1)；//檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子節(jié)點(diǎn)

if(up＞=bestp)//右子樹可能含最優(yōu)解

AddLiveNode(up，cp，cw，false，i+1)；

HeapNode＜Typep，Typew＞N；//取下一個(gè)擴(kuò)展節(jié)點(diǎn)

H-＞Delete Max(N)；

E=N．ptr；

cw=N．weight；

cp=N．profit；

up=N．uprofit；

i=N．level；

}

for(int j=n；j＞0；j--){

bestx[j]=E-＞L Child；

E=E-＞parent；

}

return cp；

}

5．測試

在Visual C++下對(duì)該算法進(jìn)行測試，例如背包的最大容量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．算法分析

分枝限界法處理0-1背包問題的時(shí)間復(fù)雜度為O（2n），分枝限界算法將所有的結(jié)果形成一棵樹，但是在生成樹的過程中會(huì)剪斷一些不符合要求的枝來簡化算法的計(jì)算。分枝限界法需要算出一般背包問題，將一般背包問題作為一個(gè)限界值，根據(jù)自身的約束，實(shí)現(xiàn)剪枝的目的。分枝限界法容易求得最優(yōu)解，但是時(shí)間效率并不高。分枝限界法可以求出0-1背包的最優(yōu)解。但是因?yàn)樗且詷錇榛A(chǔ)的算法，因此它的空間開銷也較大。

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

[2]劉玉娟，王相海．0-1背包2問題的兩種擴(kuò)展形式及其解法[J]．計(jì)算機(jī)應(yīng)用研究，2006．

The Branch and BoundAlgorithm for 0-1 Knapsack Problem Based on Visual C++

Huang Honghua
(Fujian Chuanzheng Communications College,Fuzhou 350007,Fujian)

The 0-1knapsack problem is a classic NP problem.In this paper,the branch and bound algorithm for the 0-1 knapsack problem is analyzed,which is carried out with Visual C++.

0-1 knapsack;branch and bound

黃鴻華，女，福建連江人，本科，講師，研究方向：計(jì)算機(jī)技術(shù)。