文档介绍：算法分析与设计实验报告学院: 信息科学与工程学院专业班级: i got7 指导老师: 学号: i got7 姓名: 鸟宝宝 a. 合并排序合并排序是分治法的应用,把需要排序的数组 A[1 - n] ,一分为二 A[1 -n/2] 和 A[n/2+1 - n] ,然后在对每一个子数组递归排序, 接着再把这两个子数组合并成一个有序的数组。算法描述: 第一步: 申请空间, 使其大小为两个已经排序序列之和, 该空间用来存放合并后的序列第二步: 设定两个指针, 最初位置分别为两个已经排序序列的起始位置第三步: 比较两个指针所指向的元素, 选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤 3 直到某一指针超出序列尾, 将另一序列剩下的所有元素直接复制到合并序列尾关键代码: private static void Sort( int [] a, int left , int right ){ if ( left >= right ) return ; int mid =( left + right )/ 2; Sort (a, left , mid ); Sort (a, mid + 1, right ); merge (a, left , mid , right ); } private static void merge( int [] a, int left , int mid , int right ){ int [] tmp = new int [a. length ]; int r1 = mid + 1; int tIndex = left ; int cIndex = left ; // 逐个归并 while ( left <= mid && r1 <= right ){ if (a[ left ] <= a[ r1 ]) tmp [ tIndex ++] =a[ left ++]; else tmp [ tIndex ++] =a[ r1 ++]; } // 将左边剩余的归并 while ( left <= mid ){ tmp [ tIndex ++] =a[ left ++]; } // 将右边剩余的归并 while ( r1 <= right ){ tmp [ tIndex ++] =a[ r1 ++]; } System. out .print( "第" +(++ number )+ " 次排序:" ); // 从临时数组拷贝到原数组 while ( cIndex <= right ){ a[ cIndex ]= tmp [ cIndex ]; // 输出中间归并排序结果 System. out .print( a[ cIndex ]+ "" ); cIndex ++; } System. out .println(); } 运行结果截屏: 算法分析:合并排序满足分治法的基本公式 T(n)=2T(n/2)+f(n) 其中 2T(n/2) 是2 个子问题求解,即对两个子数组排序; 而 f(n) 是将子问题合起来求原始问题的解的代价, 即将两个有序的子数组合并为一个有序的数组。在最终的合并阶段, 键值的比较的代价, 在最坏的情况下是 n-1 ,( 比如每个数组的第 i 号轮流被放入数组),根据主定理, T(n)=O(nlogn) 。 b. 0-1 背包问题问题描述:在0/1 背包问题中, 需对容量为 W 的背包进行装载。从 n 个物品中选取装入背包的物品, 每件物品 j 的重量为 wj, 价值为 vi 。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。有3 中方法可解: 动态规划法: 递推式: K(w,j)=max{K(w-wj, j-1)+vj, K(w,j-1)} w≥ wj K(w,j)=K(w,j-1) w< wj 初始条件: K(0,j)=0, K(w, 0)=0. 初始化条件表示把前面i 个物品装入容量为0 的背包和把0 个物品装入容量为 j 的背包,得到的价值均为 0。第二个式子说明: 如果第 i 个物品的重量大于背包的容量, 则装入第i 个物品得到的最大价值和装入第 i-1 个物品得到的最大价值是相同的,即物品 i 不能装入背包中。第一个式子说明: 如果第 i 个物品的重量小于背包的容量, 则会有两种情况:( 1 )如果把第 i 个物品装入背包,则背包中物品的价值就等于把前 i-1 个物品装入容量为 iwj 的背包中的价值加上第i 个物品的价值 iv;(2 )如果第 i 个物品没有装入背包,则背包中物品的价值就是等于把前 i-1 个物品装入容量为 j 的背包中所取得的价值。显然, 取二者中价值较大者作为把前 i 个物品装入容量为 j 的背包中的最优解