动态规划与回溯法解决0-1背包问题.doc

上传人:F****n 文档编号:98642057 上传时间:2019-09-12 格式:DOCX 页数:9 大小:70.37KB
返回 下载 相关 举报
动态规划与回溯法解决0-1背包问题.doc_第1页
第1页 / 共9页
动态规划与回溯法解决0-1背包问题.doc_第2页
第2页 / 共9页
动态规划与回溯法解决0-1背包问题.doc_第3页
第3页 / 共9页
动态规划与回溯法解决0-1背包问题.doc_第4页
第4页 / 共9页
动态规划与回溯法解决0-1背包问题.doc_第5页
第5页 / 共9页
点击查看更多>>
资源描述

《动态规划与回溯法解决0-1背包问题.doc》由会员分享,可在线阅读,更多相关《动态规划与回溯法解决0-1背包问题.doc(9页珍藏版)》请在金锄头文库上搜索。

1、0-1背包动态规划解决问题一、问题描述:有n个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?二、总体思路:根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现。三、动态规划的原理及过程:number4,capacity7i1234w(重量)3521v(价值)91074原理:动态规划与分治法类似,都是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。但不同的是,分治法在子问

2、题和子子问题等上被重复计算了很多次,而动态规划则具有记忆性,通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。过程:a)把背包问题抽象化(X1,X2,Xn,其中 Xi 取0或1,表示第 i 个物品选或不选),Vi表示第 i 个物品的价值,Wi表示第 i 个物品的体积(重量);b)建立模型,即求max(V1X1+V2X2+VnXn);c)约束条件,W1X1+W2X2+WnXn (V2X2+V3X3+VnXn)+V1X1;而(V2X2+V

3、3X3+VnXn)+V1X1=(V1X1+V2X2+VnXn),则有(V2Y2+V3Y3+VnYn)+V1X1(V1X1+V2X2+VnXn);该式子说明(X1,Y2,Y3,Yn)才是该01背包问题的最优解,这与最开始的假设(X1,X2,Xn)是01背包问题的最优解相矛盾,故01背包问题满足最优性原理;f)寻找递推关系式,面对当前商品有两种可能性:第一,包的容量比该商品体积小,装不下,此时的价值与前i-1个的价值是一样的,即V(i,j)=V(i-1,j);第二,还有足够的容量可以装该商品,但装了也不一定达到当前最优价值,所以在装与不装之间选择最优的一个,即V(i,j)=max V(i-1,j)

4、,V(i-1,j-w(i)+v(i) 其中V(i-1,j)表示不装,V(i-1,j-w(i)+v(i)表示装了第i个商品,背包容量减少w(i)但价值增加了v(i);由此可以得出递推关系式:1)j=w(i) V(i,j)=maxV(i-1,j),V(i-1,j-w(i)+v(i)number4,capacity7i1234w(重量)3521v(价值)91074四、构造最优解:最优解的构造可根据C列的数据来构造最优解,构造时从第一个物品开始。从i=1,j=c即m1c开始。1、对于mij,如果mij=mi+1j,则物品i没有装入背包,否则物品i装入背包; 2、为了确定后继即物品i+1,应该寻找新的j

5、值作为参照。如果物品i已放入背包,则j=j-wi;如果物品i未放入背包,则j=j。3、重复上述两步判断后续物品i到物品n-1是否放入背包。4、对于物品n,直接通过mnj是否为0来判断物品n是否放入背包。只要能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。首先要明确这张表是至底向上,从左到右生成的。序号WeightValue123456713947111316202025104711111114173274711111111114144444444从表格中可以看出背包的最大价值value=20,即当X1=1,X2=0,X3=1,X4=1。五、算法测试代码:#include#in

6、clude#include#include#include#includeusing namespace std;const int c = 8; /背包的容量const int w = 0,3,5,2,1; /物品的重量,其中0号位置不使用 。 const int v = 0,9,10,7,4; /物品对应的待加,0号位置置为空。const int n = sizeof(w)/sizeof(w0) - 1 ; /n为物品的个数 int xn+1;void package0_1(int m11,const int w,const int v,const int n)/n代表物品的个数 /采用从

7、底到顶的顺序来设置mij的值 /首先放wn for(int j = 0; j = c; j+) if(j = 1; i-) for(int j = 0; j = c; j+) if(j wi) mij = mi+1j;/如果j mi+1j-wi + vi? mi+1j : mi+1j-wi + vi; void answer(int m11,const int n) int j = c; int i; for(i = 1; i = n-1; i+) if(mij = mi+1j) xi = 0; else xi = 1; j = j - wi; xn = mij ? 1 : 0; int ma

8、in() int m611=0; package0_1(m,w,v,n); for(int i = 0; i = 5; i+) for(int j = 0; j = 10; j+) printf(%2d ,mij); cout endl; answer(m,n); cout The best answer is:n; for(int i = 1; i = 5; i+) cout xi ; system(pause); return 0;0-1背包回溯法解决问题一、问题描述:有n个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?二、总体思路:01背包属

9、于找最优解问题,用回溯法需要构造解的子集树。在搜索状态空间树时,只要左子节点是可一个可行结点,搜索就进入其左子树。对于右子树时,先计算上界函数,以判断是否将其减去。上界函数bound():当前价值cw+剩余容量可容纳的最大价值=当前最优价值bestp。为了更好地计算和运用上界函数剪枝,选择先将物品按照其单位重量价值从大到小排序,此后就按照顺序考虑各个物品。三、回溯法实现的过程:number4,capacity7i1234w(重量)3521v(价值)91074根据问题的解空间,对于n=4时的0-1背包问题,可用一棵完全二叉树表示其解空间,如下图所示。回溯过程:从根节点A开始回溯,节点A是当前的唯

10、一的活节点,在这个纵深方向先进入A的左子树B或者右子树C。假设先选择节点B,此时,节点B成为当前的活节点,节点B成为当前扩展节点。节点A到B选择w1=3,节点B背包剩余容量r=4,价值v=9,节点B到节点D,由于选择w2=5,此时背包容量r=4,背包容量不够,因而不可行,利用剪枝函数,减去以D为根节点的子树;然后回溯到B的右节点E,此时,E节点的剩余容量r=4,v=9, 选择w3=2,符合要求,节点E成为当前的扩展节点,进入节点J,此时,节点J的剩余容量r=2,v=16,选择w4=1,符合要求,到叶子节点T,此时,节点T的剩余容量r=1,v=20;因此得到一个可行解,即x=(1,0,1,1),

11、此时节点T成为一个死结点,回溯到节点U,得到一个可行解v=16,即x=(1,0,1,0),节点U成为死结点,回溯到节点E,进入右子树,节点K的剩余容量r=4,v=9,选择w4=1,符合要求,到达节点V,v=13,得到一个可行解x=(1,0,0,1),节点V成为死结点,回溯到节点K,到达叶子结点W,v=9得到一个可行解x=(1,0,0,0)。按此方式继续搜索整个解的空间。搜索结束后找到的最好解是0-1背包问题的最优解。五、算法测试代码:#include #include int n;/物品数量double c;/背包容量double v100;/各个物品的价值double w100;/各个物品的重量double cw = 0.0;/当前背包重量double cp = 0.0;/当前背包中物品价值double bestp = 0

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 办公文档 > 教学/培训

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号