回溯法和分支限界法解决01背包题精.doc

《回溯法和分支限界法解决01背包题精.doc》由会员分享，可在线阅读，更多相关《回溯法和分支限界法解决01背包题精.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、0-1背包问题计科1班 朱润华 2019040732方法1：回溯法一、回溯法描述：用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个（最优）解。对于0-1背包问题，解空间由长度为n的0-1向量组成。该解空间包含对变量的所有0-1赋值。例如n=3时，解空间为： （0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1） 然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物

2、品的总价值最大?形式化描述：给定c 0, wi 0, vi 0 , 1in.要求找一n元向量(x1,x2,xn,), xi0,1, ? wi xic,且 vi xi达最大.即一个特殊的整数规划问题。二、回溯法步骤思想描述：0-1背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当cp+r=bestp时，可剪去右子树。计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，

3、然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。例如：对于0-1背包问题的一个实例，n=4,c=7,p=9,10,7,4,w=3,5,2,1。这4个物品的单位重量价值分别为3,2,3,5,4。以物品单位重量价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。由此得一个解为1,0.2,1,1，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。 在实现时，由Bound计算当前节点处的上界。类Knap的数据成员记录解空间树中的节点信息，以减少参数传递调用所需要的栈空

4、间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。三、回溯法实现代码：#include stdafx.h#include using namespace std;templateclass Knaptemplatefriend Typep Knapsack(Typep ,Typew ,Typew,int);private:Typep Bound(int i);void Backtrack(int i);Typew c; /背包容量int n; /物品数Typew *w; /物品重量数组Typ

5、ep *p; /物品价值数组Typew cw; /当前重量Typep cp; /当前价值Typep bestp;/当前最后价值templateTypep Knapsack(Typep p,Typew w,Typew c,int n);template inline void S &a,Type &b);templatevoid BubbleSort(Type a,int n);int main()int n = 4;/物品数int c = 7;/背包容量int p = 0,9,10,7,4;/物品价值 下标从1开始int w = 0,3,5,2,1;/物品重量 下标从1开始cout背包容量为：

6、cendl;cout物品重量和价值分别为：endl;for(int i=1; i=n; i+)cout(wi,pi) ;coutendl;cout背包能装下的最大价值为：Knapsack(p,w,c,n)endl; return 0;templatevoid Knap:Backtrack(int i)if(in)/到达叶子节点bestp = cp;return;if(cw + wi bestp)/进入右子树Backtrack(i+1);templateTypep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量Typep b = cp;/

7、 以物品单位重量价值递减序装入物品while (i = n & wi = cleft)cleft -= wi;b += pi;i+;/ 装满背包if (i = n)b += pi/wi * cleft;return b;class Objecttemplatefriend Typep Knapsack(Typep,Typew ,Typew,int); public:int operator =a.d);private:int ID;float d;templateTypep Knapsack(Typep p,Typew w,Typew c,int n) /为Knap:Backtrack初始化T

8、ypew W = 0;Typep P = 0;Object *Q = new Objectn;for(int i=1; i=n; i+)Qi-1.ID = i;Qi-1.d = 1.0 * pi/wi;P += pi;W += wi;if(W = c)/装入所有物品return P;/依物品单位重量价值排序BubbleSort(Q,n);Knap K;K.p = new Typepn+1;K.w = new Typewn+1;for(int i=1; i=n; i+)K.pi = pQi-1.ID;K.wi = wQi-1.ID;K.cp = 0;K.cw = 0;K.c = c;K.n =

9、n;K.bestp = 0;/回溯搜索K.Backtrack(1);delete Q;delete K.w;delete K.p;return K.bestp;templatevoid BubbleSort(Type a,int n)/记录一次遍历中是否有元素的交换bool exchange;for(int i=0; in-1;i+)exchange = false ;for(int j=i+1; j=n-1; j+)if(aj=aj-1)Swap(aj,aj-1);exchange = true;/如果这次遍历没有元素的交换,那么排序结束 if(false = exchange)break

10、;template inline void S &a,Type &b)Type temp = a;a = b;b = temp;四、程序运行结果：五、回溯法解决0-1背包问题复杂度分析：计算上界需要O(n)时间，在最坏情况下有O(2n)个右儿子节点需要计算上界，故解0-1背包问题的回溯算法所需要的计算时间为O(n2n)。方法2：分支限界法：一、分支限界法描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c 0, wi 0, vi 0 , 1in.要求找一n元向量(x1,x2,xn,), x

11、i0,1, wi xic,且 vi xi达最大.即一个特殊的整数规划问题。二、分支限界法步骤思想：首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。例如：0-1背包问题，当n=3时，w=16,15,15, p=45,25,2

12、5, c=30。优先队列式分支限界法：处理法则:价值大者优先。AB,CC，D，EC，EC，J，KCF，GG，L，MG，MGN，OO。三、分支限界法解决0-1背包问题实现代码：/0-1背包问题 分支限界法求解#include stdafx.h#include MaxHeap.h#include using namespace std;class Objecttemplatefriend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); public:int operator =a.d;private:int ID;float d;

13、/单位重量价值template class Knap;class bbnodefriend Knap;templatefriend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); private:bbnode * parent; /指向父节点的指针bool LChild; /左儿子节点标识templateclass HeapNodefriend Knap;public:operator Typep() constreturn uprofit;private:Typep uprofit, /节点的价值上界profit; /节点所

