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

0-1背包动态规划解决问题一、问题描述：有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？二、总体思路：根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。三、动态规划的原理及过程：number＝4，capacity＝7i1234w(重量)3521v(价值)91074原理：动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。过程：a)把背包问题抽象化（X1，X2，…，Xn，其中Xi取0或1，表示第i个物品选或不选），Vi表示第i个物品的价值，Wi表示第i个物品的体积（重量）；b)建立模型，即求max(V1X1+V2X2+…+VnXn)；c)约束条件，W1X1+W2X2+…+WnXncapacity；d)定义V(i,j)：当前背包容量j，前i个物品最佳组合对应的价值；e)最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。判断该问题是否满足最优性原理，采用反证法证明：假设(X1，X2，…，Xn)是01背包问题的最优解，则有(X2，X3，…，Xn)是其子问题的最优解，假设(Y2，Y3，…，Yn)是上述问题的子问题最优解，则理应有(V2Y2+V3Y3+…+VnYn)+V1X1(V2X2+V3X3+…+VnXn)+V1X1；而(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)；第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即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)jw(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)｝number＝4，capacity＝7i1234w(重量)3521v(价值)91074四、构造最优解：最优解的构造可根据C列的数据来构造最优解，构造时从第一个物品开始。从i=1,j=c即m[1][c]开始。1、对于m[i][j]，如果m[i][j]==m[i+1][j]，则物品i没有装入背包，否则物品i装入背包；2、为了确定后继即物品i+1，应该寻找新的j值作为参照。如果物品i已放入背包，则j=j-w[i]；如果物品i未放入背包，则j=j。3、重复上述两步判断后续物品i到物品n-1是否放入背包。4、对于物品n，直接通过m[n][j]是否为0来判断物品n是否放入背包。只要能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。首先要明确这张表是至底向上，从左到右生成的。序号WeightValue123456713947111316202025104711111114173274711111111114144444444从表格中可以看出背包的最大价值value=20，即当X1=1，X2=0，X3=1，X4=1。五、算法测试代码：#includestdio.h#includestdlib.h#includeiostream#includequeue#includeclimits#includecstringusingnamespacestd;constintc=8;//背包的容量constintw[]={0,3,5,2,1};//物品的重量，其中0号位置不使用。constintv[]={0,9,10,7,4};//物品对应的待加，0号位置置为空。constintn=sizeof(w)/sizeof(w[0])-1;//n为物品的个数intx[n+1];voidpackage0_1(intm[][11],constintw[],constintv[],constintn)//n代表物品的个数{//采用从底到顶的顺序来设置m[i][j]的值//首先放w[n]for(intj=0;j=c;j++)if(jw[n])m[n][j]=0;//j小于w[n],所对应的值设为0，否则就为可以放置elsem[n][j]=v[n];//对剩下的n-1个物品进行放置。inti;for(i=n-1;i=1;i--)for(intj=0;j=c;j++)if(jw[i])m[i][j]=m[i+1][j];//如果jw[i]则，当前位置就不能放置，它等于上一个位置的值。//否则，就比较到底是放置之后的值大，还是不放置的值大，选择其中较大者。elsem[i][j]=m[i+1][j]m[i+1][j-w[i]]+v[i]?m[i+1][j]:m[i+1][j-w[i]]+v[i];}voidanswer(intm[][11],constintn){intj=c;inti;for(i=1;i=n-1;i++)if(m[i][j]==m[i+1][j])x[i]=0;else{x[i]=1;j=j-w[i];}x[n]=m[i][j]?1:0;}intmain(){intm[6][11]={0};package0_1(m,w,v,n);for(inti=0;i=5;i++){for(intj=0;j=10;j++)printf(%2d,m[i][j]);coutendl;}answer(m,n);coutThebestansweris:\n;for(inti=1;i=5;i++)coutx[i];system(pause);return0;}0-1背包回溯法解决问题一、问题描述：有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？二、总体思路：01背包属于找最优解问题，用回溯法需要构造解的子集树。在搜索状态空间树时，只要左子节点是可一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去。上界函数bound():当前价值cw+剩余容量可容纳的最大价值=当前最优价值bestp。为了更好地计算和运用上界函数剪枝，选择先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。三、回溯法实现的过程：number＝4，capacity＝7i1234w(重量)3521v(价值)91074根据问题的解空间，对于n=4时的0-1背包问题，可用一棵完全二叉树表示其解空间，如下图所示。回溯过程：从根节点A开始回溯，节点A是当前的唯一的活节点，在这个纵深方向先进入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)，此时节点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背包问题的最优解。五、算法测试代码：#includestdio.h#includeconio.hintn;//物品数量doublec;//背包容量doublev[100];//各个物品的价值doublew[100];//各个物品的重量doublecw=0.0;//当前背包重量doublecp=0.0;//当前背包中物品价值doublebestp=0.0;//当前最优价值doubleperp[100];//单位物品价值排序后intorder[100];//物品编号intput[100];//设置是否装入//按单位价值排序voidknapsack(){inti,j;inttemporder=0;doubletemp=0.0;for(i=1;i=n;i++)perp[i]=v[i]/w[i];for(i=1;i=n-1;i++){for(j=i+1;j=n;j++)if(perp[i]perp[j])//冒泡排序perp[],order[],sortv[],sortw[]{temp=perp[i];perp[i]=perp[i];perp[j]=temp;temporder=order[i];order[i]=order[j];order[j]=temporder;temp=v[i];v[i]=v[j];v[j]=temp;temp=w[i];w[i]=w[j];w[j]=temp;}}}//回溯函数voidbacktrack(inti){doublebound(inti);if(in){bestp=cp;return;}if(cw+w[i]=c){cw+=w[i];cp+=v[i];put[i]=1;backtrack(i+1);cw-=w[i];cp-=v[i];}if(bound(i+1)bestp)//符合条件搜索右子数backtrack(i+1);}//计算上界函数doublebound(inti){doubleleftw=c-cw;doubleb=cp;while(i=n&&w[i]=leftw){leftw-=w[i];b+=v[i];i++;}if(i=n)b+=v[i]/w[i]*leftw;returnb;}intmain(){inti;printf(请输入物品的数量和容量：);scanf(%d%lf,&n,&c);printf(请输入物品的重量和价值：);for(i=1;i=n;i++){printf(第%d个物品的重量：,i);scanf(%lf,&w[i]);printf(价值是：);scanf(%lf,&v[i]);order[i]=i;}knapsack();backtrack(1);printf(最有价值为：%lf\n,bestp);printf(需要装入的物品编号是：);for(i=1;i=n;i++){if(put[i]==1)printf(%d,order[i]);}return0;}