《算法分析与设计》作业答案

1、考虑0xi1,而不是xi∈{0，1}的连续背包问题。一种可行的贪婪策略是：按价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其装入；否则，往背包内装如此物品的一部分。

(a) 对于n=3，w=[100,10,10]，p=[20,15,15]，以及c=105，上述装入法获得结果是什么？

(b)证明这种贪婪算法总能获得最优解。 (c) 用伪代码描述此算法。

答：（a）利用贪婪算法，按价值密度考察的背包为w2，w3，w1；

背包w2和w3重20，还可以容纳85，由于0xi1，背包w1还可以装入x1=0.85，则背包内物品总价值为

15+15+20*0.85＝47.

（b）假设已按价值密度排好序，考察w1,w2,……,wi，……，

对应的价值为p1,p2,……,pi,……

如果装到pi-1再装pi时，恰好要取xi个wi。（0xi1,） 因为比它价值密度大的都已装载完，所以此时获得的为最优解。 （c）算法描述如下： template

int ContainerLoading( int x[], T w[], T c, int n ) {

int *t = new int[n+1]; IndirectSort(w, t, n); for( int i=1; i<=n; i++) x[i] = 0;

for(i=1; i<=n && w[t[i]]<=c; i++){ x[t[i]] = 1; c += w[t[i]]; } delete []t; }

1

2、证明当且仅当二分图没有覆盖时，下述算法找不到覆盖。 m＝0; //当前覆盖的大小

对于A中的所有i，New[i]=Degree[i] 对于B中的所有i，Cov[i]=false

while(对于A中的某些i，New[i]>0) {

设v是具有最大的New[i]的顶点；C[m++]=v; for(所有邻接于v的顶点j) { If(!Cov[j]) {

Cov[j] = true;

对于所有邻接于j的顶点，使其New[k]减1 }}}

if (有些顶点未被覆盖) 失败

else 找到一个覆盖2）给出一个具有覆盖的二分图，使得上述算法找不到最小覆盖。

证明：如果二分图有覆盖，则通过以上贪婪算法，总能得到最小覆盖A’。 首先假定A’为空集

当更多的顶点可被覆盖时，把能覆盖未被覆盖的顶点数目最多的顶点加入A’ 如果有些顶点未被覆盖，则失败， 否则总能找到一个覆盖。

所以只有当二分图没有覆盖时，才会失败而找不到覆盖， 否则总能找到一个覆盖A’。 2）

令S= {S1，. . .，S5 },

U= { 4，5，. . .，15}, S1 = { 4，6，7，8，9，1 3 }， S2 = { 4，5，6，8 }，

S3 = { 8，1 0，1 2，1 4，1 5 }， S4 = { 5，6，8，1 2，1 4，1 5 }， S5 = { 4，9，1 0，11 }。

通过以上算法，得S ' = {S1，S2，S4，S5 }

实际最小覆盖为{S1，S4，S5 }

3、对于二分图覆盖问题设计另一种贪婪启发算法，贪婪准则是：如果B中某一个顶点被A中一个顶点覆盖，选择A中这个顶点；否则，从A中选择一个顶点，使得它所覆盖的未被覆盖的顶点数目

2

最多。给出这种贪婪算法的伪代码。

解答：贪婪算法的伪代码为:

m=0 // 当前覆盖的大小

对于A 中的所有i, Out[i]=outdegree[i]; 对于B 中的所有i, In[i]=indegree[i]; 对于B 中的所有i, Cov[i]=false;

for (对于B中所有入度为1的顶点i) { 设v是邻接于B[i]的顶点 C[m++]=v; for (所有邻接于v的顶点 j) { if (!Cov[j]) { Cov[j]=true;

对于所有邻接于j的顶点，使其Out[k]减1 } } }

while (对于A 中的某些i, Out[i]>0) { 设v是具有最大Out[i]的顶点 C[m++]=v;

for (所有邻接于v的顶点 j) { if (!Cov[j]) { Cov[j]=true;

对于所有邻接于j的顶点，使其Out[k]减1 } } }

if (有些顶点未被覆盖) 失败 else 找到一个覆盖

