算法分析之动态规划.pptVIP

段旭良@四川农业大学 5025968@ 段旭良@四川农业大学 5025968@ 段旭良@四川农业大学 5025968@ 实验要求 理解动态规划的原理及一般应用 最优子结构 子问题重叠 递归关系的提取 编程实现典型的动态规划算法，对算法进行验证，分析算法复杂度。 实验内容 1 Edit-Distance 字符串A通过插入、删除、替换字符变成另一个字符串B，操作的次数表示两个字符串的差异。 用于计算文本相关性、相似性 递归关系 两字符串长度为N、M，对1≤i≤N，1≤j≤M，有 若ai=bj 则LD(i,j)=LD(i-1,j-1) 若ai≠bj 则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1 实验内容 求解例 A=GGATCGA，B=GAATTCAGTTA，计算LD(A,B) 第一步：初始化LD矩阵 LD算法矩阵 ? ? G A A T T C A G T T A ? 0 1 2 3 4 5 6 7 8 9 10 11 G 1 0? 1? 2? 3? 4? 5? 6? 7? 8? 9? 10? G 2 ? ? ? ? ? ? ? ? ? ? ? A 3 ? ? ? ? ? ? ? ? ? ? ? T 4 ? ? ? ? ? ? ? ? ? ? ? C 5 ? ? ? ? ? ? ? ? ? ? ? G 6 ? ? ? ? ? ? ? ? ? ? ? A 7 ? ? ? ? ? ? ? ? ? ? ? 实验内容 第二步：利用递归式，依次列出其他行列 若ai=bj 则LD(i,j)=LD(i-1,j-1) 若ai≠bj 则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1 LD算法矩阵 ? ? G A A T T C A G T T A ? 0 1 2 3 4 5 6 7 8 9 10 11 G 1 0 1 2 3 4 5 6 7 8 9 10 G 2 1 1 2 3 4 5 6 6 7 8 9 A 3 2 1 1 2 3 4 5 6 7 8 8 T 4 3 2 2 1 2 3 4 5 6 7 8 C 5 4 3 3 2 2 2 3 4 5 6 7 G 6 5 4 4 3 3 3 3 3 4 5 6 A 7 6 5 4 4 4 4 3 4 4 5 5 实验内容 2 0-1背包问题 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。 0-1表示要么装，要么不装。 实验内容 分析 考虑由前i (1≤i≤n)个物品定义的实例，物品重量分别为w1,w2,…wi，价值分别为v1,v2,…vi，背包承重量 j (1 ≤ j ≤ w)。 设V[i,j]为能放进承重量为j的前i个物品中最有价值子集的总价值。这个子集分两类： 不包括第i个物品的最优子集价值是v[i-1,j] 包括第i个物品的子集中，该最优子集是由该物品和前i-1个物品中能放进承重j-wi的背包的最优子集组成，总价值为vi + V[ i-1, j-wi ]。 实验内容 分析 考虑由前i (1≤i≤n)个物品定义的实例，物品重量分别为w1,w2,…wi，价值分别为v1,v2,…vi，背包承重量 j (1 ≤ j ≤ w)。 设V[i,j]为能放进承重量为j的前i个物品中最有价值子集的总价值。这个子集分两类： 不包括第i个物品的最优子集价值是v[i-1,j] 包括第i个物品的子集中，该最优子集是由该物品和前i-1个物品中能放进承重j-wi的背包的最优子集组成，总价值为vi + V[ i-1, j-wi ]。 实验内容 物品 重量 价值 1 2 12元 2 1 10元 3 3 20元 4 2 15元 承重量j i 0 1 2 3 4 5 0 0　 0 0 0 0 0 w1=2,v1=12 1 0 0 12 12 12 12 w2=1,v2=10 2 0 10 12 22 22 22 w3=3,v3=20 3 0 10 12 22 30 32 w4=2,v4=15 4 0 10 15 25 30 37 　 0 … j-wi … j … W 0 　 　 　 　 　 　 　 … 　 　 　 　 　 　 　 i-1 　 　 V(i-1,j-wi) 　 V(i-1, j) 　 　 i 　 　 　 V(i, j) 　 　 i+1 　 　 　 　 … 　 　 　 　 　 　 　 n 　 　 　 　 　 　 　 实验结果 按要求粘贴 算法名称及代码 个人信息适时嵌入代码 代码要注意换行、缩进层次 要有注释，最好有着色 22/code/ 结果截图 分析结论 报告严格命名 学号_姓名_实验3.doc