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

黃鴻華

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

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

黃鴻華

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

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

0-1背包；分枝限界

1．0-1背包問題

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

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

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

2．幾種解法的比較

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

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

2．2 回溯法

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

2．3 貪心算法

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

2．4 分枝限界法

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

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

3．解決0-1背包問題

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

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

4． C++實現(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的價值

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é)點

Typew wt=cw+w[i]；//檢查當前擴展結(jié)點的左兒子節(jié)點

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

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

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

}

up=Bound(i+1)；//檢查當前擴展結(jié)點的右兒子節(jié)點

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

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

HeapNode＜Typep，Typew＞N；//取下一個擴展節(jié)點

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++下對該算法進行測試，例如背包的最大容量c＝10，要放入的物品個數(shù)n＝5，重量w＝{2，6，2，5，4}，價值v＝{5，6，3，4，6}。

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

背包的總價值：15

背包的總重量：8

6．算法分析

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

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

[2]劉玉娟，王相海．0-1背包2問題的兩種擴展形式及其解法[J]．計算機應用研究，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

黃鴻華，女，福建連江人，本科，講師，研究方向：計算機技術。