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

实验实验 5 动态规划实验动态规划实验 实验内容实验内容 1. 最长公共子序列问题(LCS)。在使用动态规划算法来求解最长公共子序 列时，二维数组 cij用于记录序列 Xi和 Yj的最长公共子序列的长度，对于序 列 X = A, C, B, C, D, A, B, D和 Y = A, B, D, C, A, B, A，绘制对应的 cij。 所绘制的所绘制的 cij数组：数组： 0ACBCDABD 0000000000 A011111222 B011222233 D011112223 C012233333 A022222333 B022333344 A033333444 2. 最长公共子序列问题(LCS)。使用动态规划算法求解最长公共子序列。 【输入：两个字符序列；输出：两个字符序列的最长公共子序列。例如：输入 序列 A = “ABCBDAB“，序列 B = “BDCABA“；输出“BCAB“（或其他任意一条 长度为 4 的公共子序列） 】 源代码：源代码： #include #include #include using namespace std; int dp10001000; string str1,str2,s1,s2; int max(int a,int b,int c) if(ab if(ba if(ca int lcs(int len1,int len2) memset(dp,0,sizeof(dp); int i,j,x; dp01=0; dp10=0; dp11=0; dp00=0; for(i=2;i1 s1=s1+str1i-2; i-; continue; if(dpij+2=dpij-1) 3 s1=s1+_; s2=s2+str2j-2; j-; continue; if(dpij+1=dpi-1j-1 | dpij-5=dpi-1j-1) s1=s1+str1i-2; s2=s2+str2j-2; j-; i-; continue; for(i=len1-1;i=0;i-) cout=0;j-) coutstr1str2) len1=str1.size(); len2=str2.size(); cout int c10100;/*对应每种情况的最大价值*/ int knapsack(int m,int n) int i,j,w10,p10; printf(“请输入每个物品的重量,价值：n“); 5 for(i=1;ici-1j) /*如果本物品的价值加上背包剩下的空间能放的物品的价值 */ /*大于上一次选择的最佳方案则更新 cij*/ cij=pi+ci-1j-wi; else cij=ci-1j; else cij=ci-1j; return(cnm); int main() int m,n;int i,j; printf(“请输入背包的承重量,物品的总个数：n“); scanf(“%d,%d“, printf(“旅行者背包能装的最大总价值为%d“,knapsack(m,n); printf(“n“); return 0; 5*. 对最长公共子序列问题的动态规划算法进行改进，输出所有最长公共子 序列。 源代码：源代码： 6*. 某工厂预计明年有 A、B、C、D 四个新建项目，每个项目的投资额 Wk 及其投资后的收益 Vk如下表所示，投资总额为 30 万元，如何选择项目才能使 总收益最大？【0-1 背包问题】 ProjectWkVk 7 A1512 B108 C129 D85 源代码：源代码： 说明：说明： (1) 编程语言不限，建议使用 Java、C+或者 C 语言。 (2) 需要将程序源代码复制并粘贴到每道题之后的方框中（部分题需要填写 输出结果） 。 (3) 在提交