蛮力法等求解背包问题范例.doc

算法综合实验报告 学 号： 姓 名： 一、实验内容： 分别用蛮力、动态规划、贪心及分支限界法实现对TSP问题或者0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。 二、程序设计的基本思想、原理和算法描述： 蛮力法 数据结构: 使用一维数组存储物品的价值和重量还有下标。 函数组成 除主函数外还有一个subset（）函数，在此函数中列出所有的子集列出子集的同时求解最大价值，并且物品总重量要小于背包总容量。 输入/输出设计 首先通过键盘输入物品的总重量，再输入背包总容量，依次输入每个物品的重量，对应输入相应重量的价值，循环直至输入所有物品的重量和价值。最后输出物品的最大价值。 本程序通过键盘进行输入、屏幕进行输出。 （根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式） 符号名说明 w[1001]为物品重量的集合，v[1001]为物品价值的集合，n为物品数量，m为背包总容量,x[1001]用来存储物品是否装入背包，0为不装入，1为装入。用a[1001]来存储下标，用下标找出所有子集。 算法描述 采用增量构造的方法来构造出物品的所有子集，对物品的下标应用此方法进行构造，下标与物品相对应，选出子集时物品的重量加之前重量小于背包总重量时将价值加上去，最后选出能装入背包的物品的最大值。 动态规划法 (1)数据结构： 使用一维数组存储各个物品价值，重量，使用一个二维数组存储动态规划的整体求解的表，并以背包容量为最大列号，物品个数为最大行号。 (2)函数组成： 除主函数外由两个函数组成，一个是求解两个数中的大的一个的函数，另一个则是进行动态规划求解的函数，在使用动态规划方法具体求解时调用求最大值函数，在主程序之中调用动态规划函数。 (3)输入/输出设计： 首先通过键盘输入物品的总重量，再输入背包总容量，依次输入每个物品的重量，对应输入相应重量的价值，循环直至输入所有物品的重量和价值。输出物品的最大价值。 本程序通过键盘进行输入、屏幕进行输出。 （根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式） (4)符号名说明： w[1001]为物品重量的集合，v[1001]为物品价值的集合，n为物品数量，m为背包总容量,x[1001]用来存储物品是否装入背包，0为不装入，1为装入。V[1001][1001]用来存储动态规划具体求解过程,V[n][m]为最终结果最大价值。 (5)算法描述： [1].背包容量不足以装入物品i，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，则x[i]=0，背包不增加价值。 [2].背包容量可以装入物品i，如果把第i个物品装入背包，则背包中物品的价值等于前i-1个物品装入容量为j-w[i]的背包中的价值加上第i个物品的价值；如果第i个物品没有装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j的背包中所取得的价值。取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。表示在前个物品中能够装入容量为的背包中的物品的最大值，则可以得到如下动态函数： 贪心法 数据结构： 定义多个一维数组存储数据进行贪心选择。 (2)函数组成 ： 编写了一个选择排序函数，一个判断是否能装入包中的函数，一个主函数，在主函数中调用判断函数，在判断函数初始调用排序函数将单位价值重量从大到小进行排序。 (3)输入/输出设计： 首先通过键盘输入物品的总重量，再输入背包总容量，依次输入每个物品的重量，对应输入相应重量的价值，循环直至输入所有物品的重量和价值。先输出放入背包中的物品序号，在输出总价值，最后输出背包总容量。 本程序通过键盘进行输入、屏幕进行输出。（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式） (4)符号名说明: w[1001]为物品重量的集合，v[1001]为物品价值的集合，a[1001]为单位物品价值集合,n为物品数量，m为背包总容量,x[1001]用来存储物品是否装入背包，0为不装入，1为装入。 (5)算法描述： 制定贪心策略，求出单位物品价值并从大到小进行排序，依照排序结果从大到小放入，知道物品重量大于背包剩余容量为止，但是求出的并不是最优解，贪心法无法求出0/1背包的最优解，只能求出背包问题的最优解。 分支限界法 数据结构 定义一个优先队列存储分支限界所使用的树的节点，使用一维数组存储物品的重量和价值。 函数组成 一个构造函数，申请动态数组构造树，一个析构函数，删掉动态申请的数组，一个计算上界的函数，一个生成新节点的函数，一个将节点加入优先队列的函数，一个取上界最大节点的函数，