算法设计与分析

1、算法设计与分析作业作业一动态规划作业姓名指导教师学号日 期班级作业内容1）预习教材并查找资料，学习动态规划基本知识。2）完成并实现教材例题：最长公共子序列3）完成并实现教材例题：01背包作业解答作业2-1：求最长公共子序列A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = another sequence Z = is a subsequence of X if there exists a strict

2、ly increasing sequence of indices of X such that for all j = 1,2,.,k, x 口 = zj. For example, Z = is a subsequence of X = with index sequence . Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.InputThe program input is from the std inpu

3、t. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.OutputFor each set of data the program prints on the standard output the length of the maximum-length common subsequence from the

4、 beginning of a separate line.代码：#includecstdio#includecstring#includealgorithmusing namespace std;#define inf 1200#define loop(x,y,z) for(x=y;xz;x+)#define INF 99999999#define ll long long,j;char s1inf,s2inf;int ansinfinf;void init()memset(ans,0,sizeof 0);int getAns(int i,int j)if(i0|j0)return 0;re

5、turn ansij;int calDP()int len1=strlen(s1);int len2=strlen(s2);int i,j;loop(i,0,len1)loop(j,0,len2)if(s1i=s2j)ansij=getAns(i-1,j-1)+1;elseansij=max(getAns(i-1,j),getAns(i,j-1);return anslen1Tlen2T;int main()int i,j;while(scanf(%s%s”,s1,s2)printf(%dn”,calDP();return 0;测试数据：Sample Inputabcfbcabfcabprog

6、ramming contestabcdmnpSample Output420测试截图： E cod e66&lbinC ebu g1 .exeabcfbc 4 programning 2 abed Qabfcab contest mnp作业2-201背包问题：Many years ago , in Teddys hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dogs , cows , also he went to the

7、grave The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bones value along his trip , can you calculate out the maximum of the total value the bone co

8、llector can get ?InputThe first line contain a integer T , the number of cases. Followed by T cases , each case three lines , the first line contain two integer N , V, (N = 1000 , V = 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representin

9、g the value of each bone. The third line contain N integers representing the volume of each bone.OutputOne integer per line representing the maximum of the total value (this number will be less than 2 3).Sample Input15 101 2 3 4 55 4 3 2 1Sample Output14代码：#includecstdio#includecstring#includealgori

10、thmusing namespace std;#define inf 1200#define loop(x,y,z) for(x=y;xz;x+)#define INF 99999999#define ll long longint n,bag;int valueinf;int volumeinf;int ansinfinf;/存放结果void init()memset(ans,0,sizeof ans);void calDP()int i,j;loop(i,0,bag+1)loop(j,1,n+1)if(i-volumej0)ansij=ansij-1;elseansij=max(ansi-volumejj-1+valuej,ansij-1)int main()int T;int i,j;scanf(