算法导论上机报告
算法导论
上机报告
班级： 1313012 学号： 131********
姓名：黄帮振
实验编号 1 题目1 归并排序算法
实验内容描述一个运行时间为θ(nlgn)的算法 给定n个整数的集合S和另一个整数x 该算法能确定S中是否存在两个其和刚好为x的元素。
实验
目的
用分治思想，设计子问题，实现归并排序算法；
报告正文
一、算法分析
1、运用归并排序算法
归并排序运用的是分治思想，时间复杂度为θ(nlgn)能够满足题目要求的运行时间。归并排序的分解部分是每次将数组划分两个部分，时间复杂度为θ（1）再对已经分解的两个部分再进行分解直到将数组分解成单个元素为止。解决部分是递归求解排序子序列，合并部分是将已经排序的子序列进行合并得到所要的答案，时间复杂度为θ(lgn)。
2、在已经排好序的基础上，对其运用二分查找
二分查找算法的时间复杂度为θ(lgn)在题目要求的范围内，二分查找的条件为待查的数组为有序序列。算法的主要思想为设定两个数 low指向最低元素 high指向最高元素，然后比较数组中间的元素与待查元素进行比较。如果待查元素小于中间元素，那么表明查找元素在数组的前半段，反之，如果待查元素大于中间元素，那么表明查找元素在数组的后半段。
二、伪代码：
MERGE(A,p,q,r)
1.n1=q-p+1
2.n2=r-q
3.Let L[1..n1+1]andR[1..n2+1]be new arrays
4.For i=1 to n1
5. L[i]=A[p+i-1]
6.For j=1 to n2
7. R[j]=A[q+j]
8.L[n1+1]=无穷
9.R[n2+1]=无穷
10.I=1
11.J=1
12.For k=p to r
13. If L[i]<=R[j]
14. A[k]=L[i]
15. I=i+1
16. Else A[k]=R[j]
17. J=j+1
MERGE-SORT(A,p，r)
1、if p 2、 q=(p+r)/2(取下限) 3、 MERGE-SORT（A,p,q） 4、 MERGE-SORT(A,q+1,r) 5、 MERGE(A,p,q,r) 三、实验总结 在主函数中调用二分查找的时候，参数应该为BinSearch(a,j+1,n,x-a[j]）从j+1开始遍历而不是都是从第一个开始。在程序中由于程序语言规定数组的下标从0开始而算法伪代码要求从1开始，因此在定义数组大小的时候将数字加1，但是在编译运行的时候会得不到想要的结果，出现数组下标访问错误。 实验编号 1 题目2 优先队列排序 实验内容实现优先队列排序算法，需要支持以下操作： INSERT(S,x):把元素x插入到集合S中 MAXMUM(S):返回S中具有最大key的元素 EXTRACT-MAX(S):去掉并返回S中的具有最大key的元素 INCREASE-KEY(S,x,k)：将元素x的关键字值增到k。 实验 目的 堆排序，运用堆来实现优先队列。 报告正文 一、算法原理 1、堆排序算法是引用堆这个数据结构进行信息管理。堆排序的时间复杂度是θ(nlgn),但是与归并排序不同的是堆排序具有空间的原址性，任何时候都只需要常数个额外的元素空间存储临时数据。堆排序算法分为3个过程MAX-HEAPIEY:调整堆以满足小顶堆性质其时间复杂度为θ(lgn)；BUILD-MAXHEAP:从无序的输入数据数组中构造小顶堆，其时间复杂度为线性时间;HEAP-SORT:对数组进行原址排序，其时间复杂度为θ(nlgn)。 2、在堆的基础上实现优先队列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY时间复杂度为θ(lgn)。 二、伪代码 BUILD-MAX-HEAP(A) 1.A.heap-size=A.length 2.For i=A.length/2(取下限) downto 1 3.MAX-HEAPIFY（A，i） HEAPSORT（A） 1.Build-MAX-HEAP（A） 2.For i=A.length downto 2 3.Exchange A[1] with A[i] 4.A.heap-size=A.heap-size - 1 5.MAX-HEAPIFY(A,1) HEAP-MAIMUM(A) 1.return A[1] HEAP-EXTRACT-MAX(A) 1.if A.heap-size<1 2. Error “heap underflow” 3.Max=A[1] 4.A[1]=A[A.heap-size] 5.A.heap-size=A.heap-size - 1 6.MAX-HEAPIFY(A,1) 7.Return max HEAP-INCREASE-KEY(A,i,key) 1.if key 2.Error “new key is smaller than current key” 3.A[i]=key 4.While i>1 and A[PARENT(i)] 5. Exchange A[i] with A[PARENT(i)] 6. I=PARENT(i) MAX-HEAP-INSERT(A,key) 1.A.heap-size=A.heap-size + 1 2.A[A.heap-size]=负无穷 3.HEAP-INCREASE-KEY(A,A.heap-size,key) 三、实验总结 一开始没有理解将一个序列转换成小顶堆的过程，在编写MAX-EXSTRACT函数的时候，当去掉第一个元素后，程序并没有调用MAX-HEAP进行调整堆，因此最后序列是无序状态。 实验编号 1 题目3 快速排序算法 实验 实现快速排序算法。 内容 实验 使用Java实现插入排序算法。 目的 报告正文 快速排序采用分治策略，时间复杂度为θ(nlgn),但是最坏情况下为θ(n2),并且快速排序算法属于原地排序，并不需要开辟空间。快速排序复杂的步骤为其分解的步骤 分解的过程 数组A[p..r]被划分为两个子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于A[q],而A[q]也小于等于A[q+1..r]中的每个元素。而在实现的过程总是选择将A[r]作为基准点进行划分A[p..r]数组。 二、伪代码 QUICKSORT(A，p，r) 1 if p < r 2 q = PARTITION(A，p，q) 3 QUICKSORT(A，p，q-1) 4 QUICKSORT(A，q+1，r) PARTITION(A，p，r) 1 x = A[r] 2 i = p-1 3 for j = p to r-1 4 if A[j] x 5 i = i+1 6 exchange A[i] with A[j] 7 exchange A[i+1] with A[r] 8 return i + 1 三、实验总结 问题答案：当选取第一个或者最后一个为基准点时，当n个元素相同的时候为最坏情况 比较次数为n*(n-1)/2；快速排序比较次数最少为θ(nlgn),,最大的比较次数为θ(n2)。 实验编号 1 题目4 用分治算法实现题目要求的时间复杂度运算 实验内容运用分治的策略将两个已经排好序的序列中，找出第k大的元素 且要求时间复杂度为θ(lgm+lgn),其中m和n分别为两个序列的长度。 实验 目的 用分治算法实现题目要求。 报告正文 如果K是中位数，则（M＋n）是奇数还是偶数是有关系的。如果是奇数，那么中位数唯一，如果是偶数就有两个中位数，可以随便取一个。如果找到的第K大数是x，假如在A的位置是A(x)，在B中的位置是B(x)，则Ax+Bx-1=k是成立的。 接下来是具体实现逻辑： 1、首先假设K大数在A数组中，首先检查(m/(m+n))*(k-1)，假设其值为A1。然后检查B中 (k+1-(n/(m+n))*(k-1))假设为B1，检查A1、B1是否相等，或者大于B中的第(k+1-(n/(m+n))*(k-1))，并且小于(k+1-(n/(m+n))*(k-1))+1个元素。满足条件就可以知道A1就是所求，否则看条件2。 2、如果两个条件都不满足，那么需要判断第K个元素是位于A1左边还是右边。如果A1>B1，那么K肯定不在A[0, (m/(m + n)) * (k - 1)]以及B[(k + 1 - (m/(m + n)) * (k - 1))+ 1, n]中； 如果A1 1))]中。第K个元素有可能在B中，同理可以假设在B中，再进行一次搜索。复杂度log(m)+log(n)。 二、伪代码 Searchkth（A,B,alow,ahigh,blow,bhigh,k） 1.amid=(alow+ahigh+1)/2 2.bmid=(blow+bhigh+1)/2 3.If alow>ahigh 4. return B[blow+k-1] 5.If blow>bhigh 6. return A[alow+k-1] 7.If A[amid]<=B[bmid] 8.If A[amid]<=B[bmid] 9. If k<= amid-alow+bmid-blow+1 10. Return Searchkth(A,B,alow,ahigh,blow,bmid-1,k) 11. Else 12. Return Searchkth(A,B,amid+1,ahigh,blow,bhigh,k-(amid-alow)-1) 13.Else 14. If k<= amid-alow+bmid-blow+1 15. Return Searchkth(A,B,alow,amid-1,blow,bhigh,k) 16. Else 17. Return Searchkth(A,B,alow,ahigh,bmid+1,bhigh,k-(bmid-blow)-1) 三、实验总结 理解分治策略的三个步骤：分解、解决和合并对于具体问题的具体表现，要善于根据时间复杂度与所学的算法进行结合，找出可以利用的地方。 实验编号 2 题目1 矩阵链乘 实验 用动态规划实现矩阵链乘，保证相乘的次数最少。 内容 实验 用动态规划实现矩阵链乘 目的 报告正文 一、算法原理 1 最优子结构为：如果最优的加括号的方式将其分解为Ai..k与Ak+1..j的乘积 则分别对Ai..k与Ak+1..j加括号的方式也一定是最优的。 2 定义m[i,j]为计算矩阵Ai..j所需标量乘法次数的最小值，对于i=j时,矩阵链乘只包含唯一的矩阵Ai,因此不需要做任何标量乘法运算，所以m[i,i]=0;当i 3 矩阵链乘的递归式 4 在算法设计的时候 需要m数组记录Ai..j最小相乘次数，s数组记录构造最优解所需要的信息，其记录的k值指出了AiAi+1Aj的最优括号化方案的分割点应在AkAk+1之间。 5 矩阵链乘的时间复杂度为θ(n3) 二、伪代码 MATRIX-CHAIN-ORDER（p） 1.n=p.length-1 2.Let m[1..n,1..n] and s[1..n-1,2..n] be new tables 3.For i=1 to n 4. M[i,i]=0 5.for l=2 to n 6. For i=1 to n-l+1 7. J=i+l-1 8. M[i,j]=无穷 9. For k=i to j-1 10. Q=m[i,k]+m[k+1,j]+p(i-1)*p(k)*p(j) 11. If q 12. M[i,j]=q 13. S[i,j]=k PRINT-OPTIMAL-PARENS(s,i,j) 1.if i==j 2. Print “A” 3.Else print “(” 4. PRINT-OPTIMAL-PARENS(s,i,s[i,j]) 5. PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j) 6. Print “）” 三、实验总结 矩阵链乘主要运用动态规划的思想，这种思想的重要之处在于找到最优的子结构，并设计出最优解的形式。编程是并未遇到什么问题，过程较为顺利。 实验编号 2 题目2 最长公共子序列 实验 用动态规划求下列字符串的最长公共子序列。 内容 实验 用动态规划实现寻找最长公共子序列算法。 目的 报告正文 一、算法原理 1 最优子结构：令X= 2 定义一个b[i,j]指向表项对应计算c[i,j]时所选择的子问题最优解，过程返回表b和表c，c[m,n]保持X和Y的LCS长度。 3 LCS的递归式为 4 LCS的时间复杂度为θ(m+n),b表的空间复杂度为θ(mn)。 二、伪代码 LCS-LENGTH（X,Y） 1.m=X.length 2.n=Y.length 3.Let b[1..m,1..n] and c[0..m,0..n] be new tables 4.For i=1 to m 5. c[i,0]=0 6.For j=0 to n 7. c[0,j]=0 8.For i=1 to m 9. For j=1 to n 10.If xi==yj 11. c[i,j]=c[i-1,j-1]+1 12. b[i,j]=1 13.Else if c[i-1,j]>=c[i,j-1] 14. c[i,j]=c[i-1,j] 15. b[i,j]=2 16.Else c[i,j]=c[i,j-1] 17. b[i,j]=3 18.return ； PRINT-LCS(b,X,i,j) 1.if i==0 or j==0 2. Return ; 3.If b[i,j]==1 4. PRINT-LCS(b,X,i-1,j-1) 5. Print xi 6.Elseif b[i,j]==2 7.PRINT-LCS(b,X,i-1,j) 8.else PRINT-LCS(b,X,i,j-1) 三、实验总结 用动态规划求取最长公共子序列的时候，要理解b数组的用途和使用。一开始编程时将输入的字符串转化为字符出现问题，后来使用charAt（）函数解决了问题。 实验编号 2 题目3 最长公共子串 实验 用动态规划求取以下字符串的最长公共子串。 内容 实验 用动态规划实现最长公共子串算法 目的 报告正文 一、算法原理 1 最优子结构 令X= 2 定义L[i,j]为以x[i]和y[j]为结尾的相同子串的最大长度，记录着X和Y的最长公共子串的最大长度。 3 最长公共子串的递归式 4 最长公共子串的时间复杂度为θ(mn)，空间复杂度为θ(mn)。 二、伪代码 getLCString(str1,tr2) len1 = str1.length; len2 = str2.length; maxLen = len1 > len2 ? len1 : len2; int[] max = new int[maxLen]; int[] maxIndex = new int[maxLen]; int[] c = new int[maxLen]; Let max[0..maxlen-1],maxindex[0..maxlen-1] and c[0..maxlen-1] be new tables For i = 0 to len2 for j = len1 - 1 to 0 if str2[i] == str1[j] if i == 0 or j == 0 c[j] = 1; else c[j] = c[j - 1] + 1; else c[j] = 0; if c[j] > max[0]) max[0] = c[j]; maxIndex[0] = j; for k = 1to maxLen max[k] = 0; maxIndex[k] = 0; else if c[j] == max[0] for k = 1 to maxLen if max[k] == 0 max[k] = c[j]; maxIndex[k] = j; for j to maxLen if max[j] > 0 Print j + 1 for i = maxIndex[j] - max[j] + 1 to maxIndex[j] Print str1[i] 三、实验总结 要同上述的最长公共子序列进行对比 区分他们的不同之处。也要理解用动态规划求解时的相同之处和不同之处。 实验编号 2 题目4 最大子段和 实验内容给定n个整数（可能为负数）组成的序列a[1],a[2]...a[n],求该序列a[i]+a[i+1]...a[j]的子段和的最大值。 实验 目的 用动态规划实现数列的最大和 报告正文 一、算法原理 1 最优子结构：定义当所给整数全为负数的时候，最大子段和为0,则最大子段和为max{0,a[i]+a[i+1]...+a[j]},1≤i≤j≤n 2 引入一个辅助数组b,动态规划的分解分为两步：(1)计算辅助数组的值；(2)计算辅助数组的最大值。辅助数组b[j]用来记录以j为尾的子段以及集合中的最大子段和。 3 最大子段和的递归式 4 最大子段和使用动态规划进行计算的时间复杂度为θ(n)。 二、伪代码 Maxsum（A） 1.sum=0 2.temp=0 3.B[1..A.length]=arraycopy(A) 4.For i=0 to B.length 5.If B[i]>0 6. Sum=B[i] 7. Break 8.for j=i+1 to B.length 9. If B[j]>0 10. For a=i to j 11. temp=temp+b[a] 12. If temp>sum 13. sum=temp 14.print max 三、实验总结 对比比较了动态规划和分治法的不同，感受到用动态规划解决的便捷。 实验编号 2 题目5 最短路径问题 实验 解决多级图中的最短路径问题 内容 实验 用动态规划解决多级图中的最短路径问题 目的 报告正文 一、算法原理 1 可以由图可知，图中的顶点讲图划分7个阶段，分别了解每个阶段可以有几种可供选择的点，引入f[k]表示状态k到终点状态的最短距离。最优子结构为当前状态的f[k]由上个状态的f[k-1]和状态k-1到状态k的距离决定决策：当前状态应在前一个状态的基础上获得。决策需要满足规划方程,规划方程f(k)表示状态k到终点状态的最短距离。 2 多段图最短路径的递归式 二、伪代码 Shortestpath let indexs [0..W1[0].length],isLabel [0..W1[0].length] be a new table i_count = -1 distance = W1[start] index = start presentShortest = 0 indexs[++i_count] = index; isLabel[index] = true; while i_count min = Integer.MAX_VALUE; for i = 0 to distance.length if !isLabel[i] and distance[i] != -1 and i != index if distance[i] < min min = distance[i] index = i if index == end break; isLabel[index] = true indexs[++i_count] = index if W1[indexs[i_count - 1]][index] == -1 or presentShortest + W1[indexs[i_count - 1]][index] > distance[index] presentShortest = distance[index]; else presentShortest += W1[indexs[i_count - 1]][index]; for i = 0 to distance.length if distance[i] == -1 and W1[index][i] != -1 distance[i] = presentShortest + W1[index][i]; else if W1[index][i] != -1 and presentShortest + W1[index][i] < distance[i]) distance[i] = presentShortest + W1[index][i]; return distance[end] - distance[start]; 三、实验总结 遇到的问题：无法将多段图的每个阶段点的状态表示并记录下来。并不了解如何将动态规划与贪心算法的如迪杰斯特拉算法进行对比，真正从最优子结构将最短路径表示出来。 实验编号 3 题目1 分数背包问题和0/1背包问题 实验 解决分数背包和0/1背包问题 内容 实验 分别用贪心算法和动态规划实现分数背包问题和0/1背包问题 目的 报告正文 一、算法原理 1 0-1背包问题：选择n个元素中的若干个来形成最优解，假定为k个。对于这k个元素a1, a2, ...ak来说，它们组成的物品组合必然满足总重量<=背包重量限制，而且它们的价值必然是最大的。假定ak是我们按照前面顺序放入的最后一个物品，它的重量为wk，它的价值为vk。前面k个元素构成了最优选择，把ak物品拿走，对应于k-1个物品来说，它们所涵盖的重量范围为0-(W-wk)。假定W为背包允许承重的量，最终的价值是V，剩下的物品所构成的价值为V-vk。这剩下的k-1个元素构成了W-wk的最优解。 2 分数背包问题：所选择的的贪心策略为按照选择单位重量价值最大的物品顺序进行挑选。算法的步骤：设背包容量为C 共有n个物品 物品重量存放在数组W[n]中 价值存放在数组V[n]中 问题的解存放在数组X[n]中。第一步，改变数组W和V的排列顺序使其按单位重量价值V[i]/W[i]降序排列，并将数组X[n]初始化为0；第二步初始化i=0，设计一个循环，循环终止条件为W[i]>C，循环体为将第i个物品放入背包，X[i]=1;C=C-W[i];i++最后一步将结果存入到X数组中X[i]=C/W[i]。 3 分数背包问题采用选择单位重量价值最大的物品顺序进行挑选，其算法的时间复杂度为θ(nlgn)。 4 背包问题的递归式: f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 二、伪代码 Knapsack01（v,w,weight） 1.n=w.length 2.let c[0..n,0..weight] be a new table 3.For i=0 to n 4. c[i,0]=0 5.For j=1 to weight 6. c[0,j]=0 7.For i=1 to n 8. For j=1 to weight 9. If(j 10. c[i,j]=c[i-1,j] 11. Else 12. If c[i-1,j]>(c[i-1,j-w[i-1]]+v[i-1]) 13. c[i,j]=c[i-1,j] 14. Else 15. c[i,j]=c[i-1,j-w[i-1]]+v[i-1] KnapsackFra(weight,v,w) 1.vw[0..v.length] 2.For i=0 to v.length 3. vw[i]=v[i]/w[i] 4.c=weight 5.sum=0 6.temp=0 7.While c>0 8. temp=0 9. For i=0 to v.length 10. If vw[i]>temp 11. temp=vw[i] 12.For i=0 to i 13. If temp==vw[i] 14. Break 15.If c-w[i]>0 16. sum=sum+v[i] 17. c=c-w[i] 18. vw[i]=0 19.Else 20. sum=sum+c*vw[i] 21. c=c-c 22. vw[i]=0 23.Print sum 三、实验总结 分数背包问题所采用的贪心策略之不能得到最优解是由于物品不允许分割，因此无法保证最终能将背包装满，部分闲置的背包容量使背包的单位重量价值降低了。 实验编号 3 题目2 简单的调度问题 实验内容给予工作编号为J1、J2...Jn，已知其工作的运行时间分别为T1、T2...TN。有一个单独的处理器，为了安排这些工作以到达减少平均完成时间的最好方法是什么。假定它是一个非抢占式调度，一旦工作开始，它必须运行完成。 实验 安排进程的先后次序使得等待时间最短。 目的 报告正文 一、算法原理 由于是非抢占式调度，所以应该尽量让时间短的工作先做，然后再让时间长的工作做。这里我们使用快速排序，快速排序的时间复杂度是O(nlgn)，然后将前n-1项工作时间相加，计算出平均完成时间 二、伪代码 Schedule(A) 1.Let time[0..A.length-1] be a new table 2.Quicksort(time,0,time.length-1) 3.Sum=0 4.For i=0 to time.length-1 5.Sum+=time[i] 6. Print time[i] and sum/(n-1) 三、实验总结 注意sum除的是n-1而不是n。 实验编号 3 题目3 单源最短路径 实验 以A为源点，按照矩阵所给的长度，设计单源最短路径 内容 实验 用Bellman-Ford实现单源最短路径问题 目的 报告正文 一、算法原理 Bellman-Ford算法通过对边进行松弛操作来渐近地降低从源点A到每个结点的最短路径的估计值，直到该估计值与实际的最短路径权重相同为止。该算法返回TRUE值当且仅当输入图中不包含可以从源结点到达的权重为负值的环路。 Bellman-Ford算法的执行步骤： 1、初始化：将除源点外的所有顶点的最短距离估计值d[v]←+∞, d[s]←0；2、迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离，运行|v|-1次；3、检验负权回路，判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false表明问题无解，否则算法返回true并且从源点可达的顶点v的最短距离保存在d[v]中。 二、伪代码 Bellman-Ford(G,w,s) 1.d[s]=0 2.Bound=正无穷 3.For i=0 to G.length 4. For j=0 to G[0].length 5. If g[i,j]==0 6. Graph[i,j]=bound 7. Else 8. Graph[i,j]=G[i,j] 9.For each v∈V-{A} 10. If graph[0,i]>graph[0,k]+graph[k,i] 11. Graph[0,i]=graph[0,k]+graph[k,i] 12.For each v∈V-{A} 13. if Graph[0,i]>graph[0.k]+graph[k,i] 14. Retrun false 15.Return true 三、实验总结 基本能将Bellman-Ford算法写出来，但是二维数组的行列长度的表示，还须分开，否则会出现数组越界的问题。实现单元路径最短算法，最重要的是从一点出发经过或者不经过多个点都要遍历，进行比较才能的出最后的结果。 实验编号 3 题目4 全结点最短路径算法 实验 利用Floyd-Warshall算法计算所给矩阵的全结点最短路径 内容 实验 实现Floyd-Warshall算法 目的 报告正文 一、算法原理 设G的顶点为V={1,2,3...n} 对于任意一对顶点i,j属于V，假设i到j有路径且中间节点皆属于集合{1,2,3...k}，P是其中的一条最小权值路径。就是i到j的最短路径P 所通过的中间顶点最大不超过k。设d(k)ij为从结点i到结点j的所有中间结点全部取自结合{1,2,...,k}的一条最短路径的权重。D(k)ij的递归定义为 D(k)ij= wij if k=0 = min(d(k-1)ij,d(k-1)ik+d(k-1)kj) if k>=1 Floyd-Warshall算法的时间复杂度为θ(v3)。 二、伪代码 FloydWarshall(G) 1.for each v∈V 2. If i==j 3. Graph[i,j]=0 4. Elseif G[i,j]==0 5. Graph[i,j]=正无穷 6. Else 7. Graph[i,j]=G[i,j] 8.n=graph.length 9.For each v∈V 10. if Graph[i,j]>graph[i,k]+graph[k,j] 11. Graph[i,j]=graph[i,k]+graph[k,j] 三、实验总结 相比单源结点路径，全结点路径遍历的次数要倍增，但是算法实现的原理还是考察经过多个结点路径的变化。 实验编号 4 题目1 回溯法解决背包问题 实验 使用回溯算法解决背包问题 内容 实验 使用回溯算法解决背包问题 目的 报告正文 一、算法原理 利用回溯法求解首先是要确定约束函数，根据0-1背包问题的特点，由于背包的容量是确定，因此背包问题中第k个物品的取舍要取决于放入后是否超过背包的容量。即 C1..k-1+ wk<= W(其中C1..k表示已经决定好前k-1物品的取舍后当前背包的重量，wk 为第k件物品的容量，W为背包的容量) ；为了求出最优解，从而确定求解的限界条件。为了能达到最大的价值，不超过背包容量的前提下，通过计算只放入一部分第k物品来计算最大的价值，要确保当前的选择的最大价值大于已经选择的价值，此为限界条件。 二、伪代码 BackTrace(i,nv,nw,v,w,weight) 1.n=bestx.length 2.If i==n 3. If nv>bestval 4. Bestval=nv 5. For k=0 to n 6. Bestx[k]=x[k] 7.Else 8. For j=0 to 1 9. X[i]=j 10. If nw+w[i]*x[i]<=weight 11. Nw=nw+w[i]*x[i] 12. Nv=nv+v[i]*x[i] 13. BackTrace(i+1,nv,nw,v,w,weight); 14. Else 15. Bestval=nv 16. For k=0 to i 17. Bestx[k]=x[k] KnapsackBack(v,w,weight) 1.let bestx[0..v.length-1]and X[0..v.length] be new tables 2.Bestval=0 3.BackTrace(0,0,0,v,w,weight) 三、实验总结 在每一次迭代时，要把每种情况都罗列出来，并将其去向用if-else语句表达出来，少写一种情况会导致最后的结果出不来或者发生错误。回溯算法最难的是迭代环节，此次编程后对于回溯算法稍有了解。 实验编号 4 题目2 9-Queen问题 实验 设计一个算法是的在同一棋盘上的8个皇后不发生冲突 内容 实验 使用回溯算法设计8-Queen的算法 目的 报告正文 一、算法原理 利用回溯法求解8-queen问题，即确定每个queen在每一行的位置，首先确定约束条件，要求每个queen不能再同一行，同一列和同一对角线上引入queen[i],记录第i行的列数，由于两个queen不能再同一列，因此数组中没有相同的值，而对于判断是否在同一对角线上的条件为:假设两个queen的坐标位置分别为(i,j),(k,h),当且仅当|i-k|=|j-h|时才确定两个queen在同一对角线上。 回溯的过程：不断检索该行能够存放的位置，先从第一行第一列开始检查，如果不能放置，接着检查该行第二个位置，依次检查下去，直到在该行找到一个可以放置一个皇后的地方，然后保存当前状态 转到下一行重复上述方法的检索。如果检查了该行所有的位置均不能放置一个皇后，说明上一行皇后放置的位置无法让所有的皇后找到自己合适的位置，因此就要回溯到上一行，重新检查该皇后位置后面的位置。 二、伪代码 X[0..8]=0 Place(k)//判断皇后的位置是否冲突 1.For i=1 to k 2. If x[i]==x[k]||abs(k-i)==abs(x[k]-x[i]) 3. Return false 4.Return true BackTrace() 1.n=x.length//解的长度 2.k=1 3.While k>=1 4.Do 5. X[k]=x[k]+1 6. While x[k] 7. Do 8. X[k]=x[k]+1 9. If x[k] 10. For i=1 to n 11. Printx x[i] 12. Elseif k<(n-1)&&x[k] 13. K=k+1 14. Else//出现这行的皇后无地方可放,需要回溯 15. X[k]=0 16. K=k-1 三、实验总结 在遍历时，监察冲突位，应该从下标为1的值开始检查，如果从0下标的值开始，结果会缺失一部分，这与设计者的想法有关，设计从1开始摆放皇后的话，须从上述位置开始检查。