算法设计与分析动态规划实验

ID:9410918

大小:71.79 KB

页数:7页

时间:2018-04-30

算法设计与分析动态规划实验_第1页
算法设计与分析动态规划实验_第2页
算法设计与分析动态规划实验_第3页
算法设计与分析动态规划实验_第4页
算法设计与分析动态规划实验_第5页
资源描述:

《算法设计与分析动态规划实验》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、实验5动态规划实验实验内容1.最长公共子序列问题(LCS)。在使用动态规划算法来求解最长公共子序列时,二维数组c[i][j]用于记录序列Xi和Yj的最长公共子序列的长度,对于序列X={A,C,B,C,D,A,B,D}和Y={A,B,D,C,A,B,A},绘制对应的c[i][j]。所绘制的c[i][j]数组:0ACBCDABD0000000000A011111222B011222233D011112223C012233333A022222333B022333344A0333334442.最长公共子序列问题(LCS)。使用动态规划算法

2、求解最长公共子序列。【输入:两个字符序列;输出:两个字符序列的最长公共子序列。例如:输入序列A="ABCBDAB",序列B="BDCABA";输出"BCAB"(或其他任意一条长度为4的公共子序列)】源代码:#include#include#includeusingnamespacestd;intdp[1000][1000];stringstr1,str2,s1,s2;intmax(inta,intb,intc){if(a>b&&a>c)returna;if(b>a&&b>c)r

3、eturnb;if(c>a&&c>b)returnc;}intlcs(intlen1,intlen2){memset(dp,0,sizeof(dp));7inti,j,x;dp[0][1]=0;dp[1][0]=0;dp[1][1]=0;dp[0][0]=0;for(i=2;i

4、==str2[j-2])x=dp[i-1][j-1]+5;elsex=dp[i-1][j-1]-1;dp[i][j]=max(x,dp[i-1][j]-2,dp[i][j-1]-2);}}returndp[i-1][j-1];}voidprint(intlen1,intlen2){inti,j;i=len1+1;j=len2+1;while(i>1&&j>1){if(dp[i][j]+2==dp[i-1][j]){s2=s2+'_';s1=s1+str1[i-2];i--;continue;}if(dp[i][j]+2==dp[i

5、][j-1]){7s1=s1+'_';s2=s2+str2[j-2];j--;continue;}if(dp[i][j]+1==dp[i-1][j-1]

6、

7、dp[i][j]-5==dp[i-1][j-1]){s1=s1+str1[i-2];s2=s2+str2[j-2];j--;i--;continue;}}for(i=len1-1;i>=0;i--){cout<=0;j--){cout<

8、len2;while(cin>>str1>>str2){len1=str1.size();len2=str2.size();cout<

9、为i、i+1、……、n时0-1背包问题的最优值。绘制价值数组v={8,10,6,3,7,2},重量数组w={4,6,2,2,5,1},背包容量C=12时对应的m[i][j]数组。所绘制的m[i][j]数组:wv48610262357124.0-1背包问题。给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,背包的容量为C。如何选择装入背包的物品,可以使得装入背包中物品的总价值最大?【输入:两个一维数组分别用于存储每一种物品的价值和重量,以及一个整数表示背包的容量。例如:价值数组v[]={6,3,6,5,4},重量数组w[]=

10、{2,2,4,6,5},背包容量C=10。输出:背包的最大总价值和所选取的物品。例如:最大总价值=15,物品选取策略为10011。】源代码:#includeintc[10][100];/*对应每种情况的最大价值*/intknaps

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

《算法设计与分析动态规划实验》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、实验5动态规划实验实验内容1.最长公共子序列问题(LCS)。在使用动态规划算法来求解最长公共子序列时,二维数组c[i][j]用于记录序列Xi和Yj的最长公共子序列的长度,对于序列X={A,C,B,C,D,A,B,D}和Y={A,B,D,C,A,B,A},绘制对应的c[i][j]。所绘制的c[i][j]数组:0ACBCDABD0000000000A011111222B011222233D011112223C012233333A022222333B022333344A0333334442.最长公共子序列问题(LCS)。使用动态规划算法

2、求解最长公共子序列。【输入:两个字符序列;输出:两个字符序列的最长公共子序列。例如:输入序列A="ABCBDAB",序列B="BDCABA";输出"BCAB"(或其他任意一条长度为4的公共子序列)】源代码:#include#include#includeusingnamespacestd;intdp[1000][1000];stringstr1,str2,s1,s2;intmax(inta,intb,intc){if(a>b&&a>c)returna;if(b>a&&b>c)r

3、eturnb;if(c>a&&c>b)returnc;}intlcs(intlen1,intlen2){memset(dp,0,sizeof(dp));7inti,j,x;dp[0][1]=0;dp[1][0]=0;dp[1][1]=0;dp[0][0]=0;for(i=2;i

4、==str2[j-2])x=dp[i-1][j-1]+5;elsex=dp[i-1][j-1]-1;dp[i][j]=max(x,dp[i-1][j]-2,dp[i][j-1]-2);}}returndp[i-1][j-1];}voidprint(intlen1,intlen2){inti,j;i=len1+1;j=len2+1;while(i>1&&j>1){if(dp[i][j]+2==dp[i-1][j]){s2=s2+'_';s1=s1+str1[i-2];i--;continue;}if(dp[i][j]+2==dp[i

5、][j-1]){7s1=s1+'_';s2=s2+str2[j-2];j--;continue;}if(dp[i][j]+1==dp[i-1][j-1]

6、

7、dp[i][j]-5==dp[i-1][j-1]){s1=s1+str1[i-2];s2=s2+str2[j-2];j--;i--;continue;}}for(i=len1-1;i>=0;i--){cout<=0;j--){cout<

8、len2;while(cin>>str1>>str2){len1=str1.size();len2=str2.size();cout<

9、为i、i+1、……、n时0-1背包问题的最优值。绘制价值数组v={8,10,6,3,7,2},重量数组w={4,6,2,2,5,1},背包容量C=12时对应的m[i][j]数组。所绘制的m[i][j]数组:wv48610262357124.0-1背包问题。给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,背包的容量为C。如何选择装入背包的物品,可以使得装入背包中物品的总价值最大?【输入:两个一维数组分别用于存储每一种物品的价值和重量,以及一个整数表示背包的容量。例如:价值数组v[]={6,3,6,5,4},重量数组w[]=

10、{2,2,4,6,5},背包容量C=10。输出:背包的最大总价值和所选取的物品。例如:最大总价值=15,物品选取策略为10011。】源代码:#includeintc[10][100];/*对应每种情况的最大价值*/intknaps

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