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+…+WnXn(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)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。五、算法测试代码:#include#include#include#include#include#includeusingnamespacestd;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],const...