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

实验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数组：0ACBCDABD0000000000A011111222B011222233D011112223C012233333A022222333B022333344A0333334442. 最长公共子序列问题(LCS)。使用动态规划算法求解最长公共子序列。【输入：两个字符序列；输出：两个字符序列的最长公共子序列。例如：输入序列A = ABCBDAB，序列B = BDCABA；输出BCAB（或其他任意一条长度为4的公共子序列）】源代码：#include#include#includeusing namespace std;int dp10001000;string str1,str2,s1,s2;int max(int a,int b,int c)if(ab & ac)return a;if(ba & bc)return b;if(ca & cb)return c;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;ilen1+2;i+)dpi1=-2*(i-1);for(j=2;jlen2+2;j+)dp1j=-2*(j-1);for(j=2;jlen2+2;j+)for(i=2;i1 & j1)if(dpij+2=dpi-1j)s2=s2+_;s1=s1+str1i-2;i-;continue;if(dpij+2=dpij-1)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-)couts1i;cout=0;j-)couts2j;coutstr1str2)len1=str1.size();len2=str2.size(); coutlcs(len1,len2)endl;for(int i=1;i=len1+1;i+)for(int j=1;j=len2+1;j+)coutsetw(5)dpij ;coutendl; print(len1,len2);return 0;3. 0-1背包问题。在使用动态规划算法求解0-1背包问题时，使用二维数组mij存储背包剩余容量为j，可选物品为i、i+1、n时0-1背包问题的最优值。绘制价值数组v = 8, 10, 6, 3, 7, 2，重量数组w = 4, 6, 2, 2, 5, 1，背包容量C = 12时对应的mij数组。所绘制的mij数组：wv48610262357124. 0-1背包问题。给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为C。如何选择装入背包的物品，可以使得装入背包中物品的总价值最大？【输入：两个一维数组分别用于存储每一种物品的价值和重量，以及一个整数表示背包的容量。例如：价值数组v = 6,3,6,5,4，重量数组w = 2,2,4,6,5，背包容量C=10。输出：背包的最大总价值和所选取的物品。例如：最大总价值=15，物品选取策略为10011。】源代码：#includeint c10100;/*对应每种情况的最大价值*/int knapsack(int m,int n) int i,j,w10,p10; printf(请输入每个物品的重量,价值：n); for(i=1;i=n;i+) scanf(%d,%d,&wi,&pi); for(i=0;i10;i+) for(j=0;j100;j+) cij=0;/*初始化数组*/ for(i=1;i=n;i+) for(j=1;j=m;j+) if(wici-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,&m,&n); printf(旅行者背包能装的最大总价值为%d,knapsack(m,n); printf(n); return 0;5*. 对最长公共子序列问题的动态规划算法进行改进，输出所有最长公共子序列。源代码：6*. 某工厂预计明年有A、B、C、D四个新建项目，每个项目的投资额Wk及其投资后的收益Vk如下表所示，投资总额为30万元，如何选择项目才能使总收益最大？【0-1背包问题】ProjectWkVkA1512B108C129D85源代码：说明：(1) 编程语言不限，建议使用Java、C+或者C语言。(2) 需要将程序源代码复制