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

《动态规划与回溯法解决0-1背包问题》由会员分享，可在线阅读，更多相关《动态规划与回溯法解决0-1背包问题（8页珍藏版）》请在装配图网上搜索。

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

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

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

4、，所以在装与不装之间选择最优的一个，即 V(i,j)=max V(i-1,j) , 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)=max V(i-1,j), V(i-1,j-w(i)+v(i)number =4, capacity = 7i1234w(重里)3521v（价彳1 ）91074四、构造最优解：最优解的构造可根据C列的数据来构造最优解，构造时从第一个物品开始。从i=1尸c即m1c开始。1、对于mij,如果mij=

5、mi+1j,则物品i没有装入背包，否则物品i装入背包；2、为了确定后继即物品i+1 ,应该寻找新的j值作为参照。如果物品i已放入背包， 则j=j-wi；如果物品i未放入背包，则j=j。3、重复上述两步判断后续物品i到物品n-1是否放入背包。4、对于物品n,直接通过 mnj是否为0来判断物品n是否放入背包。01背包的动态规划算法。只要能通过找规律手工填写出上面这张表就算理解了 首先要明确这张表是至底向上，从左到右生成的。序号WeightValue1234567139471113162025104711111114173274711111111114144144444从表格中可以看出背包的最大价值

6、value=20 ,即当X1=1 , X2=0 , X3=1 , X4=1 。五、算法测试代码:#include#include#include#include#include#includeusing namespace std;constint c = 8;/背包的容量constint w口 = 0,3,5,2,1;/物品的重量，其中 0号位置不使用。constint v = 0,9,10,7,4;/ 物品对应的待加，0号位置置为空。constint n = sizeof(w)/sizeof(w0) - 1 ; /n 为物品的个数int xn+1;void package0_1(int m

7、11,constint w,constint v,constint n)/n代表物品的个数/采用从底到顶的顺序来设置mij的值首先放wnfor(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,constint n)int j = c;inti;for(i = 1; i= n-1; i+)if(mij = mi+1j) xi = 0;elsexi = 1;j =

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

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

10、如下图所示。回溯过程：从根节点A开始回溯，节点A是当前的唯一的活节点，在这个纵深方向先进入 A的左子树B或者右子树Co假设先选择节点 B,此时，节点B成为当前的活节点，节点 B成为当前扩展 节点。节点A到B选才W w1=3,节点B背包剩余容量r=4,价值v=9,节点B到节点D,由于选择w2=5, 此时背包容量r=4,背包容量不够，因而不可行，利用剪枝函数，减去以D为根节点的子树； 然后回溯到B的右节点E,此时，E节点的剩余容量r=4 , v=9,选才w w3=2,符合要求，节点 E成为当前的扩展节点，进入节点J,此时，节点J的剩余容量r=2 , v=16 ,选才w w4=1,符合要求，到叶子节

11、点 T,此时，节点 T的剩余容量r=1 , v=20 ;因此得到一个可行解，即x=(1,0,1,1),此时节点 T成为一个死结点，回溯到节点 U ,得到一个可行解v=16,即x=(1,0,1,0),节点U成为死结点，回溯到节点E,进入右子树，节点 K的剩余容量r=4,v=9,选才w w4=1，符合要求，到达节点V,v=13，得到一个可行解 x=(1,0,0,1),节点V成为死结点， 回溯到节点K,到达叶子结点 W, v=9得到一个可行解 x=(1,0,0,0)。按此方式继续搜索整 个解的空间。搜索结束后找到的最好解是0-1背包问题的最优解。五、算法测试代码：#include #include

12、int n;物品数量double c;背包容量double v100;/各个物品的价值double w100;各个物品的重量double cw = 0.0;/当前背包重量double cp = 0.0;/ 当前背包中物品价值double bestp = 0.0;/当前最优价值double perp100;单位物品价值排序后int order100;/ 物品编号int put100;/ 设置是否装入/按单位价值排序void knapsack() inti,j;inttemporder = 0;double temp = 0.0;for(i=1;i=n;i+) perpi=vi/wi;for(i=

13、1;i=n-1;i+) for(j=i+1;j=n;j+) if(perpin)(bestp = cp;return;)if(cw+wibestp)符合条件搜索右子数backtrack(i+1);)/计算上界函数double bound(inti)(double leftw= c-cw;double b = cp;while(i=n&wi=leftw)(leftw-=wi;b+=vi;i+;)if(i=n)b+=vi/wi*leftw;return b;)int main()(inti;printf(请输入物品的数量和容量：);scanf(%d %lf,&n,&c);printf(请输入物品的重量和价值：);for(i=1;i=n;i+)(printf( 第个物品的重量：,i);scanf(%lf,&wi);printf(价值是：);scanf(%lf,&vi);orderi=i;)knapsack();backtrack(1);printf(最有价值为：%lfn,bestp);printf(需要装入的物品编号是：)；for(i=1;i=n;i+)(if(puti=1)printf(%d ,orderi);)return 0;)