蛮力法、动归、贪心、分支限界法解01背包问题.doc

《蛮力法、动归、贪心、分支限界法解01背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法综合实验报告学号：1004121206姓名：林一、实验内容：分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。二、程序设计的基本思想、原理和算法描述：1、蛮力法1.1数据结构注：结构体obj用来存放单个物品的价值和重量typedefstructobj{intw;//物品的重量intv;//物品的价值};1.2函数组成voidsubset(ints[][10],intn)：用来生成子集的函数voidjudge(int

2、s[][10],objobj[],intmark[],intn,intc)：判断子集的可行性intgetmax(intmark[],intn,int&flag)：求解问题的最优解voidoutputObj(intflag,ints[][10],intn):输出选择物品的情况1.3输入/输出设计本程序通过键盘进行输入、屏幕进行输出。1.4符号名说明符号说明S[][]存放子集mark[]记录子集的可行性n物品的个数c物品的容量max记录背包所能产生的最大价值flag记录能产生最大价值的子集的编号1.5

3、算法描述算法的伪代码描述如下：输入：背包的容量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+wj

4、态规划法2.1数据结构该程序不涉及任何数据结构2.2函数组成intmax(inti,intj);比较并返回两个数中的较大值intKnapSack(intw[],intv[],intx[],intn,intc);求解背包取得的最大值2.3输入/输出设计本程序通过键盘进行输入、屏幕进行输出。2.4符号名说明符号说明n物品的个数c物品的容量w[]物品的重量v[]物品的价值x[]物品的选择情况V[][]存放迭代结果2.5算法描述算法的伪代码描述如下：输入：背包的容量c,物品的个数n,n个物品的重量w[n]

5、,价值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的背包中的最优

6、解1、贪心法3.1数据结构注：结构体用来存放物品的重量、价值、单位价值、物品编号等信息struct_Object{intValue;//物品价值intWeight;//物品重量doubleAveValue;//物品单位价值doubleNum;//物品可以放入的数量intkey;//物品标号};3.2函数组成intPartition(_Objectr[],intfirst,intend)；以数组第一个元素为准对数组进行一次划分并返回基准元素的位置坐标voidQuickSort(_Objectr[],

7、intfirst,intend)；快速排序doubleknaspsack(intn,intM,_Objectobject[])；求解背包问题的最优解3.3输入/输出设计本程序通过键盘进行输入、屏幕进行输出。3.4符号名说明符号说明n物品的个数c物品的容量pro[]物品的重量、价值、单位价值、编号3.5算法描述算法的伪代码描述如下：输入：背包的容量c,物品的个数n,n个物品的重量pro[n].Weight,价值pro[n].Value输出：装入背包的物品标号和背包获得的最大价值1.计算物品的单位价值

8、并存入pro[n].2.将物品按照单位价值递减的顺序进行排序3.i=0;1.循环直到（object[i].Weight>c）4.1将第i个物品放入背包,object[i].Num=1；4.2c-=pro[n].Weight；4.3i++；2.记录最后放入背包的物品的重量：object[i].Num=(double)C/object[i].Weight；1、分支限界法4.1数据结构注：物品结构体，存放物品价值、重量、单位价值、物品编号等信息structobj{intv;//物品价值i