1、实验四 动态规划算法设计与应用一. 实验目的和要求1.加深对动态规划算法的基本原理的理解，掌握用动态规划方法求解最优化问题的方法步骤及应用；2.用动态规划设计整数序列的最长递增子序列问题的算法，分析其复杂性，并实现；3.用动态规划设计求凸多边形的三角剖分问题的算法，分析其复杂性，并实现。4.选做题：用动态规划设计求解 0/1 背包问题的算法，分析其复杂性，并实现。二基本原理动态规划是一种非常重要的程序设计方法，常用于求解最优化问题。最优化问题：给定若干个约束条件和一个目标函数，在某指定集合中求满足所有约束条件的且使得目标函数值达最大或最小的元素和相应的目标函数值，即：问题的最优值和最优解。适用
2、动态规划求解的问题的基本要素：(1)满足最优性原理：即一个最优化问题的最优解包含了其子问题的最优解。(2)无后向性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也即，某状态以后的过程不会影响以前的状态，只与当前状态有关，这种特性也被称为无后效性。(2)具有重叠的子问题：即问题被分解成的子问题存在互相重叠。动态规划方法对于这些重叠的子问题只求解一次，以提高算法的效率。三 该类算法设计与实现的要点动态规划算法求解最优化问题的步骤：(1) 找出问题的最优子结构。分析问题的最优解（最优值）的结构特征。 (2) 递归地定义最优值。 根据最优子结构，确定最优值所满足的递归公式。(3) 计算最优值。
3、根据最优值的递归公式，采用自底向上的迭代或自顶向下的递归，计算最优值。 (4) 构造最优解。在求解最优值的过程中要记录下得到最优值的相应最优解的信息，并根据该信息构造最优解。注意：在计算最优值时应保存相应的信息：(a) 已经求出的子问题的最优值（避免重复计算） 。(b) 最优解的有关信息。 动态规划算法求解其它问题的步骤：(1) 根据最优化原理分析问题的解的结构。(2) 递归地定义问题的解。(3) 计算问题的解。 根据解的递归公式，自底向上或自顶向下地计算解，计算过程中注意保存已经求出的子问题的解。其中，自底向上方法通过迭代来实现，适用于所有的子问题都需要解的情况，实现时要注意根据递归公式正确
4、确定子问题的求解顺序。自顶向下方法通过递归来实现，适用于不必解所有的子问题的情况，实现时要注意标记子问题是否计算过，同一个子问题只在第一次递归调用时计算并存储结果。四实验内容(一) 最长递增子序列问题1.问题描述求一个由 n 个整数组成的整数序列的最长递增子序列。一个整数序列的递增子序列可以是序列中非连续的数按照原序列顺序排列而成的。 最长递增子序列是其递增子序列中长度最长的。2. 具体要求（若在 ACM 平台上提交程序，必须按此要求）平台上 1700 题输入：输入的第一行是一个正整数 n，表示测试例个数。接下来几行是 n 个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数 k
5、 (k#define MAX 50void bubble(int r,int n,int B)int i,j,temp;for(i=0;irj+1)temp=rj;rj=rj+1;rj+1=temp;for(i=0;i0i=i-1;j=j-1;elseif(Hij=1)i=i-1;elsej=j-1;C0=B0;for(i=0;i=Lij-1)Lij=Li-1j;Hij=1;elseLij=Lij-1;Hij=2;printf(“ %d“,Lnn);length=Lnn;printf(“n“);printf(“第%d 个子序列元素：“,num+1);Lcss(H,n,A,length,B);v
6、oid main()int m,i,j,AMAX,BMAX,CMAX,DMAX;printf(“测试例的个数：n“);scanf(“%d“,for(i=0;i#includefloat distance100100;#define MAX 100void dis(int count,float xMAX,float yMAX)int i,j;for(i=0;iam)s=am;return s;void main()int m,i,j,AMAX;float xMAX,yMAX,lengthMAX;printf(“输入测例个数：n“);scanf(“%d“,for(i=0;im;i+)printf(“输入第%d 测例数的顶点数为：nn“,i+1);scanf(“%d“,for(j=0;jAi;j+)scanf(“%f“,scanf(“%f“,dis(Ai,x,y);lengthi=triangle(0,Ai-1);printf(“nn“);printf(“结果如下：nn“);for(i=0;im;i+)printf(“%.3f“,lengthi);printf(“nn“);
