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

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

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

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

4、n)+V1X1； . 2 / 9 而(V2X2+V3X3+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)； 第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所

5、以在装与不装之间选择最优的一个，即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(i)+v(i) number4，capacity7 i 1 2 3 4 w(重量) 3 5 2 1 v(价值) 9 10 7 4 四、构造最优解： 最优解的构造可根据C列的数据来构造最优解

6、，构造时从第一个物品开始。从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背包的动态规划算法。 首先要明确这张表是至底向上，从左到右生成的。 . 3 / 9 序号 三、回溯法实现的过程： number4，capacity7 Wei

7、ght Value 1 2 3 20 2 5 10 4 7 11 11 11 14 17 3 2 7 4 7 11 11 11 11 11 4 1 4 4 4 4 4 4 4 4 4 5 6 7 1 3 9 4 7 11 13 16 20 从表格中可以看出背包的最大价值value=20，即当X1=1，X2=0，X3=1，X4=1。 五、算法测试代码： #include<stdio.h> #include<stdlib.h> #include<iostream> #include<queue> #include<climits> #in

8、clude<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代表物品的个数 /采用从底到顶的顺序来设置mij

9、的值 . 4 / 9 /首先放wn for(int j = 0; j <= c; j+) if(j < wn) mnj = 0; /j小于wn,所对应的值设为0，否则就为可以放置 else mnj = 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则，当前位置就不能放置，它等于上一个位置的值。 /否则，就比较到底是放置之后的值大，还是不放置的值大，选择其中较大者。 else mij

10、= 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; else xi = 1; j = j - wi; . 5 / 9 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(- ,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背包回溯法解决问题 . 6 / 9 一、问题描述： 有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？ 二、总体思路： 01背包属于找最优解问题，用回溯法需要构造解的子集树。在搜索状态空间树

12、时，只要左子节点是可一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去。 上界函数bound():当前价值cw+剩余容量可容纳的最大价值<=当前最优价值bestp。为了更好地计算和运用上界函数剪枝，选择先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。 i 1 2 3 4 w(重量) 3 5 2 1 v(价值) 9 10 7 4 根据问题的解空间，对于n=4时的0-1背包问题，可用一棵完全二叉树表示其解空间，如下图所示。 回溯过程： 从根节点A开始回溯，节点A是当前的唯一的活节点，在这个纵深方向先进入A的左子树B或者右子树C。假设先选择节

13、点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；因此得到一个可行解， . 7 / 9 即x=(1,0,1,1)，此时节点T成为一个死结点，回溯到节点U，得到一个可

14、行解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 <stdio.h> #include <conio.h> int n;/物品数量 double c;/背包容量 double v100;/各个物品的价值 double

15、 w100;/各个物品的重量 double cw = 0.0;/当前背包重量 double cp = 0.0;/当前背包中物品价值 double bestp = 0.0;/当前最优价值 double perp100;/单位物品价值排序后 int order100;/物品编号 int put100;/设置是否装入 /按单位价值排序 void knapsack() 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<=

16、n;j+) if(perpi<perpj)/冒泡排序perp,order,sortv,sortw temp = perpi; perpi=perpi; perpj=temp; temporder=orderi; orderi=orderj; orderj=temporder; temp = vi; . 8 / 9 vi=vj; vj=temp; temp=wi; wi=wj; wj=temp; /回溯函数 void backtrack(int i) double bound(int i); if(i>n) bestp = cp; return; if(cw+wi<=c) cw

17、+=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; b+=vi; i+; if(i<=n) . 9 / 9 b+=vi/wi*leftw; return b; int main() int i; printf(请输入物品的数量和容量：); scanf(%d %lf,&n,&