发布时间 : 星期六 文章算法分析与设计复习题及参考答案更新完毕开始阅读13b82668abea998fcc22bcd126fff705cc175cff
x=615×x=625543××x=24433???? 即有4个可行解：
（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。 11、设数组A有n个元素，需要找出其中的最大最小值。 （1） 请给出一个解决方法，并分析其复杂性。 （2） 把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。 解：（1）基本思想：从头到尾逐个扫描，纪录最大和最小元素。 输入：具有n个元素的数组 输出：最大值和最小值 步骤：
void FindMaxMin(int A[], int n, int max, int min) { max=min=A[0]; for (i=1;i max=(A[left] } A[left] else{ mid=(left+right)/2; FindMaxMin(left,mid,gmax,gmin); FindMaxMin(mid+1,right,hmax,hmin); max=(gmax min=(gmin 12、有n个程序 和长度为L的磁带，程序i的长度为a，已知 ，求最优解(x，x ，...，x，…，ii2i 1 n x)，x =0，1, x =1，表示程序i 存入磁带，x =0，表示程序i不存入磁带，满足，且存放 niii 的程序数目最多。 解：由于目标是存放的程序数目最 多，所以最优量度应该是 min{a| a为程序i的长度}， i i即每次选入的程序都是当前最短的。我们可以将n个程序按a[1]≤a[2]≤…≤a[n]顺序排序，然后从i=1开始依次选择。算法如下： procedure programming(L,n, a, x) begin //n个程序按a[1]≤a[2]≤…≤a[n]顺序排序 x←0; i=1; while (a[i] ≤L and i≤n) do { x[i] ←1; L←L-a[i]；i←i+ 1; } end. 13、试用分治 法实现有重复元素的排列问题：设是要进行排列的个元素，其中元素 12nr,r,...,rR可能相同，试设计计算的所有不同排列的 算法。 12n 解：解答如下： Template 动态规划算法实现0-1闭包问题，请写出该算法。 解：解答如下： Template for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); }; m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } Template 15、试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，请写出该算法。 解：解答如下： void dicomp(int n,int a[]) { k=1; if(n<3){ a[1]=0;return;}; if(n<5){ a[k]=1;a[++k]=n-1;return;}; a[1]=2;n-=2; while(n>a[k]){ k++; a[k]=a[k-1]+1; n-=a[k]; }; if(n= =a[k]){ a[k]++;n--;}; for(int i=0;i if(x= =a[middle]) return middle+1; if(x>a[middle]) left=middle+1; else right=middle-1; } return -1; } 17、试用动态规划算法实现最长公共子序列问题，请写出该算法。 解：用动态规划算法求解的算法代码如下： int lcs_len(char *a,char *b,int c[][N]) { int m=strlen(a),n=strlen(b),i,j; for(i=0;i<=m;i++) c[i][0]=0; for(j=1;j<=n;j++) c[0][j]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(a[i-1]= =b[j-1]) c[i][j]=c[i-1][j-1]+1; else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j]; else c[i][j]=c[i][j-1]; return c[m][n]; }; char *build_lcs(char s[],char *a,char *b) { int k,i=strlen(a),j=strlen(b),c[N][N]; k=lcs_len(a,b,c); s[k]=’\\0’; while(k>0){ if(c[i][j]= =c[i-1][j]) i--; else if(c[i][j]= =c[i][j-1]) j--; else{ s[--k]=a[i-1]; i--,j--; } } return s; } 18、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题，请写出状态空间搜索树。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 解：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下 方 式 求 得 ：