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

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，由于，背包w1还可以装入x1=0.85，则背包内物品总价值为

15+15+20*0.85＝47.

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

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

如果装到pi-1再装pi时，恰好要取xi个wi。（）

因为比它价值密度大的都已装载完，所以此时获得的为最优解。

（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; 

} 

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中选择一个顶点，使得它所覆盖的未被覆盖的顶点数目最多。给出这种贪婪算法的伪代码。

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

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个是假币，且假币较轻。请用分而治之方法设计一个找出假币的算法。

1）用伪代码描述你的算法；2）用C程序描述你的算法；3）分析你的算法的时间复杂性。

解答：代码如下

Feit_money(low, high) // 假定伪币较真币轻

{

float mid;

if  high-low=1  then

if A[low] else 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).

6、大整数乘法。

1）请用分而治之算法计算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=(13)'     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

|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;

}

该算法的运行时间满足的递归方程为：                             ，

计算得其时间复杂度为：T(n)=O()。

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;

if (sum if (sum  }

  return 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]];    }

    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背包问题为：。条件为：，且，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）

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;

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]; }

        printf("%d\\n",mx);        cnt = 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",r[1]);

     for(i = 2;i <= n;i++) printf("-%d",r[i]);

        printf("\\n");

    }

    return 0;}

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

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

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

解答：

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

解空间树

             ︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰︰

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个作业的排列树如下所示：

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，用伪代码写出求解子集和问题的回溯算法。

解答：

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) 设计回溯算法求解该问题.

解答：

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(temp   {

       best=temp;

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

    }

}

8、对于以下5 个矩阵：

A1: 105, A2: 54, A3: 49, A4: 910, A5: 102

求出这5个矩阵相乘需要的最小数乘次数及相应的加括号方式.

   （注：要求给出计算公式和计算过程）

解答：计算公式为：

例如：

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

{

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; i  vertex[i]=a[i];

    for(i=0; i        for(j=0; j   arc[i][j]=0; 

 for(k=0; k {

  cout<<"请输入边连接的两点:";

     cin>>i>>j;     //边依附的两个顶点的序号

        arc[i][j]=1;

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

    }

 cout<<"输入完毕"<} 

void Mgraph::BFSTraverse( )   //广度优先遍历算法

{

 for(i=0;i       visited[i]=0;

    for(i=0;i      if(visited[i]==0)

   BFSTraverse(i);

}