4、有n个硬币，其中1个是假币，且假币较轻。请用分而治之方法设计一个找出假币的算法。

3

1）用伪代码描述你的算法；2）用C程序描述你的算法；3）分析你的算法的时间复杂性。 解答：代码如下 Feit_money(low, high) // 假定伪币较真币轻 {

float mid;

if high-low=1 then

if A[low]A[high] return A[high]; else

mid=(low+high)/2;

if (high-low+1)%2==0 then

sum1=sum(low, mid); sum2=sum(mid+1, high); else

sum1=sum(low, mid-1); sum2=sum(mid+1, high); end if

if sum1=sum2 then return A[mid]; else if sum1(high-low+1)%2==0? Feit_money(low, mid) : Feit_money(low, mid-1); else

Feit_money(mid+1, high); end if end if

return 0; }

其时间复杂度为：O(log n).

用分而治之算法计算4823*9715；

2）假设两个大整数都是n=2k位，请用伪代码描述两个大整数乘积的分而治之算法。

解答：

1) 设X=4823, Y=9715，用上述算法计算XY的计算过程可列表如下，其中带'号的数值是在计算完成AC，BD，和(A-B)(D-C)之后才填入的。

X=4823 A=48 B=23 A-B=15

Y=9715 C=97 D=15 D-C=82

AC=(1643)' BD=(1107)' (A-B)(D-C)=(260)' XY=(4496)'104+[(4496)'+(345)'+(1230)']102 +(345)' =(45567445)' 进一步拆分

A=48 A1=4 B1=8 A1-B1=-4 C=97 C1=9 D1=7 D1-C1=2 A1C1=36 B1D1=56 (A1-B1)(D1-C1)=-8 AC=3600+(36+56-8)10+56=4496 B=23 A2=2 B2=3 A2-B2=-1 D=15 C2=1 D2=5 D2-C2=4 A2C2=2 B2D2=15 (A2-B2)(D2-C2)=-4 BD=200+(2+15-4)10+15=345

4

|A-B|=15 A3=1 B3=5 A3-B3=-4 |D-C|=82 C3=8 D3=2 D3-C3=-6 A3C3=8 B3D3=10 (A3-B3)(D3-C3)=24 (A-B)(D-C)=800+(8+10+24)10+10=1230 2)

mul(x, y, n) {

if (2<=n && x!=0 && y!=0) { k=n/2;

p = power(10, k); b= x % p; a=x/p; d=y % p; c=y/p;

ac=mul(a, c, k); bd=mul(b, d, k);

mix=mul(a-b, d-c, k);

return (ac*p+(mix+ac+bd)*p+bd); }

else if (x==0||y==0) return 0;

else x*y; }

O(1)n1该算法的运行时间满足的递归方程为：T ( n )   ， 计算得其时间复杂度为：T(n)=O(nlog23)。

3T(n/2)O(n)n1

7、设计一个分而治之算法来计算二叉树中分支结点的个数。请用伪代码描述你的算法。请分析算法的时间复杂度。

解答：算法伪代码如下：

