蛮力法、动态规划法、回溯法和分支限界法求解01背包问题

一、实验内容：分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。注：0/1背包问题：给定n种物品和一个容量为C的背包，物品i的重量是iw，其价值为iv，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。二、所用算法的基本思想及复杂度分析：1.蛮力法求解0/1背包问题：1）基本思想：对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。2）代码:#includeiostream#includealgorithmusingnamespacestd;#defineN100//最多可能物体数structgoods//物品结构体{intsign;//物品序号intw;//物品重量intp;//物品价值}a[N];boolm(goodsa,goodsb){return(a.p/a.w)(b.p/b.w);}intmax(inta,intb){returnab?b:a;}intn,C,bestP=0,cp=0,cw=0;intX[N],cx[N];/*蛮力法求解0/1背包问题*/intForce(inti){if(in-1){if(bestPcp&&cw+a[i].w=C){for(intk=0;kn;k++)X[k]=cx[k];//存储最优路径bestP=cp;}returnbestP;}cw=cw+a[i].w;cp=cp+a[i].p;cx[i]=1;//装入背包Force(i+1);cw=cw-a[i].w;cp=cp-a[i].p;cx[i]=0;//不装入背包Force(i+1);returnbestP;}intKnapSack1(intn,goodsa[],intC,intx[]){Force(0);returnbestP;}intmain(){goodsb[N];printf(物品种数n:);scanf(%d,&n);//输入物品种数printf(背包容量C:);scanf(%d,&C);//输入背包容量for(inti=0;in;i++)//输入物品i的重量w及其价值v{printf(物品%d的重量w[%d]及其价值v[%d]:,i+1,i+1,i+1);scanf(%d%d,&a[i].w,&a[i].p);b[i]=a[i];}intsum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题printf(蛮力法求解0/1背包问题:\nX=[);for(i=0;in;i++)coutX[i];//输出所求X[n]矩阵printf(]装入总价值%d\n,sum1);bestP=0,cp=0,cw=0;//恢复初始化}3）复杂度分析：蛮力法求解0/1背包问题的时间复杂度为：)2()(nOnT。2.动态规划法求解0/1背包问题：1）基本思想：令),(jiV表示在前)1(nii个物品中能够装入容量为)1(Cjj的背包中的物品的最大值，则可以得到如下动态函数：0),0()0,(jViV)(),1(),,1(max))(,1(),(iiiiwjvwjiVjiVwjjiVjiV按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第n个阶段。最后，),(CnV便是在容量为C的背包中装入n个物品时取得的最大价值。2）代码：#includeiostream#includealgorithmusingnamespacestd;#defineN100//最多可能物体数structgoods//物品结构体{intsign;//物品序号intw;//物品重量intp;//物品价值}a[N];boolm(goodsa,goodsb){return(a.p/a.w)(b.p/b.w);}intmax(inta,intb){returnab?b:a;}intn,C,bestP=0,cp=0,cw=0;intX[N],cx[N];intKnapSack2(intn,goodsa[],intC,intx[]){intV[N][10*N];for(inti=0;i=n;i++)//初始化第0列V[i][0]=0;for(intj=0;j=C;j++)//初始化第0行V[0][j]=0;for(i=1;i=n;i++)//计算第i行，进行第i次迭代for(j=1;j=C;j++)if(ja[i-1].w)V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].p);j=C;//求装入背包的物品for(i=n;i0;i--){if(V[i][j]V[i-1][j]){x[i-1]=1;j=j-a[i-1].w;}elsex[i-1]=0;}returnV[n][C];//返回背包取得的最大价值}intmain(){goodsb[N];printf(物品种数n:);scanf(%d,&n);//输入物品种数printf(背包容量C:);scanf(%d,&C);//输入背包容量for(inti=0;in;i++)//输入物品i的重量w及其价值v{printf(物品%d的重量w[%d]及其价值v[%d]:,i+1,i+1,i+1);scanf(%d%d,&a[i].w,&a[i].p);b[i]=a[i];}intsum2=KnapSack2(n,a,C,X);//调用动态规划法求0/1背包问题printf(动态规划法求解0/1背包问题:\nX=[);for(i=0;in;i++)coutX[i];//输出所求X[n]矩阵printf(]装入总价值%d\n,sum2);for(i=0;in;i++){a[i]=b[i];}//恢复a[N]顺序}3）复杂度分析:动态规划法求解0/1背包问题的时间复杂度为：)()(CnOnT。3.回溯法求解0/1背包问题：1）基本思想：回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。2）代码:#includeiostream#includealgorithmusingnamespacestd;#defineN100//最多可能物体数structgoods//物品结构体{intsign;//物品序号intw;//物品重量intp;//物品价值}a[N];boolm(goodsa,goodsb){return(a.p/a.w)(b.p/b.w);}intmax(inta,intb){returnab?b:a;}intn,C,bestP=0,cp=0,cw=0;intX[N],cx[N];intBackTrack(inti){if(in-1){if(bestPcp){for(intk=0;kn;k++)X[k]=cx[k];//存储最优路径bestP=cp;}returnbestP;}if(cw+a[i].w=C){//进入左子树cw=cw+a[i].w;cp=cp+a[i].p;cx[a[i].sign]=1;//装入背包BackTrack(i+1);cw=cw-a[i].w;cp=cp-a[i].p;//回溯，进入右子树}cx[a[i].sign]=0;//不装入背包BackTrack(i+1);returnbestP;}intKnapSack3(intn,goodsa[],intC,intx[]){for(inti=0;in;i++){x[i]=0;a[i].sign=i;}sort(a,a+n,m);//将各物品按单位重量价值降序排列BackTrack(0);returnbestP;}intmain(){goodsb[N];printf(物品种数n:);scanf(%d,&n);//输入物品种数printf(背包容量C:);scanf(%d,&C);//输入背包容量for(inti=0;in;i++)//输入物品i的重量w及其价值v{printf(物品%d的重量w[%d]及其价值v[%d]:,i+1,i+1,i+1);scanf(%d%d,&a[i].w,&a[i].p);b[i]=a[i];}intsum3=KnapSack3(n,a,C,X);//调用回溯法求0/1背包问题printf(回溯法求解0/1背包问题:\nX=[);for(i=0;in;i++)coutX[i];//输出所求X[n]矩阵printf(]装入总价值%d\n,sum3);for(i=0;in;i++){a[i]=b[i];}//恢复a[N]顺序3）复杂度分析：最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为：)2()(nOnT。由于其对蛮力法进行优化后的算法，其复杂度一般比蛮力法要小。空间复杂度：有n个物品，即最多递归n层，存储物品信息就是一个一维数组，即回溯法求解0/1背包问题的空间复杂度为)(nO。4.分支限界法求解背包问题：1）基本思想：分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。2）代码:#includeiostream#includealgorithmusingnamespacestd;#defineN100//最多可能物体数structgoods//物品结构体{intsign;//物品序号intw;//物品重量intp;//物品价值}a[N];boolm(goodsa,goodsb){return(a.p/a.w)(b.p/b.w);}intmax(inta,intb){returnab?b:a;}intn,C,bestP=0,cp=0,cw=0;intX[N],cx[N];structKNAPNODE//状态结构体{bools1[N];//当前放入物体intk;//搜索深度intb;//价值上界intw;//物体重量intp;//物体价值};structHEAP//堆元素结构体{KNAPNODE*p;//结点数据intb;//所指结点的上界};//交换两个堆元素voidswap(HEAP&a,HEAP&b){HEAPtemp=a;a=b;b=temp;}//堆中元素上移voidmov_up(HEAPH[],inti){booldone=false;if(i!=1){while(!done&&i!=1){if(H[i].bH[i/2