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;imax) max=A[i]; if (A[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 void Perm(Type list[],int k,int m) { if(k= =m){ for(int i=0;i<=m;i++) cout< int ok(Type list[],int k,int i) { if(i>k) for(int t=k;t

动态规划算法实现0-1闭包问题，请写出该算法。 解：解答如下： Template void Knapsack(Type v,int w,int c,int n,Type **m) { Int jMax=min(w[n]-1,c); for(int j=0;j<=jMax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; for(int i=n-1;i>1;i--){ jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j];

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 Void Traceback(Type **m,int w,int c,int n,int x) { for(int i=1;i

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 int BinarySearch(Type a[],const Type& x,int n) {//假定数组a[]已按非递减有序排列，本算法找到x后返回其在数组a[]中的位置，//否则返回-1 int left=0,right=n-1; while(left<=right){ int middle=(left+right)/2;

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。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下

方

式

求

得

：