《算法分析之动态规划.ppt课件》由会员分享，可在线阅读，更多相关《算法分析之动态规划.ppt课件（11页珍藏版）》请在装配图网上搜索。
1、实验实验3 3 动态规划动态规划段旭良四川农业大学段旭良四川农业大学实验要求实验要求n了解动态规划的原理及普通运用n最优子构造n子问题重叠n递归关系的提取n编程实现典型的动态规划算法，对算法进展验证，分析算法复杂度。段旭良四川农业大学段旭良四川农业大学实验内容实验内容n1 Edit-Distancen字符串A经过插入、删除、交换字符变成另一个字符串B，操作的次数表示两个字符串的差别。n用于计算文本相关性、类似性n递归关系n两字符串长度为N、M，对1iN，1jM，有n假设ai=bjn那么LD(i,j)=LD(i-1,j-1)n假设aibjn那么LD(i,j)=Min(LD(i-1,j-1),LD
2、(i-1,j),LD(i,j-1)+1段旭良四川农业大学段旭良四川农业大学实验内容实验内容n求解例nA=GGATCGA，B=GAATTCAGTTA，计算LD(A,B)n第一步：初始化LD矩阵LD算法矩阵 GAATTCAGTTA 0123456789 10 11G10 1 2 3 4 5 6 7 8 9 10 G2 A3 T4 C5 G6 A7 段旭良四川农业大学段旭良四川农业大学实验内容实验内容n第二步：利用递归式，依次列出其他行列第二步：利用递归式，依次列出其他行列假设ai=bj那么LD(i,j)=LD(i-1,j-1)假设aibj那么LD(i,j)=Min(LD(i-1,j-1),LD(i
3、-1,j),LD(i,j-1)+1LD算法矩阵 GAATTCAGTTA 0123456789 10 11G10123456789 10G211234566789A321123456788T432212345678C543322234567G654433333456A765444434455段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学实验内容实验内容n2 0-1背包问题n给定n种物品和一背包。物品i的分量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?n0-1背包问题是一个特殊的整数规划问题。n0-1表示要么装，要么不
4、装。nixCxwxviniiiniii1,1,0max11段旭良四川农业大学段旭良四川农业大学实验内容实验内容n分析n思索由前i(1in)个物品定义的实例，物品分量分别为w1,w2,wi，价值分别为v1,v2,vi，背包承分量 j(1 j w)。n设Vi,j为能放进承分量为j的前i个物品中最有价值子集的总价值。这个子集分两类：n不包括第i个物品的最优子集价值是vi-1,jn包括第i个物品的子集中，该最优子集是由该物品和前i-1个物品中能放进承重j-wi的背包的最优子集组成，总价值为vi+V i-1,j-wi。段旭良四川农业大学段旭良四川农业大学实验内容实验内容n分析n思索由前i(1in)个物品
5、定义的实例，物品分量分别为w1,w2,wi，价值分别为v1,v2,vi，背包承分量 j(1 j w)。n设Vi,j为能放进承分量为j的前i个物品中最有价值子集的总价值。这个子集分两类：n不包括第i个物品的最优子集价值是vi-1,jn包括第i个物品的子集中，该最优子集是由该物品和前i-1个物品中能放进承重j-wi的背包的最优子集组成，总价值为vi+V i-1,j-wi。00,V0i0),0(,00),1(),1(),1(max),(ijVjwjwjjiVvwjiVjiVjiViiii时，；时段旭良四川农业大学段旭良四川农业大学实验内容实验内容物品重量价值1212元2110元3320元4215元承
6、重量承重量ji0123450000000w1=2,v1=1210012121212w2=1,v2=10201012222222w3=3,v3=20301012223032w4=2,v4=154010152530370j-wij W0 i-1V(i-1,j-wi)V(i-1,j)iV(i,j)i+1 n 段旭良四川农业大学段旭良四川农业大学实验结果实验结果n按要求粘贴n算法称号及代码n个人信息适时嵌入代码n代码要留意换行、缩进层次n要有注释，最好有着色n10.2.130.222/code/n结果截图n分析结论报告严厉命名 学号_姓名_实验3.doc 上传至ftp10.2.130.222/Upload/Ex3
算法分析之动态规划.ppt课件
