算法设计与分析期末论

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

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

3、expense(i)等于分配过第i件工作后这时所达到的总费用，分配第i+1i+1件工作，总费用expense(i+1)=expense(i)+,当i<n时，继续递归，当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(i<n)workdistribute(i+1,n,p,x,

4、c);elseif(minexpense>x0|minexpense=-1)minexpense=x0;for(int k=1;k<=n;k+)qk=pk;x0-=cij;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;in

5、t xN=0;int pN=0;printf("ttt1.工作分配问题nn");printf("请输入人数n");scanf("%d",&n);下面用来输入所需费用for(int i=1;i<=n;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

6、",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，已分配过的人X,分配的路径p，以及费用数组c，用X来保存已非配工作所需费用void workdistribute(int i,int n,int *p,int x,int cN

7、)for(int j=1;j<=n;j+)if(xj=0)xj=1;x0+=cij;pi=j;if(i<n)/当未分配完时继续调用workdistribute(i+1,n,p,x,c);else/最后一事件分配完后，判断此次分配是不是最小费用if(minexpense>x0|minexpense=-1)/如果是最小分配或第一次分配，则保存此次分配数据minexpense=x0;for(int k=1;k<=n;k+)qk=pk;xj=0;x0-=cij;/返回上一层之前，先减去此事件分配的费用1.4最后通过简例说明程序实现过程输入事件数为3输入费用矩阵 C32 1 34

8、 5 21 2 1第一层第一次分配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第一层第二次分配完毕，然后循环workdist

9、ribute(3,n,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<stdio.h>#include <malloc.h>#define N 100int qN=0;/全局变量int minexpense=-1;/最小费用void workdistri

10、bute(int i,int n, int p,int x,int cN);/递归函数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(&

11、quot;%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");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(i<n)w

12、orkdistribute(i+1,n,p,x,c);else/判断最后一事件分配完后，判断此次分配是不是最小费用if(minexpense>x0|minexpense=-1)/如果是最小分配或第一次分配，则保存此次分配数据minexpense=x0;for(int k=1;k<=n;k+)qk=pk;xj=0;x0-=cij;/当此事件及以后的事件分配完后，/返回上事件进行下一次分配前减去此次事件分配所需费用1.6运行结果2、 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？要求对每种物品i装入

13、背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i（要求使用递归法实现）。2.1设计算法在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i，因此，该问题称为背包问题。此问题的形式化描述是，给定C>0,wi,vi>0，1in,要求找出n元0-1的向量(,.,),0,1,1in,使得C，而且达到最大。因此，0-1背包问题是一个特殊的整数规划问题。设所给0-1背包问题的子问题的最优值为m(i,j),即m(i,j)是背包容量为j,可选物品为i,i+1，···,n时0-1

14、背包问题的最优值。由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<=j)mij=vi;xi=1;elsemij=0;else if(i>=1)/装不是最底层物品时knapsack(i+1,n, v,w,c,m);/继续递归，装i层下物品for(int j=1;j<=c;j+)if(j>=wi&am

15、p;&mi+1j<=mi+1j-wi+vi)/当背包容量不小于物品重量时的最优放法mij=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<=j是mij=mij=vi;xi=1;即m4

16、1m48值为0,0,3,3,3,3,3,3;返回上一层i=3,j从1循环到c时if(j>=wi&&mi+1j<=mi+1j-wi+vi)时用mij=mi+1j-wi+vi计算出mij值，反之mij=mi+1j，计算第3层时，第4层以计算出，得第三层m31m38值为 0, 4, 4, 4, 7, 7, 7, 7；然后返回第二层同样方式得m21m28值为0, 4, 4, 4, 7, 7, 7, 7；返回到第一层，此时计算出第一层值m11m182, 4, 6, 6, 6, 7, 9, 9, 9。此时判断条件if(i=1)成立，计算最优解w0保存的是物体的个数n，当i不大于

17、物品个数时，通过判断if(mic=mi+1c，当背包价值数组第i行最后的值于下行最后值相同，第i个物品不放，m18=9m28=7,所物品1放入，m28=m38=7,物体2不放入背包，m38=7m48=3所以物体3放入,而m58=0m48,物体4也放入，此时调用traceback(i+1,m,w,c-wi);后i=5>n=4，返回上一层，递归结束x1x4=1,0,1,1;回到main函数输出背包最大价值9，以及放入物品重量和价值1,2，2,4，3,3。程序结束。2.5程序源代码及注释#include<stdio.h>#define N 50int knapsack(int i,

18、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(&qu

19、ot;%d",&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);/输出所放物品重量和价值scan