搜索
算法综合实验报告学号：1004121206姓名：林一、实验内容：分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。二、程序设计的基本思想、原理和算法描述：1、蛮力法1.1数据结构注：结构体obj用来存放单个物品的价值和重量typedefstructobj{intw;//物品的重量intv;//物品的价值};1.2函数组成voidsubset(ints[][10],intn)：用来生成子集的函数voidjudge(ints[][10],objobj[],intmark[],intn,intc)：判断子集的可行性intgetmax(intmark[],intn,int&flag)：求解问题的最优解voidoutputObj(intflag,ints[][10],intn):输出选择物品的情况1.3输入/输出设计本程序通过键盘进行输入、屏幕进行输出。1.4符号名说明1.5算法描述算法的伪代码描述如下：输入：背包的容量c,物品的个数n,n个物品的重量w[n],价值v[n]输出：装入背包的物品编号以及产生的最大价值1.初始化最大价值max=0,结果子集s=φ;2.对集合{1,2,......n}的每一个子集T，执行下述操作：2.1初始化背包的价值v=0，背包的重量w=0;2.2对子集t的每一个元素j2.2.1如果w+wjc,则w=w+wj,v=v+vj;2.2.2否则，转步骤2考察下一个子集；2.3如果maxv,则max=v;s=t;3.输出子集S中的各元素2、动态规划法2.1数据结构该程序不涉及任何数据结构2.2函数组成intmax(inti,intj);比较并返回两个数中的较大值intKnapSack(intw[],intv[],intx[],intn,intc);求解背包取得的最大值2.3输入/输出设计符号说明S[][]存放子集mark[]记录子集的可行性n物品的个数c物品的容量max记录背包所能产生的最大价值flag记录能产生最大价值的子集的编号本程序通过键盘进行输入、屏幕进行输出。2.4符号名说明2.5算法描述算法的伪代码描述如下：输入：背包的容量c,物品的个数n,n个物品的重量w[n],价值v[n]输出：装入背包的物品标号和背包获得的最大价值1.初始化二维数组V[][]={0}2.初始化二维数组的第0行，第0列2.循环直到i==n2.1循环直到j=c2.1.1如果背包的容量不足以装入物品i,则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值相等2.2.2如果背包的容量可以装入物品i,分别计算装入物品i可达到的价值量V[i-1][j-w[i]]+v[i],以及不放入物品i可以得到的最大价值V[i-1][j]，取二者中的较大者作为把前i个物品装入容量为j的背包中的最优解3、贪心法3.1数据结构注：结构体用来存放物品的重量、价值、单位价值、物品编号等信息struct_Object符号说明n物品的个数c物品的容量w[]物品的重量v[]物品的价值x[]物品的选择情况V[][]存放迭代结果{intValue;//物品价值intWeight;//物品重量doubleAveValue;//物品单位价值doubleNum;//物品可以放入的数量intkey;//物品标号};3.2函数组成intPartition(_Objectr[],intfirst,intend)；以数组第一个元素为准对数组进行一次划分并返回基准元素的位置坐标voidQuickSort(_Objectr[],intfirst,intend)；快速排序doubleknaspsack(intn,intM,_Objectobject[])；求解背包问题的最优解3.3输入/输出设计本程序通过键盘进行输入、屏幕进行输出。3.4符号名说明3.5算法描述算法的伪代码描述如下：输入：背包的容量c,物品的个数n,n个物品的重量pro[n].Weight,价值pro[n].Value输出：装入背包的物品标号和背包获得的最大价值1.计算物品的单位价值并存入pro[n].2.将物品按照单位价值递减的顺序进行排序符号说明n物品的个数c物品的容量pro[]物品的重量、价值、单位价值、编号3.i=0;4.循环直到（object[i].Weightc）4.1将第i个物品放入背包,object[i].Num=1；4.2c-=pro[n].Weight；4.3i++；5.记录最后放入背包的物品的重量：object[i].Num=(double)C/object[i].Weight；4、分支限界法4.1数据结构注：物品结构体，存放物品价值、重量、单位价值、物品编号等信息structobj{intv;//物品价值intw;//物品重量doubleavg;//物品单位价值intid;//物品编号};注：结构体node用来存放节点表节点structnode{node*parent,//父亲结点指针*next;//后继结点指针intlevel,//节点所处的层isin,//记录物品是否装入背包，0代表不装,1代表装入cw,//当前背包已经装入的物品重量cv;//当前背包已经装入的物品价值doubleub;//结点的上界值};4.2函数组成intPartition(_Objectr[],intfirst,intend)；以数组第一个元素为准对数组进行一次划分并返回基准元素的位置坐标voidQuickSort(_Objectr[],intfirst,intend)；快速排序doubleUpb(inti,intcw,intcv);//计算上界值node*nnoder(node*parent1,intisin1,doubleub1);生成一个新的结点voidaddnode(node*node1);//将结点添加到队列中node*nextnode();//取下一个结点voidfenzjx();//分支界限法的主要实现函数voidoutput();//用于输出物品的选择情况及最优解4.3输入/输出设计本程序通过键盘进行输入、屏幕进行输出。4.4符号名说明符号说明c背包的容量n物品的个数pro存放物品信息avg物品的单位价值量opv背包容量最优解popv指向最优解的指针level节点的层cw当前背包装载量cv当前背包价值ub节点的上界值isin记录当前结点物品是否放入背包flag物品原来位置(4)算法描述算法的伪代码描述如下：输入：背包的容量c,物品的个数n,n个物品的信息pro[n]输出：装入背包的物品标号和背包获得的最大价值1.对输入的物品按照单位价值量递减的顺序进行排序2.初始化问题最优解opv=0,初始化第0层结点，计算上界值ub=Upb(0,0,0);并设置该结点设为优先级队列的根结点3.循环直到优先级队列为空3.1如果取出当前结点位于第n-1层，则其子结点已是叶子结点，判断子结点取值情况，若得到的解大于当前问题得到的最优解opv，则重置问题的最优解opv3.2如果取出当前结点层leveln-1对结点i的每个孩子结点x执行下列操作:3.2.1如果结点x可能产生的最优解ubopv，则丢弃该结点;3.2.2否则估算该节点x的目标函数值ub,将结点加入队列;4.将该结点对应的最优值输出，回溯求得最优解的各个分量三、源程序及注释：1、蛮力法#includeiostream#includemath.husingnamespacestd;//物品typedefstructobj{intw;intv;};//生成子集voidsubset(ints[][10],intn){inti,j,m,k;for(i=0;ipow(2,n);i++){k=i;for(j=n-1;j=0;j--){m=k%2;s[i][j]=m;k=k/2;}}}//判断子集可行性voidjudge(ints[][10],objobj[],intmark[],intn,intc){inti,j,v,w;for(i=0;ipow(2,n);i++){w=0;v=0;for(j=0;jn;j++){w+=obj[j].w*s[i][j];v+=obj[j].v*s[i][j];}if(w=c)mark[i]=v;elsemark[i]=0;}}//求问题的最优解intgetmax(intmark[],intn,int&flag){inti,max;max=0;for(i=0;ipow(2,n);i++){if(mark[i]max){max=mark[i];flag=i;}}returnmax;}//输出选择物品的情况voidoutputObj(intflag,ints[][10],intn){cout装入背包物品的编号为：;for(inti=0;in;i++){if(s[flag][i]==1)couti+1;}coutendl;}intmain(){ints[1024][10],mark[1024],n,max,c,flag;objobj[10];cout请输入背包的容量：;cinc;cout请输入物品的个数：;cinn;cout请分别输入物品的重量：;for(inti=0;in;i++){cinobj[i].w;}cout请分别输入物品的价值：;for(i=0;in;i++){cinobj[i].v;}subset(s,n);judge(s,obj,mark,n,c);max=getmax(mark,n,flag);outputObj(flag,s,n);cout背包可容纳的最大价值为：maxendl;return0;}2、动态规划法#includeiostreamusingnamespacestd;//比较并返回两个数中的较大值intmax(inti,intj){if(ij)returnj;elsereturni;}//求解背包取得的最大值intKnapSack(intw[],intv[],intx[],intn,intc){inti,j,V[105][1005]={0};for(i=0;i=n;i++)//初始化第0列V[i][0]=0;for(j=0;j=c;j++)//初始化第0行V[0][j]=0;for(i=1;i=n;i++)//计算第i行，进行第i次迭代{for(j=1;j=c;j++){if(jw[i])V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);}}for(j=c,i=n;i0;i--)//求装入背包的物品编号{if(V[i][j]V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}returnV[n][c];}intmain(){intc,n,w[105],v[105],x[105],max;//x[]记录物品的选择情况cout请输入背包的重量：;cinc;cout请输入物品的个数：;cinn;cout请分别输入物品的重量：;for(inti=1;i=n;i++)cinw[i];cout请分别输入物品的价值：;for(i=1;i=n;i++)cinv[i];max=KnapSack(w,v,x,n,c);cout装入背包的物品编号为：;for(i=1;i=n;i++){if(x[i]==1)couti;}coutendl;cout背包可容纳的最大价值为：maxendl;return0;}3、贪心法#includeiostream#includestdio.husingnamespacestd;//物品结构体struct_Object{intValue;//物品价值intWeight;//物品重量doubleAveValue;//物品单