14、相应的价值Typew weight; /节点所相应的重量int level; /活节点在子集树中所处的层序号bbnode *ptr; /指向活节点在子集中相应节点的指针templateclass Knaptemplatefriend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); public:Typep MaxKnapsack();private:MaxHeapHeapNode *H;Typep Bound(int i);void AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,

15、int lev);bbnode *E; /指向扩展节点的指针Typew c; /背包容量int n; /物品数Typew *w; /物品重量数组Typep *p; /物品价值数组Typew cw; /当前重量Typep cp; /当前价值int *bestx; /最优解template inline void S &a,Type &b);templatevoid BubbleSort(Type a,int n);int main()int n = 3;/物品数int c = 30;/背包容量int p = 0,45,25,25;/物品价值 下标从1开始int w = 0,16,15,15;/物

16、品重量 下标从1开始int bestx4;/最优解cout背包容量为：cendl;cout物品重量和价值分别为：endl;for(int i=1; i=n; i+)cout(wi,pi) ;coutendl;cout背包能装下的最大价值为：Knapsack(p,w,c,n,bestx)endl; cout此背包问题最优解为:endl;for(int i=1; i=n; i+)coutbestxi ;coutendl;return 0;templateTypep Knap:Bound(int i)/计算节点所相应价值的上界 Typew cleft = c-cw; /剩余容量高Typep b =

17、cp; /价值上界/以物品单位重量价值递减序装填剩余容量while(i=n & wi=cleft)cleft -= wi;b += pi;i+;/装填剩余容量装满背包if(i=n)b += pi/wi*cleft;return b;/将一个活节点插入到子集树和优先队列中templatevoid Knap:AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev) bbnode *b = new bbnode;b-parent = E;b-LChild = ch;HeapNode N;N.uprofit = up;N.profit = cp;N

18、.weight = cw;N.level = lev;N.ptr = b;H-Insert(N);/优先队列式分支限界法，返回最大价值，bestx返回最优解templateTypep Knap:MaxKnapsack()H = new MaxHeapHeapNode(1000);/为bestx分配存储空间bestx = new intn+1;/初始化int i = 1;E = 0;cw = cp = 0;Typep bestp = 0;/当前最优值Typep up = Bound(1); /价值上界/搜索子集空间树while(i!=n+1)/检查当前扩展节点的左儿子节点Typew wt = c

19、w + wi;if(wt bestp)bestp = cp + pi;AddLiveNode(up,cp+pi,cw+wi,true,i+1); up = Bound(i+1);/检查当前扩展节点的右儿子节点if(up=bestp)/右子树可能含有最优解AddLiveNode(up,cp,cw,false,i+1);/取下一扩展节点HeapNode N;H-DeleteMax(N);E = N.ptr;cw = N.weight;cp = N.profit;up = N.uprofit;i = N.level;/构造当前最优解for(int j=n; j0; j-)bestxj = E-LCh

20、ild;E = E-parent;return cp;/返回最大价值，bestx返回最优解templateTypep Knapsack(Typep p,Typew w,Typew c,int n, int bestx) /初始化Typew W = 0; /装包物品重量Typep P = 0; /装包物品价值/定义依单位重量价值排序的物品数组 Object *Q = new Objectn; for(int i=1; i=n; i+)/单位重量价值数组Qi-1.ID = i;Qi-1.d = 1.0*pi/wi; P += pi;W += wi;if(W=c)return P;/所有物品装包 /

21、依单位价值重量排序BubbleSort(Q,n);/创建类Knap的数据成员Knap K;K.p = new Typepn+1;K.w = new Typewn+1;for(int i=1; i=n; i+)K.pi = pQi-1.ID; K.wi = wQi-1.ID; K.cp = 0;K.cw = 0;K.c = c;K.n = n;/调用MaxKnapsack求问题的最优解 Typep bestp = K.MaxKnapsack(); for(int j=1; j=n; j+)bestxQj-1.ID = K.bestxj; delete Q;delete K.w;delete K.

22、p;delete K.bestx;return bestp;templatevoid BubbleSort(Type a,int n)/记录一次遍历中是否有元素的交换bool exchange;for(int i=0; in-1;i+)exchange = false ;for(int j=i+1; j=n-1; j+)if(aj=aj-1)Swap(aj,aj-1);exchange = true;/如果这次遍历没有元素的交换,那么排序结束 if(false = exchange)break ;template inline void S &a,Type &b)Type temp = a;a

23、 = b;b = temp;四、程序运行结果：五、分支限界法解决0-1背包问题复杂度分析：时间复杂度为：O(2n)；空间复杂度：O(n2n)。六、回溯法与分支限界法分析比较：这两种算法都得到了验证，运行结果证明了算法设计是可行的。通过对O-1背包问题的算法设计及时间复杂度分析可以看出：无论采用回溯法还是分支限界法，都是在已知约束条件下求解最大值建立数学模型算法实现的过程；但算法具体实现和数据结构的建立要用到递归和栈操作。比较回溯法和分支限界法，前者的时间复杂度高于后者，从耗费上而言优于后者。对于回溯法，能够获得最优解，时间复杂度较高，判断右子树时，按效率密度vi/wi对剩余对象排序；对于分支限界法：速度较快，易求解，不过占用的内存较大，效率不高。成 绩 单第 13 页