背包问题的算法研究与实现本科毕业论文 精品

}

template Typep Knap::Bound(int i) {//计算上界

Typew cleft=c-cw; //剩余容量 Typep b=cp;

//以物品单位重量价值递减序装入物品 while (i<=n&&w[i]<=cleft){ cleft-=w[i]; b+=p[i]; i++; } //装满背包

if(i<=n)b+=p[i]* cleft/w[i]; return b; }

class Object {

friend int Knapsack(int*,int *,int,int); public;

int operator<=(Object a) const {return(d>=a.d);} private: int ID; float d; };

template

Typep Knapsack(Typep p[], Typep w[],Typew c,int n) {

//为Knap::Backtrack 初始化 Typew W=0; Typep P=0;

Object*Q=new Object[n];

10

for(int i=1;i<=n;i++){ Q[i-1].ID=i;

Q[i-1].d=1.0*p[i]/w[i]; p+=p[i]; w+=w[i]; }

if(w<=c)return P;//装入所有物品

//依物品单位重量价值排序

sort(Q,n);

KnapK; K.p=new Typep[n+1]; K.w=new Typew[n+1]; for (int i=1;i<=n;i++){ K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; //回搠搜索 K.Backtrack(1); delete[]Q; delete[]K.w; delete[]K.p; reture K,bestp; }[1] ③ 算法效率

由于计算上界函数需要O(n)时间，在最坏情况下有O(2n)个右孩子结点需要上界函数，故计算0-1背包问题的回溯算法所需的计算时间复杂度为O(n2n)。

11

对回溯法的改进主要是对判断是否移动右子树上，一种更有效的方法是按效益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放人背包的对象时，就使用它的一部分。

回溯算法的运行时间取决于它在搜索过程中所生成的结点数,而限界函数可以大量减少所生成的结点个数,省去许多无谓的搜索, 使得搜索速度更快 ,其调用限界函数计算上界需花费O(n)时间 ,最坏情况下有O(2n)个结点需调用限界函数 ,需花费O(n)时间,所以该算法的时间复杂度为O(n2n)[12]。 回溯法的另一个重要特性就是在搜索执行的同时产生解空间 在搜索期间的任何时刻 仅保留从开始结点到当前可扩展结点的路径其空间需求为O(从开始结点起最长路径的长度),所以 ,此处该算法的空间复杂度为O(n),回溯法是算法设计的基本方法之一 ,它适用于解一些涉及到寻找一组解的问题或者求满足某些约束条件的最优解的问题,且适用于求解组合数量较大的问题。

2.3 0-1背包问题在分枝-限界法中的实现

2.3.1分枝-限界法的基本原理与分析

分枝限界发是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-结点(expansion node)的扩充方式。每个活结点有且仅有一次会变成E-结点。当一个结点变为E-结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出(最优)可行解的结点，其余结点加人活结点表，然后从表中选择一个结点作为下一个E结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充才结束。 有两种常用的方法可用来选择下一个E-结点:

① 先进先出(FIFO)即从活结点表中取出结点的顺序与加人结点的顺序相同，因此活结点表的性质与队列相同。

② 最小耗费或最大收益法在这种模式中，每个结点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活结点表可以最小堆来建立，下一个E-结点就是具有最小耗费的活结点，如果希望搜索一个具有最大收益的解， 则可用最大堆来构造活结点表，下一个E-结点是具有最大收益的活结点[15]。

12

2.3.2 0-1背包问题的实现

工作在解空间树上的FIFO分枝定界方法非常类似于从根结点出发的宽度优先搜索。它们的主要区别时在FIFO分枝定界中不可行的结点不会被搜索。

0-1背包问题的最大收益分枝定界算法可以使用定界函数来计算活结点的收益上限upprofit，使得以活结点为根的子树中的任一结点的收益值都不可能超过upprofit，活结点的最大堆使用upprofit作为关键值域。在子集树中执行最大收益分枝定界搜索的函数首先初始化活结点的最大堆，并使用一个数组bestx来记录最优解。由于需要不断地利用收益密度来排序，物品的索引值会随之变化，因此必须将函数所生成的结果映射回初始时的物品索引。函数中的循环首先检验E-结点左孩子的可行性，如它是可行的，则将它加入子集树及活结点队列(即最大堆)，仅当结点右子树的定界值指明可能找到一个最优解时才将右孩子加入子集树和队列中。

则主要算法描述为： class Object{

friend int Knapsack(int *,int *,int,int,int *); public:

int operator<=(Object a) const {return (d>=a.d);} private: int ID;

float d;//单位重量价值 };

template class Knap; class bbnode{

friend Knap;

friend int Knapsack(int *,int *,int,int,int *); private:

bbnode *parent; //指向父结点的指针

13