算法设计与分析期末论文

1、算法设计与分析论文学院：计算机学院专业：计算机科学与技术姓名：龚振学号：2分数20得分一、 简答（任选两题，210分=20分） 1.简述动态规划算法求解问题的一般步骤。答：找出最优解的性质，并刻画其机构特征；递归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时地带的信息，构造最优解。6.简述回溯法求解问题的一般步骤。答：(1)用回溯法解题通常包含一下3个步骤(2)针对所给问题，定义问题的解空间；(3)确定易于搜索的解空间；(4)以深度优先方式搜索解空间，并在搜索过程中用剪枝反函数避免无效搜索。分数二、算法设计与程序实现 （任选两题，240分=80分）统一要求（若该题有特殊要求，会在

2、题中给出）：1. 设计算法2. 分析计算复杂度3. 程序实现4. 最后通过简例说明程序实现过程5. 需将源程序附上，程序需有必要的注释语句6. 需给出程序运行结果截图80得分1、 工作分配问题：设有件工作分配给个人。将工作分配给第个人所需费用为。为每一个人分配一件不同的工作，并使总费用达到最小。1.1设计算法工作分配按照遍历应该有n!种分法，从中找出所需费用最少的费用。这里采用递归的方法解决问题对于每一条路径所需费用为expense=，其中表示第i建工作分配给第pi个人时所需费用，p1pn互不相同，即每个人只能分配一件工作。在计算的时候可以设计expense(i)等于分配过第i件工作后这时所达

3、到的总费用，分配第i+1i+1件工作，总费用expense(i+1)=expense(i)+,当in时，继续递归，当i=n时判断本此分配的工作总费用是否比之前保存的最低费用小，是则把此次分配总费用值赋给minexpense，并保存此次分配的路径给q。可以设计如下递归函数void workdistribute(int i,int n,int *p,int x,int cN)for(int j=1;j=n;j+)if(xj=0)xj=1;x0+=cij;pi=j;if(ix0|minexpense=-1)minexpense=x0;for(int k=1;k=n;k+)qk=pk;x0-=cij;

4、xj=0;1.2分析计算复杂度1.3程序实现进行宏定义N大小为100,在以后可以重新赋值#define N 100int qN=0;/定义全局变量q数组用来保存工作分配路径int minexpense=-1;/定义全局变量用来保存分配中最小费用void workdistribute(int i,int n, int p,int x,int cN);主函数void main() int n=0;int cNN;int xN=0;int pN=0;printf(ttt1.工作分配问题nn);printf(请输入人数n);scanf(%d,&n);下面用来输入所需费用for(int i=1;i=n;

5、i+)for(int j=1;j=n;j+)scanf(%d,&cij);调用workdistribute(1,n,p,x,c);函数进行递归分配工作，递归结束后进行输出最小费用和此分法，以矩阵的形式显示workdistribute(1,n,p,x,c);printf(%dn,minexpense);此循环用来输出最少费用的分配方法for(int k=1;k=n;k+)for(int j=1;j=n;j+)if(qk!=j)printf( );elseprintf(%d ,ckj);printf(n);/workdistribute(i,n,p,x,c)函数设计，传递进行分配的是第几件工作i，

6、已分配过的人X,分配的路径p，以及费用数组c，用X来保存已非配工作所需费用void workdistribute(int i,int n,int *p,int x,int cN)for(int j=1;j=n;j+)if(xj=0)xj=1;x0+=cij;pi=j;if(ix0|minexpense=-1)/如果是最小分配或第一次分配，则保存此次分配数据minexpense=x0;for(int k=1;k=n;k+)qk=pk;xj=0;x0-=cij;/返回上一层之前，先减去此事件分配的费用1.4最后通过简例说明程序实现过程输入事件数为3输入费用矩阵 C32 1 34 5 21 2 1第