int MaxSubSum(int a, int left, int right) { int sum=0;

if (left==right)sum=a[left]>0?a[left]:0; else{int center=(left+right)/2;

int leftsum=MaxSubSum(a,left,center);

int rightsum=MaxSubSum(a,center+1,right); int s1=0;lefts=0;

for (int i=center;i>=left;i--) { lefts+=a[i];

if (lefts>s1) s1=lefts; }

int s2=0;rights=0;

for (int i=center+1;i<=right;i++) { rights+=a[i];

if (rights>s2) s2=rights; }

sum=s1+s2;

5

if (sumreturn sum; }

算法时间复杂度为：

8、货物装箱问题：设有一艘货船装货箱。共有n=6件货箱，它们的重量如下表示：[w1,…, w6] = [100, 200, 50, 90, 50, 20]，船的限载重量是c=300。试用贪婪算法装船，要求货箱装得最多。贪婪准则：从剩下的货箱中选择重量最小的货箱。

1） 请给出问题的解；

2） 对一般的n，重量为w=[w1,…, wn]，船的限载重量是c>0，要求船的货箱装得最多，请用伪代码描述你的算法；

3） 考虑有两条船的情况，即有两条船，船的限载重量是分别是c1和c2；共n件货箱，重量为w=[w1,…, wn]，试用贪婪算法装船，要求两条船的货箱装得最多。请描述你的算法，该算法总能产生最优解吗？请说明你的理由。

解答：1）货箱按重量从小到大排列，得{20,50,50,90,100,200}.根据选择最小重量货箱的贪婪准则，则准箱顺序为{w6,w3,w5,w4,w1,w2}，因为船限载重量c=300，故实际装箱为w6,w3,w5,w4共4个货箱重210。

2）算法如下

template

int ContainerLoading( int x[], T w[], T c, int n ) { int *t = new int[n+1];

IndirectSort(w, t, n);//对重量按间接寻址方式排序 for( int i=1; i<=n; i++) x[i] = 0;

for(i=1; i<=n && w[t[i]]<=c; i++){ x[t[i]] = 1; //t[i]是间接寻址表 c -= w[t[i]]; }

6

复杂性分析：TnTnO1nc2TnOnnc2Onlogn delete t[];}

3）伪代码如下：

void knapsack(int v[ ], int w[ ], int c, int m[ ][ ]) { int n=v.length-1;

int jMax=min(w[n]-1,c);

for( int j=0; j<=jMax; j++) m[n][j]=0;

for( int j=w[n]; j<=2*w[n]-1; j++) m[n][j]=v[n];

for( int j=2*w[n]; j<=c; j++) m[n][j]=2*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<=2*w[i]; j++)

m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i]);

for(int j=2*w[i]; j<=c; j++)

m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i], m[i+1][j-2*w[i]]+2*v[i] ); }

m[1][c]=m[2][c]; if (c>=2*w[1])

m[1][c]=max(m[1][c], m[2][c-w[1]]+v[1], m[2][c-2*w[1]]+2*v[1]); else if (c>=w[1])

m[1][c]=max(m[1][c], m[2][c-w[1]]+v[1]);} 显然，该算法能产生最优解。

二、习题（15、16、17章）

1、定义0/1/2背包问题为：max{ni1pixi}。限制条件为：

ni1wixic，且

xi{0,1,2},1in，f(i , y)表示剩余容量为y，剩余物品为：i，i+1，…，n时的最优解的

值。

1）推出f(i , y)的递推表达式（类似于15-1和5-2式）；

2）请设计求解f(i , y)的算法，并用伪代码描述你的算法； 3）分析你的算法的复杂性。

4）设W=[10,20,15,30,10]，P=[6,10,15,18,5],c=78，请用你的算法求解。 解答： 1）

max(f(i1,y),f(i1,ywi)vi,f(i1,y2*wi)2*vi,cy2*wif(i,y)max(f(i1,y),f(i1,ywi)vi),2*wiywif(i1,y) 0ywi

2vn,2wnycf(n,y)vn,wny2wn0,0ywn

7

2)

void knapsack(int v[ ], int w[ ], int c, int m[ ][ ]) {

int n=v.length-1;

int jMax=min(w[n]-1,c); for( int j=0; j<=jMax; j++) m[n][j]=0;

for( int j=w[n]; j<=2*w[n]-1; j++) m[n][j]=v[n];

for( int j=2*w[n]; j<=c; j++) m[n][j]=2*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<=2*w[i]; j++)

m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i]);

for(int j=2*w[i]; j<=c; j++)

m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i], m[i+1][j-2*w[i]]+2*v[i] ); }

m[1][c]=m[2][c]; if (c>=2*w[1])

m[1][c]=max(m[1][c], m[2][c-w[1]]+v[1], m[2][c-2*w[1]]+2*v[1]); else if (c>=w[1])

m[1][c]=max(m[1][c], m[2][c-w[1]]+v[1]); }

2、有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最小。设计算法求解该问题

9

12 15

10 6 8 2 18 9 5

19 7 10 4 16

解答：程序如下：

#define Min(a,b) ((a)<(b)) ? a: b

