实验2. 动态规划法求解最长公共子序列问题与0-1背包问题.doc

动态规划法求解最长公共子序列问题与0-1背包问题 本实验报告旨在通过动态规划法解决最长公共子序列问题和0-1背包问题，以深入理解动态规划方法的思想、求解策略及步骤。 实验目的 * 理解动态规划方法的核心思想和求解过程 * 从算法分析与设计的角度，对基于DP法求解问题的理解 实验步骤 步骤 1：理解问题，给出问题的描述。 步骤 2：算法设计，包括策略与数据结构的选择 步骤 3：描述算法，可以采用伪代码、流程图等形式。 步骤 4：算法的正确性证明，需要在理解的基础上对算法的正确性给予证明。 步骤 5：算法复杂性分析，包括时间复杂性和空间复杂性。 步骤 6：算法实现与测试，附上代码或以附件的形式提交，同时贴上算法运行结果截图。 步骤 7：技术上、分析过程中等各种心得体会与备忘，需要言之有物。 最长公共子序列问题 最长公共子序列问题的描述：对于给定的两个序列 X 和 Y，找出 X 和 Y 的一个最长公共子序列。 算法设计：采用一个结点对象存储最优值和最优值的来源。采用二维数组来存放各个子问题的最优值，并记录其来源。 算法描述： ``` LCSLength ( x[m],y[n],a[m+1][n+1] ) for i=0 to m do a[i][0] = 0 for j=0 to n do a[0][j] = 0 for i=1 to m do for j=1 to n do if x[i]= y[j] then a[i][j].value = a[i-1][j-1].value+1 a[i][j].mark = 3 else if x[i] != y[j] then if (a[i][j-1].value > a[i-1][j].value ) then a[i][j].value = a[i][j-1].value a[i][j].mark = 2 else a[i][j].value = a[i-1][j].value a[i][j].mark = 1 ``` 算法的正确性证明：设序列 X={x1,x2,…,xm}和 Y={y1,y2,…,yn}的最长公共子序列为 Z={z1,z2,…,zk}，则： * 若 xm==yn，则 zk==xm==yn，而且 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列。 * 若 xm≠yn 且 zk≠xm，则 Z 是 Xm-1 和 Y 的最长公共子序列。 * 若 xm≠yn 且 zk≠yn，则 Z 是 X 和 Yn-1 的最长公共子序列。 0-1背包问题 （略） 实验结果 在这个实验报告中，我们通过动态规划法解决了最长公共子序列问题和0-1背包问题，并对算法的正确性进行了证明。实验结果表明，动态规划法可以有效地解决这两个问题。 实验总结 通过这次实验，我们深入理解了动态规划方法的思想、求解策略及步骤，并对基于DP法求解问题的理解。同时，我们也掌握了算法设计、算法描述、算法正确性证明、算法复杂性分析和算法实现等技术。