基于C#的0—1背包问题的回溯算法

摘要：0-1背包问题是经典的NP问题。该文对0-1背包问题的回溯算法进行了分析，用C#实现该算法。

关键词：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]

在实际进行装包操作时，规定每种物品只能载入一次，而且每种物品只能执行载入或者不载入操作，则把该问题叫做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 回溯法

回溯法就是为问题声明一个解集合，这个集合存在一个可能是最优的解。递归回溯法算法思想非常简单，能够对搜索空间进行遍历，必然可以找到背包问题的最优解，缺点是背包问题解集合将随着物品数量n的变大以2的几何级数增长，当n大到一定程度上，要遍历搜索空间需耗费大量的时间和资源，因此当物件数过多的时候，就很难依靠回溯法来求解。

2.2 动态规划算法

动态规划指的是把复杂的多阶段问题分解成相对简单的单阶段问题。对于背包问题可以用穷举法对子过程进行求解，并且决策的搜索范围会因为条件的增多而变小，这样求解也更简单。

2.3 贪心算法

贪心方法的使用可以降低求解时计算的复杂度。贪心算法不是片面追求最优解，因此不理会所有情况，所以不象回溯法那样进行遍历，一般情况下，就以目前情形最为最优的 。

2.4 分枝限界法

分枝界限与回溯法拓展E节点的方法不一样，为另一种全面地遍历解集合的方法，按这种算法，任何活节点只可能一次改变为E节点。当某节点一旦改变成E节点，会同时产生一些新节点（也就是分枝），新产生的节点是从原节点跳转一步实现的。产生的新节点里，只留下有希望得到行得通解的节点，添加到活节点表，剩下的抛弃。接着从活节点表里挑选节点再进行拓展，最后就可以得到最后解，并且活动表清空了。

3 回溯算法

回溯法为一种在问题的结果空间树T上查询问题答案的算法。回溯法在全部解的结果空间树中，依照深度优先的方法，从根节点开始查询结果空间树。算法搜索至结果空间树的每个节点时，先看看是不是不存在结果。假设确定不存在，那么忽略该子树，继续向其父节点进行回溯，反之，使用该子树，仍然以深度优先的方法进行查询。当回溯法来寻找结果时，一定要回溯到顶点，并且，顶点节点的全部子树都查找完才停止。这样，按照深度优先的策略全面查询问题的结果的算法叫做回溯法，可以解决组合数很多的情况。

假设选取回溯法来解决0-1背包问题，可以用在采取子集数表示0-1背包问题的结果集合。执行查找结果空间树时，如果左节点是能用的节点，查找行为转到它的左子树。那什么时候进入右边的子树查找呢？那就是只有在右边子树里有希望找找最优解的时候，才转到右边子树查询。要不然就把右子树删除。此过程由上界函数来完成。假定r是现在还没有使用的剩下物品总价值，cp是现在已有的价值，yestp为目前最优的价值。那么在cp+r<=yestp时，允许删除右边子树。寻找右边子树里上届解的一种更先进的方法是把剩下物品按照它的价值/单位重量进行排定顺序，顺序载入物品，直到载不进去时，再载入这物品的局部实现载满背包。这样，价值等于右边子树的上界解。

要使上界函数的计算更方便，不妨让物品按照重量价值进行降序排序。执行的时候，由函数fanwei来寻找最新节点的上界。只有在要进入右边子树时，才计算上界函数fanwei，由此判断是不是要将右子树删除。转到左子树时不要查找上界，这时候上界和基类节点的上界是一样的。

4 算法实现

int n；//物品数量

double c；//背包容量

double[] v=new double[100]；//各个物品的价值

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

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

double cp = 0.0；//当前背包中物品价值

double yestp = 0.0；//当前最优价值

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

//回溯函數

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）//符合条件搜索右子数

b_track（i+1）； }

//计算上界函数

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（"请输入物品的数量和容量："）；

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，要放入的物品个数n=5，重量w={2，6，2，5，4}，价值v={5，6，3，4，6}。

输出结果： 1 0 1 0 1

背包的总价值：15

背包的总重量：8

6 算法分析

因为寻找上界函数fanwei需要O（n）时间，当复杂度最坏时有O（2n）个右边派生节点需要求解上界函数，因此，用回溯法来计算0-1背包问题的时间复杂度是O（n2n）。回溯法能得到0-1背包的最优解。另一方面回溯法是以树当成基础的算法，所以其空间开销很多。

参考文献：

[1] 王晓东. 计算机算法设计与分析[M].北京： 电子工业出版社，2004.

[2] 贺毅朝， 田海燕. 基于动态规划法求解动态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背包问题的动态规划算法[J].电脑知识与技术，2007（9）.