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

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

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

3、Xi +W 2X2 + +WnXn (V2X2+V3X3+VnXn)+V 1X1 ；而(V2X2+V 3X3+VnXn)+V 1X1=(V 1X1+V 2X 2+VnXn)，则有(V2Y2+V 3丫3+VnYn)+V 1X1 (V 1X1+V 2 X2+VnXn)；该式子说明(X 1, 丫2, 丫3,Yn)才是 该01背包问题的最优解，这与最开始的假设 (Xi，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 = 7 i1234w（重 量）3521v（价 值）91074四、构造最优解：最优解的构造可根据C列的数据来构造最优解， 构造时从第一个

5、物品开始。从i=1,j=c 即 m1c开始。1、对于mij，如果mij=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背包的动态规划算法。首先要明确这张表是至底向上，从左到右生成 的。序 号WeightValue123456713947111316202025104711111114

6、173274711111111114144444444从表格中可以看出背包的最大价值 value=20即当 X仁1 ，X2=0，X3=1 ，X4=1。五、算法测试代码:#in clude#in clude#in clude#in clude#in clude #in clude/背包的/物品/物品using n amespace std;const int c = 8;容量的重量，其中0号位置不使用const int w = 0,3,5,2,1； const in t v = 0,9,10,7,4;对应的待加，0号位置置为空const int n = sizeof(w)/sizeof(w0)

7、- 1 ;n为物品的个数in t xn+1;void package0_1(i nt m11,c onst intw,c onst int v,c onst int n)/n代表物品的个数/采用从底到顶的顺序来设置mij的值/首先放 wnfor(i nt j = 0; j = c; j+)if(j = 1; i-)for(i nt j = 0; j = c; j+)if(j wi)mij = mi+1j;如果 j mi+1j-wi +vi? mi+1j : mi+1j-wi + vi;void an swer( int m11,c onst int n)int j = c;int i;for(

8、i = 1; i = n-1; i+)if(mij = mi+1j) xi = 0;elsexi = 1;j = j - wi;xn = mij ? 1 : 0;int mai n()int m611=0;packageO_1(m,w,v, n);for(i nt i = 0; i = 5; i+)for(i nt j = 0; j = 10; j+)prin tf(%2d ,mij);cout en dl;an swer(m, n);cout The best an swer is: n;for(i nt i = 1; i = 5; i+)cout xi ;system(pause);ret

9、urn 0;0-1背包回溯法解决问题一、问题描述：有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背 包里装入的物品具有最大的价值总和？二、总体思路：01背包属于找最优解问题，用回溯法需要构 造解的子集树。在搜索状态空间树时，只要 左子节点是可一个可行结点，搜索就进入其 左子树。对于右子树时，先计算上界函数，以判断是否将其减去。上界函数bound():当前价值cw+剩余容量 可容纳的最大价值 =当前最优价值bestp 。 为了更好地计算和运用上界函数剪枝，选择 先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。三、回溯法实现的过程：number = 4 , ca

10、pacity = 7 i1234w（重3521量)v（价91074值)根据问题的解空间，对于n=4时的0-1背包问 题，可用一棵完全二叉树表示其解空间， 如下图 所示。回溯过程：从根节点A开始回溯，节点A是当前的唯一的 活节点，在这个纵深方向先进入 A的左子树B 或者右子树C。假设先选择节点B,此时，节点 B成为当前的活节点，节点 B成为当前扩展节 点。节点A到B选择w仁3,节点B背包剩余容量 r=4,价值v=9,节点B到节点 D，由于选择 w2=5,此时背包容量r=4,背包容量不够，因而 不可行，利用剪枝函数，减去以 D为根节点的 子树；然后回溯到B的右节点E，此时，E节点 的剩余容量r=4

11、 ，v=9,选择w3=2,符合要求， 节点E成为当前的扩展节点，进入节点 J,此时, 节点J的剩余容量r=2 ，v=16，选择w4=1, 符合要求，到叶子节点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,选择w4=1 ，符合要求，到达节点V，v=13,得到一个可行解x=(1,0,0,1),节点V成为死结 点，回溯到节点K，到达叶子结点 W，v=9得 到一个可行解x=(1,

12、0,0,0)。按此方式继续搜索 整个解的空间。搜索结束后找到的最好解是 0-1 背包问题的最优解。五、算法测试代码:#in clude 1#in clude vconi o.h1int n;/ 物品数量double c;/背包容量double v100;/各个物品的价值double w100;各个物品的重量double cw = 0.0;/当前背包重量double cp = 0.0;/当前背包中物品价值double bestp = 0.0;/当前最优价值double perp100;/单位物品价值排序后in t order100;/物品编号int put100;/设置是否装入1/按单位价值排序

13、void kn apsack()11int i,j;int temporder = 0; double temp = 0.0;for(i=1;i=n ;i+)perpi=vi/wi;for(i=1;i=n-1;i+)for(j=i+1;j=n ;j+)if(perpi n)bestp = cp; return;if(cw+wibestp) 子数backtrack(i+1);/计算上界函数double boun d(i nt i)double leftw= c-cw;double b = cp;while(i=n&wiv=leftw) leftw-=wi;b+=vi;i+;if(i=n)b+=vi/wi*leftw; return b;printf（请输入物品的重量和价值：）;for（i=1;i=n ;i+）