正文描述:《算法设计与分析动态规划实验》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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
显示全部收起