#define max 104

int r[max],s[max][max],t[max] , dp[max][max]; int main()

{ int n , i , j , mx , ca , lo ,cnt ; scanf( \"%d\" , &ca ); while( ca-- )

{ scanf( \"%d\" , &n ); mx = 214000000;

8

for ( i = 1 ; i <= n ; i++ ) for ( j = 1 ; j <= i ; j++) scanf( \"%d\" , &s[i][j] ); dp[1][1] = s[1][1];

for(i = 2;i <= n;i++) {

{

for(j = 1;j <= i;j++) if(j == 1) dp[i][j] = dp[i-1][j]+s[i][j];

}

else if(j == i) dp[i][j] = dp[i-1][j-1]+s[i][j];

else dp[i][j]=Min(dp[i-1][j-1]+s[i][j],dp[i-1][j]+s[i][j]);}

for(i = 1;i <= n;i++)

if(dp[n][i] < mx) { lo = i; mx = dp[n][i]; }

cnt = n;

printf(\"%d\\n\while(cnt) {

r[cnt] = s[cnt][lo];

if(lo == cnt) lo--;

else if(lo > 1) { if(dp[cnt-1][lo-1] < dp[cnt-1][lo]) lo = lo-1; }

cnt--; } printf(\"%d\

for(i = 2;i <= n;i++) printf(\"-%d\

printf(\"\\n\"); } return 0;}

3、在用回溯法求解0/1背包问题时，

1） 画出该问题的解空间树；

2） 用伪代码描述用于剪枝的限界函数。

解答：

1）这个问题的解可以表示成0/1 数组(x1, x2, . . . , xn )，依据wi 是否属于S，xi 分别取值1 或0。故解空间中共有2^n 个元素。它的树结构是一棵完全二叉树。 解空间树

9

︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰ 2) 限界函数：

double bound(int i)

{// 计算上界

double cleft = c - cw; // 剩余容量 double bound = cp;

// 以物品单位重量价值递减序装入物品 while (i <= n && w[i] <= cleft) {

cleft -= w[i]; bound += p[i]; i++; }

// 装满背包

if (i <= n) bound += p[i] / w[i] * cleft; return bound; }

5、给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理. 作业Ji需要机器j的处理时间为tji. 对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间. 所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和. 批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小. 1) 画出该问题的解空间树； 2) 设计回溯算法求解该问题.

解答：1)解空间树为作业构成的排列数，4个作业的排列树如下所示：

10

2）public class FlowShop

static int n, // 作业数

f1, // 机器1完成处理时间 f, // 完成时间和 bestf; // 当前最优值

static int m[][]; // 各作业所需的处理时间 static int x[]; // 当前作业调度 static int bestx[]; // 当前最优作业调度 static int f2[]; // void backtrack(int i) { if (i > n) {

for(int j = 1; j <= n; j++) bestx[j] = x[j]; bestf = f; } else

for (int j = i; j <= n; j++)

{ f1+=m[x[j]][1];

f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2]; f+=f2[i];

if (f < bestf) { swap(x,i,j);

backtrack(i+1); swap(x,i,j); }

f1-=m[x[j]][1] f-=f2[i];

} }

6、 子集和问题：对于集合S={1，2，6，8}，求子集，要求该子集的元素之和d=9。 a) 画出子集和问题的解空间树；

b) 对该树运用回溯算法，写出依回溯算法遍历节点的顺序表及节点。确定回溯算法未遍历的节点；

c) 如果S中有n个元素，指定d，用伪代码写出求解子集和问题的回溯算法。

11

解答：

1）这个问题的解可以表示成0/1 数组(x1, x2, . . . , xn )，依据wi 是否属于S，xi 分别取值1 或0。故解空间中共有2^n 个元素。它的树结构是一棵完全二叉树。

子集：{1，2 ，6}，{1，8} 解空间树

2）深度优先：结点

0->1->3->7->15->7->16->7->3->8->17->8->18->8->3->1->4->9->19->9->20->9->4->10->21->10->22->10->4->1->0->2->5->11->23->11->24->11->5->12->25->12->26->12->5->2->6->13->27->13->28->13->6->14->29->14->30

