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

黄鸿华

（福建船政交通职业学院，福建 福州 350007）

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

黄鸿华

（福建船政交通职业学院，福建 福州 350007）

0-1背包问题是经典的NP问题。本文对0-1背包问题的分枝限界算法进行了分析，用Visual C++实现该算法。

0-1背包；分枝限界

1．0-1背包问题

0-1背包问题是：把n个物品装入一个背包，已知物品的总重量及其价值分别为wi＞0和pi＞0，背包的容量假定设为ci＞0，选择哪些物品装入背包可以使得在背包的容量约束限制之内所装物品的价值最大？

在选择装入背包的物品时，对每一种物品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背包问题是一个特殊的整数规划问题：

2．几种解法的比较

2．1 动态规划算法

动态规划可以把困难的多阶段决策变换为一系列相互联系比较容易的单阶段问题。对于背包问题可以对子过程用枚举法求解，而且约束条件越多，决策的搜索范围越小，求解也越容易。

2．2 回溯法

回溯法需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解（可能是最优的）。递归回溯法算法思想非常简单，并且能够遍历搜索空间，一定能够找到背包问题的最优解；但是背包问题的解空间将随着物件数n的增大以2的n次方级增长，当n大到一定程度上，要遍历搜索空间需耗费大量的时间和资源，因此当物件数过多的时候，用回溯法解决背包问题将变得很困难。

2．3 贪心算法

使用贪心方法求解时计算的复杂度降低了很多。贪心算法是一种不要求最优解，只希望得到较为满意解的方法。贪心算法常以当前情况为基础作最优选择，它不进行遍历回溯，不会考虑所有可能的情况，所以贪心算法大大节约了时间。但有时实际有解，而使用该算法则不能找到解。

2．4 分枝限界法

分枝界限是另一种系统地搜索解空间的方法，与回溯法扩充E节点的方式不同，分枝限界法每个活节点变成E节点的机会有且仅有一次。一个节点一旦变为E节点时，则生成一些新节点（即分枝），这些新节点只需从原节点移动一步达到。在生成的新节点中，仅保留可能导出可行解的节点，加入到活节点表，其余的丢弃。然后从活节点表中选择节点再进行扩充，直到找到最终解或活动表为空。

下面介绍我的0-1背包问题的求解。

3．解决0-1背包问题

我们将分枝限界法与贪心算法相结合来解决0-1背包问题。使用分枝限界法搜索解空间，使用贪心算法来构造上界函数，这个上界函数的作用在于确定分枝限界算法中活节点的优先级。

分枝限界算法在搜索到达叶节点之前，也不知道最优解是什么。在这里，我们根据上界函数的值确定优先级，用一个最大堆来实现活节点的优先队列，这样一旦有一个叶节点成为扩展节点，就表明已经找到了最优解。

4． C++实现算法

上界函数

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表示物品总数，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为上界函数

}

分枝限界搜索过程

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){//非叶结点

Typew wt=cw+w[i]；//检查当前扩展结点的左儿子节点

if(wt＜=c){//左儿子结点为可行节点

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

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

}

up=Bound(i+1)；//检查当前扩展结点的右儿子节点

if(up＞=bestp)//右子树可能含最优解

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

HeapNode＜Typep，Typew＞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++下对该算法进行测试，例如背包的最大容量c＝10，要放入的物品个数n＝5，重量w＝{2，6，2，5，4}，价值v＝{5，6，3，4，6}。

输出结果：1 0 1 0 1

背包的总价值：15

背包的总重量：8

6．算法分析

分枝限界法处理0-1背包问题的时间复杂度为O（2n），分枝限界算法将所有的结果形成一棵树，但是在生成树的过程中会剪断一些不符合要求的枝来简化算法的计算。分枝限界法需要算出一般背包问题，将一般背包问题作为一个限界值，根据自身的约束，实现剪枝的目的。分枝限界法容易求得最优解，但是时间效率并不高。分枝限界法可以求出0-1背包的最优解。但是因为它是以树为基础的算法，因此它的空间开销也较大。

[1]王晓东．计算机算法设计与分析[M]．北京：电子工业出版社，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

黄鸿华，女，福建连江人，本科，讲师，研究方向：计算机技术。