01背包问题

10-1背包问题计科一班李振华20120407111、问题描述给定n种物品和一背包，物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品（物品不能分割），使得装入背包中物品的总价值最大?抽象描述如下：x[n]:表示物品的选择，x[i]=1表示选择放进物品i到背包中。2、问题分析推导过程（最优子结构证明，最优值递归定义）1、动态规划法算法1.抽象之后背包问题转换为找到一个最优的数组，x1，x2，.....,xn的0-1序列。2.假设最优解的序列为x1，x2，.....,xn，能使背包容量C的总价值最大.如果，x1=1，则x2,...,xn是C-w1容量的背包的总价值依然是最大的序列；如果，x1=0，则x2,....,xn是C容量的背包的总价值依然是最大的序列。这就是我们所说的最优子结构性质。3.进一步分析：我们用m(i,j)表示为已经判断好了i:n的序列的背包最大价值，并且此时的背包剩余的容量为j，对物品i进行判断如果jwi,就只要做出选择wi和不选择wi情况下，哪种更能使背包的总价值更大：m(i,j)=max{m(i+1,j),m(i+1,j-wi)+vi}(注意这是个递归式)如果jwi:m(i,j)=m(i+1,j)初始化：m(n,j)=vn(j=wn)；m(n,j)=0(0=jwn)m(0,C)=0最终的结果：m(1,C)4.如果单纯的从利用递归，重复计算了很多的值，耗费的时间是很大的，动态规划还需避免这种重复计算，怎样自顶向下或自底向上的计算呢？2采用列表的方法就可以很好的分析设计自顶向下或自底向上的计算的算法了举例分析：n=3,c=6,w={4,3,2}v={5,2,1}m[i][j]=max{m[i+1][j],m[i+1][j-w[i]]+v[i]}列如m[2][3]=max{m[3][3],m[3][3-w[2]]+v[2]}，我们最终选择了m[3][3-w[2]]+v[2]。整个问题的最优解保存在m[1][6]中。2、回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。算法框架：1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。3、分支限界法首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可3行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。上界函数b=cp;//初始化为目前背包的重量//n表示物品总数，cleft为剩余空间while(i=n&&w[i]=cleft){cleft-=w[i];//w[i]表示i所占空间b+=p[i];//p[i]表示i的价值i++;}if(i=n)b+=p[i]/w[i]*cleft;//装填剩余容量装满背包returnb;//b为上界函数主算法循环体while(i!=n+1){//非叶结点//检查当前扩展结点的左儿子结点Typewwt=cw+w[i];if(wt=c){//左儿子结点为可行结点if(cp+p[i]bestp)bestp=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=Bound(i+1);//检查当前扩展结点的右儿子结点if(up=bestp)//右子树可能含最优解AddLiveNode(up,cp,cw,false,i+1);//取下一个扩展节点}3.计算求解过程、算法实现（源代码实现相关功能）1、动态规划算法和回溯法源代码（vc6.0下调试后通过）#includestdio.h#includemalloc.h#includewindows.htypedefstructgoods{double*value;//价值double*weight;//重量char*select;//是否选中到方案intnum;//物品数量doublelimitw;//限制重量}GOODS;4doublemaxvalue,totalvalue;//方案最大价值,物品总价值char*select1;//临时数组voidbackpack(GOODS*g,inti,doubletw,doubletv)//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值{intk;if(tw+g-weight[i]=g-limitw)//将物品i包含在当前方案,且重量小于等于限制重量{select1[i]=1;//选中第i个物品if(ig-num-1)//若物品i不是最后一个物品backpack(g,i+1,tw+g-weight[i],tv);//递归调用,继续添加下一物品else//若已到最后一个物品{for(k=0;kg-num;++k)//将状态标志复制到option数组中g-select[k]=select1[k];maxvalue=tv;//保存当前方案的最大价值}}select1[i]=0;//取消物品i的选择状态if(tv-g-value[i]maxvalue)//若物品总价值减去物品i的价值还大于maxv方案中已有的价值,说明还可以继续向方案中添加物品{if(ig-num-1)//若物品i不是最后一个物品backpack(g,i+1,tw,tv-g-value[i]);//递归调用,继续加入下一物品else//若已到最后一个物品{for(k=0;kg-num;++k)//将状态标志复制到option数组中g-select[k]=select1[k];maxvalue=tv-g-value[i];//保存当前方案的最大价值(从物品总价值中减去物品i的价值)}}}intmain(){doublesumweight;GOODSg;inti;printf(背包最大重量:);scanf(%lf,&g.limitw);printf(可选物品数量:);5scanf(%d,&g.num);if(!(g.value=(double*)malloc(sizeof(double)*g.num)))//分配内存保存物品价值{printf(内存分配失败\n);exit(0);}if(!(g.weight=(double*)malloc(sizeof(double)*g.num)))//分配内存保存物品的重量{printf(内存分配失败\n);exit(0);}if(!(g.select=(char*)malloc(sizeof(char)*g.num)))//分配内存保存物品的重量{printf(内存分配失败\n);exit(0);}if(!(select1=(char*)malloc(sizeof(char)*g.num)))//分配内存保存物品的重量{printf(内存分配失败\n);exit(0);}totalvalue=0;for(i=0;ig.num;i++){printf(输入第%d号物品的重量和价值:,i+1);scanf(%lf%lf,&g.weight[i],&g.value[i]);totalvalue+=g.value[i];//统计所有物品的价值总和}printf(\n背包最大能装的重量为:%.2f\n\n,g.limitw);for(i=0;ig.num;i++)printf(第%d号物品重:%.2f,价值:%.2f\n,i+1,g.weight[i],g.value[i]);for(i=0;ig.num;i++)//初始设各物品都没加入选择集select1[i]=0;maxvalue=0;//加入方案物品的总价值backpack(&g,0,0.0,totalvalue);//第0号物品加入方案,总重量为0,所有物品价值为totalvaluesumweight=0;printf(\n可将以下物品装入背包,使背包装的物品价值最大:\n);for(i=0;ig.num;++i)6if(g.select[i]){printf(第%d号物品,重量:%.2f,价值:%.2f\n,i+1,g.weight[i],g.value[i]);sumweight+=g.weight[i];}printf(\n总重量为:%.2f,总价值为:%.2f\n,sumweight,maxvalue);//getch();return0;}2、分支限界法#includeiostream#includestackusingnamespacestd;#defineN100classHeapNode//定义HeapNode结点类{public:doubleupper,price,weight;//upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量intlevel,x[N];//活节点在子集树中所处的层序号};doubleMaxBound(inti);doubleKnap();voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);stackHeapNodeHigh;//最大队Highdoublew[N],p[N];doublecw,cp,c=50;//cw为当前重量，cp为当前价值，定义背包容量为50intn=10;//货物数量为10intmain()7{inti;for(i=1;i=n;i++)cinw[i];//输入10个物品的重量for(i=1;i=n;i++)cinp[i];//输入10个物品的价值coutKnap()endl;//调用knap函数输出最大价值return0;}doubleMaxBound(intj)//MaxBound函数求最大上界{doubleleft=c-cw,b=cp;//剩余容量和价值上界while(j=n&&w[j]=left)//以物品单位重量价值递减装填剩余容量{left-=w[j];b+=p[j];j++;}if(j=n)b+=p[j]/w[j]*left;