3）按照回溯法思想，从状态树的根结点出发，做深度优先搜索； 1.为便于计算，将W中的正数按从小到大排序；

2.当在某一状态A下，依次尝试加入和不加入正数wi， 3.若∑A+wi>d，则可停止对该结点的搜索；

4.若∑A+ ∑(wi…wn) 伪代码算法如下：

设置辅助向量A[i]，记录wi是否被选入；

SW表示W的剩余和，SA表示选入项的总和；

初始化A[i] = -1，表示未被处理过， SW= ∑W， SA=0；

 i=1;

while(i>0)

{ if (i>n) { if (SA==d) 输出 A[1..n]; i- -; } if (A[i]==-1) { A[i]=0;

SW- =wi; A[++i]=-1; } if(A[i]==0) { A[i]=1;

SA+=wi; A[++i]=-1;

if (SA==d) { 输出 A[1..n]; i--; } } If (A[i]==1)

{ A[i]=-1; SW += wi; SA - = wi; --i; } }

7、设有 n 件工作分配给 n 个人。将工作i分配给 j 个人所需的费用为 Cij. 现要求为每个人都分配1件不同的工作，并使总费用达到最小. 1) 画出该问题的解空间树； 2) 设计回溯算法求解该问题.

12

解答：

1) 该问题的解空间树是一棵排列树，4件工作分配给4个人的排列树如下：

2) 参考代码如下：

Void backtrack(int t) {

if ( t>n ) Compute(); else

for (int j=t; j<=n; j++) {

swap(r[t],r[j]); backtrack(t+1); swap(r[t],r[j]); } }

Void Compute()

{

for(int i=1, temp=0; i<=n;i++) temp+=p[i][r[i]]; if(tempbest=temp;

for(i=1; i<=n; i++) bestr[i]=r[i]; } }

8、对于以下5 个矩阵：

A1: 105, A2: 54, A3: 49, A4: 910, A5: 102

求出这5个矩阵相乘需要的最小数乘次数及相应的加括号方式. （注：要求给出计算公式和计算过程）

解答：计算公式为：

0

m[i,j]min{m[i,k]mikj13 [k1,j]pi1pkpj}ijij

例如：

m[2][2]m[3][5]p1p2p5252542292m[2][5]minm[2][3]m[4][5]p1p3p5180180592 m[2][4]m[5][5]ppp5605102145m 1 2 3 4 5 1 0 200 560 960 392 2 0 180 560 292 3 0 360 252 4 0 180 5 0 S 1 2 3 4 5 1 0 1 1 1 1 2 0 2 3 2 3 0 3 3 4 0 4 5 0 加括号的方式为: （A1（A2（A3(A4A5）)））

9、 旅行商问题：给出一个n个顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。任何一个包含所有n个顶点的环路被称作一个旅行。在旅行商问题中，要设法找到一条最小耗费的旅行。

1）对图示的例，画出旅行商问题的解空间树。 2）描述用FIFO分枝定界法解决上述问题的过程；

3）对有n个顶点的网络，用伪代码描述求解旅行商问题的FIFO分枝定界法。

伪代码如下

#include #include const int MaxSize=50; class Mgraph

14

{

private:

int vertexNum, arcNum; //顶点数和边数 int vertex[MaxSize]; //顶点数组 int arc[MaxSize][MaxSize]; //邻接矩阵 int*visited; int i,j,k; public:

Mgraph(int a[], int n, int e);

void BFSTraverse(); //广度优先遍历 void BFSTraverse(int a); int link(int v); };

Mgraph::Mgraph(int a[], int n, int e) {

visited=new int[MaxSize]; vertexNum=n; arcNum=e;

for(i=0; ifor(i=0; ifor(k=0; kcout<<\"请输入边连接的两点:\";

cin>>i>>j; //边依附的两个顶点的序号 arc[i][j]=1;

arc[j][i]=1; //置有边标志 }

cout<<\"输入完毕\"<void Mgraph::BFSTraverse( ) //广度优先遍历算法 {

for(i=0;ifor(i=0;i15