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

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

第1页 / 共10页

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

第2页 / 共10页

qq_41037660-12139374-实验2. 动态规划法求解最长公共子序列问题与0-1背包问题.doc.pdf-第3页.png

第3页 / 共10页

qq_41037660-12139374-实验2. 动态规划法求解最长公共子序列问题与0-1背包问题.doc.pdf-第4页.png

第4页 / 共10页

qq_41037660-12139374-实验2. 动态规划法求解最长公共子序列问题与0-1背包问题.doc.pdf-第5页.png

第5页 / 共10页

qq_41037660-12139374-实验2. 动态规划法求解最长公共子序列问题与0-1背包问题.doc.pdf-第6页.png

第6页 / 共10页

qq_41037660-12139374-实验2. 动态规划法求解最长公共子序列问题与0-1背包问题.doc.pdf-第7页.png

第7页 / 共10页

qq_41037660-12139374-实验2. 动态规划法求解最长公共子序列问题与0-1背包问题.doc.pdf-第8页.png

第8页 / 共10页

实验 2. 动态规划法求解最长公共子序列问题&0-1 背包问题实验内容本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试），在针对最长公共子序列问题和 0-1 背包问题求解的实践中理解动态规划方法的思想、求解策略及步骤。实验目的  理解动态规划方法的核心思想以及动态规划方法的求解过程；  从算法分析与设计的角度，对基于 DP 法求解有更进一步的理解。环境要求对于环境没有特别要求。对于算法实现，可以自由选择 C, C++, Java，甚至于其他程序设计语言。实验步骤步骤 1：理解问题，给出问题的描述。步骤 2：算法设计，包括策略与数据结构的选择步骤 3：描述算法。希望采用源代码以外的形式，如伪代码、流程图等；步骤 4：算法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给予证明；步骤 5：算法复杂性分析，包括时间复杂性和空间复杂性；步骤 6：算法实现与测试。附上代码或以附件的形式提交，同时贴上算法运行结果截图; 步骤 7：技术上、分析过程中等各种心得体会与备忘，需要言之有物。说明：步骤 1-6 在“实验结果”一节中描述，步骤 7 在“实验总结”一节中描述。以上为两个问题的求解算法，每个都需要有相应的步骤。实验结果最长公共子序列问题步骤 1：问题描述：对于给定的两个序列 X 和 Y，找出 X 和 Y 的一个最长公共子序列。步骤 2：算法设计：采用一个结点对象存储最优值和最优值的来源。采用二维

