西电软件学院算法实验报告

《西电软件学院算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第二次试验一、问题：Matrix-chainproduct分析：本题是矩阵链乘问题，需要求出最优括号化方案。即在矩阵的乘法链上添加括号来改变运算顺序以使矩阵链乘法的代价降低。可以分析该链乘的一个子段总结一些结论。假设m[i,j]表示Ai*…*Aj的链成需要进行的乘法次数（假设j-i足够大），我们可以将Ai*…*Aj分为两段进行计算：（Ai*…*Ak）*（Ak+1*…*Aj）可以得出m[i,j]的递推公式可以得出，当i=j的时候，m[i,j]=0。当i

2、最小值即时m[i,j]的最优化方案。递推公式如下：可以根据上式得到一个递归算法。本题即是求m[1,n]的值。用二维数组m存储m[i,j]的值，用二维数组s来储存应当分割的位置。以本题中第一个矩阵a)<3,5,2,1,10>为例，可以得出如下矩阵：8通过m数组可以得出最少的乘法次数，通过s数组可以输出最优方案。遇到的问题：在输出s数组的结果的时候仍然需要递归调用，需要合适的控制递归的条件。总结：在矩阵链乘问题中可以看出，动态规划结合递归的思想可以快捷的解决很多问题。本题中，重点是归纳出m[i,j]的递推公式。一、问题：LongestCommo

3、nSubsequence分析：本题即是最长公共子序列问题。假设有序列A[m]和序列B[n]，显然，对于每一个[i,j]，都对应着一个公共子序列的长度。假设长度为c，就可以得到一个二维数组c[m,n]。对于c[i,j]，当Ai=Bj的时候，问题就转变为求A[1..i-1]和B[1..j-1]的公共子序列长度的问题，所以c[i，j]的长度就是c[i-1，j-1]+1;同理，当Ai!=Bj的时候，c[i,j]应该在c[i-1,j]与c[i,j-1]中取最大值。另外，当i或者j等于0的时候，显然c的值为0。由上面所述，可以得到递推公式如下：为了解决

4、这个问题，还如要定义另一个数组用于存放c数组中每一个元素的来源。这个来源其实就反映了公共子串。可以通过箭头表示来源，相连的箭头序列中指向左上方的箭头最多的一串对应的就是最长公共子序列。比如对于题目中给出的第一个例子X:xzyzzyxY:zxyyzxz可以用一个矩阵表示计算的过程：遇到的问题：8在算法中，‘=’是属于‘<’还是‘>’会给结果带来不同。在输出子序列的时候，最长公共子序列可能不止一个，但是最终未能解决还是只能输出一个。总结：最长公共子序列问题可以利用动态规划很好的解决。动态规划的思想就是根据规律获得推导公式，然后解决问题。一、问题

5、：LongestCommonSubstring分析：最长公共子序列问题就是和最长公共子串问题差不多，就是当当Ai!=Bj的时候，对应的c[i，j]置为0。推导公式如下：最终c数组的最大值max对应的就是最长公共子串，只需要将从本位置向前述max-1个的子串即是所求子串。总结：本题就是第二题的一种特殊的情况，即c数组中的值不能从左和上两个方向获取，其他基本相同。在代码上，只需要修改小部分代码就可以实现该问题。二、问题：MaxSum分析：求和最大的子串。这个问题和第三题很像，不过这次不用二维数组而是使用两个标记来标志所求子串的起始位置（maxb

6、）结束位置（maxe）。思路是，对于第i个元素，如果当前元素与目前选中的序列的sum小于0，那么这么序列不会被选择，更新sumb与sume的值；如果sum仍然大于0，则sum可以选中。比较sum与max的值，如果sum>max，则更新maxb与maxe的值。递推公式如下：8遇到的问题：在全是负数时出现问题，后来讲max的初始值设置为第一个元素的值后就能正常了。总结：动态规划能解决很多问题，找到递推公式非常重要。一、问题：Shortestpathinmultistagegraphs.Findtheshortestpathfrom0to15fo

7、rthefollowinggraph.分析：观察本题图的特点，发现可以将图分解为7个部分，以此可以计算到每一个节点的最短的路径。即可求出最终的最短路径。总结：结合本题中的特殊情况，可以采用适当的方法来处理。第三次实验一、问题：8KnapsackProblem.Thereare5itemsthathaveavalueandweightlistbelow,theknapsackcancontainatmost100Lbs.Solvetheproblembothasfractionalknapsackand0/1knapsack.分析：本题是背包

8、问题的两个解法。对于部分背包来说比较简单，就是将单位价值大的物品优先放置到背包中，这样就能在背包中获取最大的价值。但是对于0/1背包问题来说，就相对复杂了。可以通过贪心算法解决。