7、一层第一次分配workdistribute(1,n,p,x,cN);分配过程c11,c22,c33 此时最小费用是8 赋值给minexpense，并把1,2,3保存在q数组,最后一层递归返回上一次，第二中分配方式c11,c23,c32此时费用时6，minexpense为6，1,3,2保存在q中，第一层第一次分配完毕，然后循环workdistribute(2,n,p,x,cN);第三种分配,c12,c21,c33，minexpesne=6,q:为1,3,2，第四次分配c12,c23,c31，minexpense=4，q：2,3,1第一层第二次分配完毕，然后循环workdistribute(3,n

8、,p,x,cN);第五种分配c13,c21,c32,minexpense=4，q：2,3,1，第六种分配c13,c22,c31,minexpense=4，q：2,3,1返回主程序，输出minexpense，q，2,3,1。输出时输出minexpense：4；输出路径时：只输出二维数组c中第i行中第qi个数，其他输出空格结果为 1 2 11.5源代码注释#include#include #define N 100int qN=0;/全局变量int minexpense=-1;/最小费用void workdistribute(int i,int n, int p,int x,int cN);/递归

9、函数void main() int n=0;int cNN;int xN=0;int pN=0;printf(ttt01工作分配问题n);printf(请输入人数n);scanf(%d,&n);for(int i=1;i=n;i+)/输入数组Cfor(int j=1;j=n;j+)scanf(%d,&cij);workdistribute(1,n,p,x,c);/进行分配printf(%dn,minexpense);for(int k=1;k=n;k+)for(int j=1;j=n;j+)if(qk!=j)printf( );elseprintf(%d ,ckj);/输出分配路径printf

10、(n);void workdistribute(int i,int n,int *p,int x,int cN)for(int j=1;j=n;j+)/数组每一行的列循环if(xj=0)/i行j列没分配则进行分配xj=1;x0+=cij;pi=j;if(ix0|minexpense=-1)/如果是最小分配或第一次分配，则保存此次分配数据minexpense=x0;for(int k=1;k0,wi,vi0，1in,要求找出n元0-1的向量(,.,),0,1,1in,使得C，而且达到最大。因此，0-1背包问题是一个特殊的整数规划问题。设所给0-1背包问题的子问题的最优值为m(i,j),即m(i,

11、j)是背包容量为j,可选物品为i,i+1，,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立如下计算m(i,j)的递归关系式m(i,j)= m(n,j)=2.2复杂度分析2.3程序实现int knapsack(int i, int n,int v,int w,int c,int mN)if(i=n)/当装最低的物品时for(int j=1;j=c;j+)if(wi=1)/装不是最底层物品时knapsack(i+1,n, v,w,c,m);/继续递归，装i层下物品for(int j=1;j=wi&mi+1j=mi+1j-wi+vi)/当背包容量不小于物品重量时的最优放法mi

12、j=mi+1j-wi+vi;else/当背包容量小于物品重量时mij=mi+1j;if(i=1)/当所有物品都遍历后，构造最优解traceback(i,m,w,c);return mic;/返回背包最大价值2.4程序实现过程输入时背包容量是8，物品个数是4，其重量分别是1, 4, 2, 3，价值分别为2, 1, 4, 3，主函数开始调用knapsack(1, w0,v,w,C,m),先递归到最下层i=n，背包容量从j=1到j=c开是循环，当wi=wi&mi+1jn=4，返回上一层，递归结束x1x4=1,0,1,1;回到main函数输出背包最大价值9，以及放入物品重量和价值1,2，2,4，3,3

13、。程序结束。2.5程序源代码及注释#include#define N 50int knapsack(int i,int n,int v,int w,int c,int mN);/计算最大价值递归函数int traceback(int i, int mN,int w,int c);/寻找所放物品递归函数int xN=0;/用来标记物品是否被放入void main()int wN=0,vN=0;int mNN=0;int C=0,n=0;printf(tt 02.背包问题递归n);printf(输入背包容量:n);scanf(%d,&C);printf(输入物体数量:n,&n);scanf(%d,

14、&n);printf(输入物体重量和价值n);for(int i=1;i=n;i+)scanf(%d %d,&wi,&vi);w0+;printf(最大价值为：%dn,knapsack(1, w0,v,w,C,m);printf(所放物品重量和价值为：n);printf(重量 价值n);for( i=1;i=w0;i+)if(xi=1)printf( %d %dn,wi,vi);/输出所放物品重量和价值scanf(%d,&n);int knapsack(int i, int n,int v,int w,int c,int mN)if(i=n)/当装最低的物品时for(int j=1;j=c;j+)if(wi=1)/装不是最底层物品时knapsack(