《算法设计与分析作业第3章》由会员分享，可在线阅读，更多相关《算法设计与分析作业第3章（13页珍藏版）》请在金锄头文库上搜索。
1、编程实现下述4个算法，并利用给定的数据，验证算法正确性最长公共子序列最大子段和凸多边形最优三角剖分0-1背包问题最长公共子序列利用“附件1.最长公共子序列输入数据”中给出的字符串A,B,C,D,分别找出下列两两字符串间的最长公共子串，并输出结果：A-B,C-D,A-D,C-B最长公共子序列字符串A,B,C,D生成方法：产生由9个数字0,1,2,3,4,5,6,7,8,9组成的长度在400-500之间（也可以更长）的序列A1,C1产生由9个符号),!,+,$,%,&,*,(组成的长度在400-500之间（也可以更长）的序列B1,D1+改成:-,=最长公共子序列将由26个英文字母和符号“+”组成的
2、字符串an+algorithm+is+any+welldefined+computational+procedure+that+takes+some+values+as+input+and+produces+some+values+as+output注：在C、D中，An+algorithm中的各个字母和符号“+”在保持原有前后顺序的前提下插入到字符串A1,B1,C1,D1中，得到字符串A,B,C,D最长公共子序列注意：由26个英文字母和+组成的字符串中的各个符号插入到A1,B1,C1,D1中后，任意2个符号间应当有数字隔开。例如，1a27n4+498a3l9g76o,不要出现“1an4+498
3、al9g76o”最大子段和针对“附件2.最大子段和输入数据-序列1”、“附件2.最大子段和输入数据-序列2”中给出的序列1、序列2,分别计算其最大子段和序列1：长度在300-400之间，由(-100,100)内的数字组成序列2：长度在100-200之间，由(-50,50)内的数字组成最大子段和要求：1.指出最大子段和在原序列中的位置2.给出最大子段和具体值凸多边形最优三角剖分利用：1.“附件3-1.21个基站凸多边形数据”2.“附件3-2.29个基站凸多边形数据”给出21凸多边形顶点数据、29凸多边形顶点数据，以顶点间的地理距离作为连接2个顶点的边、弦到的权值，对这2个凸多边形进行最优三角剖分
4、凸多边形最优三角剖分21凸多边形构造方法根据xx市TD-LTE网络配置数据，选取全部基站eNODEB；以这些基站作为平面点，构造平面点集的凸包，得到具有21个顶点的凸21边形凸多边形最优三角剖分29凸多边形构造方法根据xx市TD-LTE网络配置数据，选取部分基站eNODEB；以这些基站作为平面点，构造平面点集的凸包，得到具有29个顶点的凸29边形凸多边形最优三角剖分要求：1.做图做图表示最优三角剖分结果可以手绘2.计算最优三角剖分对应的最优目标值最小边长弦长总和3.2种方法:启发式,DP0-1背包问题利用“附件4.背包问题输入数据”给出的2组背包数据（背包容量、物品重量、物品价值），计算最优物品装载方案第1组数据：50个物品第2组数据：100个物品0-1背包问题要求：指出最优方案中，1.各个物品是否被放入2.物品放入后的背包总重量、总价值