数组来存放各个子问题的最优值，并记录其来源。a[i][j].mark = 1 表示 a[i][j]由 a[i][j-1]得到，a[i][j].mark = 2 表示 a[i][j]由 a[i-1][j]得到，a[i][j].mark = 3 表示 a[i][j] 由 a[i-1][j-1] +1 得到。数组 x[1：m]存放序列 X，数组 y[1: n]存放序列 Y，初始时 a[i][0]和 a[0][j]都为 0。由递推关系，便利构造出所有子问题的最优解，从结果中到推出问题最优解，开始 i = m，j = n,如果 a[i][j].mark=3，则输出 x[i]，mark 值为 2 则 i = i-1，j = j；mark 值 1 则 i = i，j = j-1。直到 i= 0 或 j= 0 终止，输出序列即为最长公共子序列反序。步骤 3：描述算法。 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 a[0][j] = 0 do for i=1 to m do for j=1 to n if x[i]= y[j] do 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 LCS-PRINT ( x[m],a[m+1][n+1] ) i=m j=n do if a[i][j].mark = 3 print x[i] then i= i-1 J = j-1 else if a[i][j].mark = 2 then I = i-1 else a[i][j].mark = 1 then j = j-1 while i=0 or j=0 步骤 4：算法的正确性证明。设序列 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 的最长公共子序列。以上，可以使用反证法进行证明。 LCS 问题的子问题重叠性质：在计算 X 和 Y 的 LCS 时，可能需要计算 Xm-1 和 Y 或 X 和 Yn-1 的 LCS，很显然都包含了 Xm-1 和 Yn-1 的 LCS。步骤 5：算法复杂性分析。构造子问题最优解为运行时间最大，进行了双重循环，所以算法时间复杂度为 O(n 2 )。空间复杂度为 O(n 2 ) 步骤 6：算法实现与测试。 LSC 类： package exem3; import java.util.Random; public class LSC { private static int m=10; private static int n=12; public static void main (String args[]){ int x[]=new int[m]; int y[]=new int[n]; //int x[]={5,2,7,4,6,9,9,0,9,2}; // int y[]={0,7,4,1,9,3,3,2,7,5,0,3,}; node a[][]=new node[m+1][n+1]; Random random = new Random(); System.out.print("序列X:"); for(int i=0;i

} System.out.println(); for(int i=0;im) i=m; if(x[i-1]==y[j-1]){ //初始化二维数组 //构建子问题的解 a[i][j].setValue(a[i-1][j-1].getValue()+1); a[i][j].setMark(3); } else if(a[i][j-1].getValue()>a[i-1][j].getValue()){ a[i][j].setValue(a[i][j-1].getValue()); a[i][j].setMark(2); } else { a[i][j].setValue(a[i-1][j].getValue()); a[i][j].setMark(1); } } } for(int i=0;i

int[] LSC= new int[len]; int mark=0; /*do{ 子序列 if(a[i][j].getMark()==3){ i=i-1; j=j-1; LSC[mark++]=x[i]; } else if(a[i][j].getMark()==2) j=j-1; else if(a[i][j].getMark()==1) i=i-1; }while(i!=0&&j!=0);*/ i=m;j=n; mark=0; do{ 最长公共子序列 //使用标志位，遍历得到最长公共 //不使用标志位，求解 if(a[i-1][j-1].getValue()==(a[i][j].getValue()-1)){ if(x[i-1]==y[j-1]){ i-=1; j-=1; LSC[mark++]=x[i]; continue; } } if(a[i-1][j].getValue()>=a[i][j-1].getValue()) i-=1; else if(a[i-1][j].getValue()=0;m--){ System.out.print(LSC[m]+" "); } } } Node 类： package exem3;

public class node { private int value; private int mark; public int getValue() { return value; } public void setValue(int value) { this.value = value; } public int getMark() { return mark; } public void setMark(int mark) { this.mark = mark; } } 实验结果：步骤 6：动态规划的求解步骤：（1）分析最优解的性质，以刻画最优解的结构特征—考察是否适合采用动态规划方法，即是否具备最优子结构性质；（2）递归定义最优值（即建立递归公式或动态规划方程），包括停止条件（递归出口）和递归体；（3）以自底向上的方式计算出最优值，并记录相关信息。应充分利用子问题重叠性质；（4）最终构造出最优解。 0-1 背包问题步骤 1：问题描述。 n 个物品和 1 个背包。对物品 I, 其价值为 vi，重量为 wi，

背包的容量为 W。如何选取物品装入背包，是背包装入物品的总价值最大。步骤 2：算法设计。采用数组 w 来存放物品的重量信息，数组 p 来存放物品的价值信息。二维数组 C[i][j]表示背包重量为 j 时前 i 个物品中放入背包的总价值。用数组 X[n],来存储物品的状态，0 表示未放入，1 表示放入。初始时当背包重量为 0 时总价值为 0，即 c[i][0] = 0；当为放入任何物品时，总价值为零，即 c[0][j] = 0；。如果 j>wi，表明第 i 个物品可以放入构成重量 j， c[i][j] = MAX(c[i-1][j-wi]+vi , c[i-1][j])，如果 jc[n-1][W]，表明第 n 个物品放入背包，xn=1，考虑前 n-1 个物品装入 W-wi 的背包中；否则 xn=0，考虑前 n-1 个物品装入 W 的背包中...以此类推。得出物品的装入状态。步骤 3：描述算法。 KNAPSACK（int n int W, int w[n] , int p[n] ） for i=0 to n do c[i][0]=0 for j=0 to W do c[0][j]=0 for i=1 to n do for j=1 to W do if w[i-1] > j thenc[i][j]=c[i-1][j] else c[i][j]=Max(c[i-1][j],c[i-1][j-w[i-1] ]+p[i-1]) REAULT (int c[n+1][W+1],int w[]) j=W for i=n to 1 do if c[i][j]>c[i-1][j] then x[i-1]=1 j=W-w[i-1] else x[i]=0 步骤 4：算法的正确性证明。反证法易证该算法所选择的策略可以正确解决该问题：设 (x1, x2,…, xn) 是所给 0-1 背包问题的一最优解，则 (x2,…, xn) 是下面相应子问题的一个最优解：约束条件：

目标函数：步骤 5：算法复杂性分析。采用 DP 求解 0-1 背包问题时间复杂性：O(nW)，空间复杂性：O(1) 步骤 6：算法实现与测试。 Kanpsack 类: package exem4; import java.util.Random; public class kanpsack { private static int n = 10; private static int W = 10; public static void main(String args[]) { int w[] = new int[n]; int p[] = new int[n]; int x[] = new int[n]; int c[][] = new int[n + 1][W + 1]; Random random = new Random(); for (int i = 0; i < n; i++) { 价值 w[i] = random.nextInt(10) + 1; p[i] = random.nextInt(8) + 1; x[i] = 0; } System.out.print("物品重量： "); for (int i = 0; i < n; i++) { System.out.print(w[i] + " "); } System.out.print("\n物品价值："); for (int i = 0; i < n; i++) { System.out.print(p[i] + " "); } System.out.println(); for (int i = 0; i < n + 1; i++) { c[i][0] = 0; } for (int i = 0; i < W + 1; i++) { c[0][i] = 0; // 随机生成物品重量和

资料库

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

相关推荐

课程资源

热门标签

最新资料