动态规划与回溯法解决0

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

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

3、 X 1+W 2X 2+WnXn<capacity；d) 定义 V(i,j) ：当前背包容量 j，前 i 个物品最佳组合对应的价值；e) 最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质： 不论初始状态和初始决策如何， 对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。 判断该问题是否满足最优性原理， 采用反证法证明：假设 (X 1，X 2， ， Xn) 是 01 背包问题的最优解，则有 (X2 ，X 3， ， Xn) 是其子问题的最优解，编辑版 word假设 (Y2 ，Y 3， ， Yn) 是上述问题的子问题最优解，则理应有

4、(V2 Y2+V 3Y3 +V nYn)+V 1X 1 > (V 2X 2+V 3X 3+VnXn)+V1X 1；而(V 2X 2 +V 3 X3+ +VnXn)+V 1X 1=(V 1 X1+V 2X2 + +VnXn) ，则有(V2 Y2+V 3Y3 +VnYn)+V 1X 1 > (V 1X 1+V 2X 2+ +VnXn) ；该式子说明 (X 1，Y 2，Y3， ， Yn) 才是该 01 背包问题的最优解，这与最开始的假设(X1 ， X 2， ， Xn)是 01 背包问题的最优解相矛盾，故01 背包问题满足最优性原理；f) 寻找递推关系式，面对当前商品有两种可能性：第一，包

5、的容量比该商品体积小，装不下， 此时的价值与前i-1 个的价值是一样的，即 V(i,j)=V(i-1,j) ；第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即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)=V(i-1,j)2) j>=w(i)V(i,j)=max V(i-1,j) ， V(i-1,j-w(

6、i)+v(i) number 4， capacity 7i1234w( 重量 )3521v( 价值 )91074四、构造最优解：最优解的构造可根据C 列的数据来构造最优解，构造时从第一个物品开始。从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 是否放入背

7、包。只要能通过找规律手工填写出上面这张表就算理解了01 背包的动态规划算法。编辑版 word首先要明确这张表是至底向上，从左到右生成的。序号WeightValue123456713947111316202025104711111114173274711111111114144444444从表格中可以看出背包的最大价值value=20，即当X1=1 ， X2=0 ， X3=1 ， X4=1 。五、算法测试代码：#include<stdio.h>#include<stdlib.h>#include<iostream>#include<queue>#i

8、nclude<climits>#include<cstring>using 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代表物品的个

9、数编辑版 word/ 采用从底到顶的顺序来设置mij 的值/ 首先放 wnfor(int j = 0; j <= c; j+)if(j < wn) mnj = 0;/j小于 wn,所对应的值设为0，否则就为可以放置elsemnj = vn;/ 对剩下的n-1 个物品进行放置。int i;for(i = n-1; i >= 1; i-)for(int j = 0; j <= c; j+)if(j < wi)mij = mi+1j;/如果 j < wi 则，当前位置就不能放置，它等于上一个位置的值。/ 否则，就比较到底是放置之后的值大，还是不放置的值大，选择其中

10、较大者。elsemij = mi+1j > 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;elsexi = 1;编辑版 wordj = j - wi;xn = mij ? 1 : 0;int main()int m611=0;package0_1(m,w,v,n);for(int i = 0; i <= 5; i+)for(int j = 0; j <=

11、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;编辑版 word0-1 背包回溯法解决问题一、问题描述：有 n 个物品，它们有各自的重量和价值， 现有给定容量的背包， 如何让背包里装入的物品具有最大的价值总和？二、总

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

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

14、容量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,0,0,0)。按此方式继续搜索整个解的空间。搜索结束后找到的最好解是 0

15、-1 背包问题的最优解。五、算法测试代码：#include <stdio.h>#include <conio.h>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 knapsa

16、ck()int 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<perpj)/冒泡排序perp,order,sortv,sortwtemp = perpi;perpi=perpi;perpj=temp;编辑版 wordtemporder=orderi;orderi=orderj;orderj=temporder;temp = vi;vi=vj;vj=temp;temp=wi;wi=wj;wj=t

17、emp;/ 回溯函数void backtrack(int i)double bound(int i);if(i>n)bestp = cp;return;if(cw+wi<=c)cw+=wi;cp+=vi;puti=1;backtrack(i+1);cw-=wi;cp-=vi;if(bound(i+1)>bestp)/符合条件搜索右子数backtrack(i+1);/ 计算上界函数double bound(int i)double leftw= c-cw;double b = cp;while(i<=n&&wi<=leftw)leftw-=wi;编辑版 wordb+=vi;i+;if(i<=n)b+=vi/wi*leftw;return b;int main()int i;printf(" 请输入物品的数量和容量：");scanf("%d %lf",&n,&c);printf(" 请输入物品的重量和价值：");for(i=1;i<=n;i+)printf(" 第 %d 个物品的重量：",i);scanf("%lf",&wi);printf(&q