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

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

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

2、putObj(intflag,intn)：用来生成•了集的函数obj[],intmark[]，intn,intc):判int&flag):求解问题的最优解s[][10],intn):输出选择物品的情况1.3输入/输出设计本程序通过键盘进行输入、屏幕进行输出。1.4符号名说明符号说明s[][]存放子集mark口记录子集的町行性n物品的个数c物品的容量max记录背包所能产生的最大价值flag记录能产生最大价值的子集的编号1.5算法描述算法的伪代码描述如下：输入：背包的容量c，物品的个数n,n个物品的重量w[n]，价值v[n]输出：装入背包的物品编号以及产生的最大价值1.初始

3、化最大价值max=O,结果子集s=d);2.对集合｛1，2,n｝的每一个子集T，执行下述操作：1初始化背包的价值v=0，背包的重量w=0;2.2对子集!;的每一个元索j2.2.1如果w+wj

4、输入/输出设计本程序通过键盘进行输入、屏幕进行输出。2.4符号名说明符号说明n物品的个数c物品的容量W[]物品的重量V[]物品的价值X[]物品的选择情况v[][]存放迭代结果2.5算法描述算法的伪代码描述如下：输入：背的容量c，物品的个数n，ri个物品的重量w[n]，价值v[n]输出：装入背包的物品标号和背包获得的最大价值初始化二维数组V[][]={0}初始化二维数组的第0行，第0列2.循环直到i==n2.1循环直到j=c2.1.1如果背包的容量不足以装入物品i，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值相等2.2.2如果背包的容量可以装入物品分别

5、计算装入物品i可达到的价值量V[i-l][j-w[i]]+v[i],以及不放入物品i可以得到的最大价值V[i-1][j]，取二者中的较大者作为把前i个物品装入容量为j的竹屮的最优解3、贪心法3.1数据结构注：结构体用来存放物品的重量、价值、单位价值、物品编号等信息structObjectintValue;//物品价值intWeight;//物品重量doubleAveValue;//物沾申•位价值doubleNum;//物品可以放入的数量intkey;//物品标号｝；3.2函数组成intPartition(Objectr[],intfirst,intend)；以数组第一个

6、元素为准对数组进行一次划分并返冋基准元素的位置坐标voidQuicksort(_0bjectr[],intfirst,intend)；快速排序doubleknaspsack(intn,intM,Objectobject[])；求解背包问题的最优解3.3输入/输出设计本程序通过键盘进行输入、屏幕进行输出。3.4符号名说明符号说明n物品的个数C物品的容量pro[]物品的重量、价值、单位价值、编号3.5算法描述算法的伪代码描述如下：输入：背包的容量c,物品的个数n,n个物品的重量pro[n].Weight,价值pro[n].Value输fli:装入背包的物品标号和背包获得的最

7、大价值计算物品的单位价值并存入pro[n].将物见按照单位价值递减的顺序进行排序i=0;循环直到(object[i].Weight〉c)2.1将第i个物品放入背包，object[i].Num=l;2.2c-=pro[n].Weight；2.3i++；3.记录最后放入背包的物品的重景：object[i]•Num=(double)C/object[i].Weight；分支限界法4.1数据结构注：物品结构体，存放物品价值、重量、单位价值、物品编号等信息structobjintv;//物品价值intw;//物品重量doubleavg;//物品单位