算法设计与分析习题 - 图文

个人精品文档资料

③计算最优值m(i，j)

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

if ( M=w[ n])

{ m[ n][ M]=v[ n]; M=M-w[ n]; }

for( int i=n-1; i>=1; i--) // i

m[ i] [M]=m[ i+1][ M]; else if (M>=w[ n])

{ m[ i][ M]=math.max( m[ i+1][ M], m[ i+1][M-w[ i]+v[i]); M=M-w[ i]; } } }

? 该算法时间复杂度：O(c*n) c常数 ④构造最优解

void trackack( int m[ ] [ ], int w[ ], int M, int x[ ] ) {//x[ i]标记i是否放入背包 int n=w.length;

for( int i=1; i

{ x[ i]=1; M=M-w[ i]; } }

x[ n]=(m[ n][ M]>0)? 1:0 ; //判断第n个物体是否放入背包 }

? 该算法时间复杂度：O(n)

第 4 章 贪心算法

1、 贪心算法基本思想？

答：从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择（贪心选择），最终得到整个问题的最优解

2、 贪心算法的基本要素？

答：贪心选择性； 最优子结构

3、 贪心算法与动态规划算法的异同?

答：1 ） 相同点： 对于要求解的问题都具有最优子结构；

2 ）不同点： 算法的基本思想不同； 求解问题的类型不同； 例：普通背包问题 贪心算法求解

欢迎大家下载学习

11

个人精品文档资料

0-1背包问题 动态规划算法求解

4、设计普通背包装载问题的贪心算法? 并分析其时间复杂度？ 答：

float greedy_knapsack ( float M, float w[ ], float p[ ], float x[ ] ) // M 背包载重 x[ ]背包问题最优解, w[ ]物品重量， P[ ]物品价值 { int n=w.length; //n物品的个数

float pp=0; //pp计算当前背包总价值 float mm＝M; //mm背包剩余载重 for( int i=1;i<=n; i++ )

{ float ww[ i]= p[ i] / w[ i]； //计算物品单位价值ww[ ]

x[ i]=0; } //初始化，所有物品没有放入背包 Mergesort (w[ i ], ww[ i]，n ); //按单位价值将物品排序，便于贪心选择 for( int i=1; i<=n; i++ ) //贪心选择，总是选择价值最大放入背包 { if ( w[ i]<=mm ) //当前物品小于背包剩余载重

{ x[ i]=1; mm=mm - w[ i]; pp=pp + p[ i]; } //整个放入背包

else { x[ i]=mm/w[ i]; pp=pp + x[ i]*p[ i]; break; } //i部分放入背包 }

return pp; }

该算法主要包括以下几部分：

? 计算物品单位价值时间，其时间复杂度O(n)；

? 按照物品单位价值排序时间，其时间复杂度为O(n*logn); (合并排序时间) ? 贪心选择时间，其时间复杂度为O(n)；

故该算法的时间复杂度为：O(n*logn+2n)； 记为： O(n*logn)

5、设计找零问题的贪心算法? 并分析其时间复杂度？

答：void greedy_zhaoling ( float GZ, int B[ ], int S[ ] ) //GZ应发工资 { B[ j]初始化排序； //为了贪心选择，依次选最大币种 for( j=1, j<=6;j++)

{ S[ j]=0； //初始化S[ j]

A=GZ/B[ j]; //A表示对应j币种张数 S[ j]=A; //S[ j]存放对应j币种总张数 GZ=GZ-A*B[ j]; }

//每求出一种面额所需的张数后， 一定要把这部分金额减去： for(i=1;i<=6;i++)

print( B[ i], “----”, S[ i]); //输出币种和对应张数 }

6、设计活动安排问题的贪心算法? 并分析其时间复杂度？ 答：伪代码：

Int greedyselector(int s[ ], int f[ ], boolean a[ ])

{int n=s.length; //n活动的个数 ；a[ ]按活动结束时间递增排序；//便于贪心选择 a[1]=true; //活动１被选中

欢迎大家下载学习

12

个人精品文档资料

int j=1; //j记录最近加入活动集合A的活动j int count=1; //count存储相容活动个数

for(int i=2; i<=n; i++)//贪心选择从活动j=2…n判是否可加入A { if( 活动i的开始时间，大于 最近活动j的结束时间 ) {将活动i加入活动集合A；

j=i; //活动i作为最近加入活动集合A的最近活动 count++; } else

活动i不加入活动集合A；} return count; }

程序设计语言：

Int greedyselector(int s[ ], int f[ ], boolean a[ ]) { int n=s.length; //n活动的个数

Mergesort (a[ ],f[ ], n ); //按活动结束时间排序，便于贪心选择 a[1]=true; //活动１被选中

int j=1; //j记录最近依次加入活动集合A的活动j int count=1; //count存储相容活动个数

for(int i=2; i<=n; i++) //贪心选择从活动i=2…n判是否可加入A { if( s[ i]>=f[ j] )

{ a[ i]=true; //将活动i加入活动集合A

j=i; //活动i作为最近加入活动集合A的最近活动 count++; }

else a[ i]=false; // s[ i]

return count; }

该算法主要包括２部分：

? 按照按活动结束时间对活动排序时间，其时间复杂度为：O(n*logn)； ? 贪心选择时间，其需要经过n-1次的比较（s[ i]>=f[ j]） 时间复杂度为：O(n-1);

故本算法的时间复杂度： O(n*logn＋n-1)； 记为： O(n*logn)。

7、掌握例dijkstra算法的求单源最短路径问题。 算法设计？求解过程？答:

void dijkstra (int v, float a[][], float dist[]) { //v表示源,a[i][j]表示边i到j的权值 //dist[i]记录源到顶点i的最短路径长度

//prev[i]记录顶点i的前一个点,可以找出最短路径 int n=dist.length;

boolean s[ ]; //s[i]标记顶点i是否加入顶点集合s if( v<1 || v>n) return; //源点v不存在 for(int i=1;i<=n;i++)

欢迎大家下载学习

13

个人精品文档资料

{ dist[i]=a[v][i]; //初始化数组dist[i]、s[i] s[i]=false;

if(dist[i]=max-value) //源到顶点i没有边 prev[i]=0; else prev[i]=v; }

dist[v]=0; s[v]=true; //把源v加入到集合s中

for(int i=1; i

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

//贪心选择，计算V-S中顶点的dist[ ]值，选择最小的那个顶点j if( (!s[j]) &&(dist[j]

s[u]=true; //源到顶点u的最短路径已经确定，u加入到s中

for(int j=2;j<=n;j++) //根据u重新计算dist[ ] if( (!s[j]) &&(a[u][j]< max-value) //u到j有边 float newdist=dist[u]+a[u][j]; if(newdist

该算法主体有两重循环，故该算法的时间复杂度记为O(n2

)

8、P126图４－８求最小生成树，写出其prim算法？ 并给出其选边过程?

答：

prim算法描述(伪代码)

void prim(int n, float c[][])//c[][]存储边权值 { T=空集； //T表示最小生成树的边集合 S={ 1 }; //S表示最小生成树包含的顶点集合 while( S!=V ) {选择边（i，j），i∈S 且j ∈V-S；且权值c[i][j]最小； //贪心选择

T=T∪ {（i，j）}; S=S∪{ j }； } }

欢迎大家下载学习

14

个人精品文档资料

prim算法描述(程序设计语言)

Void prim (int n, float c[][])

{float lowcost[ ]; float closest[ ]; boolean s[ ]; s[1]=true; //初始化，顶点1加入生成树集合s

for(int i=2;i<=n;i++) //初始化，计算与顶点1相邻顶点边权值 { lowcost[i]=c[1][i]; colsest[i]=1; s[i]=false; }

for(int i=1;i

for( int k=2;k<=n; k++) //贪心选择,v-s中找使lowcost[]最小的顶点k if((lowcost[k]

s[j]=true; //把找到的顶点j加入到生成树集合s中

for(int k=2;k<=n; k++) //根据刚加入的顶点修改lowcost, closest if((c[j][k]

{lowcost[k]=c[j][k]; closest[k]=j;} } }

该算法主体有两重循环，故该算法的时间复杂度记为O(n2

) Prim算法执行过程：

首先，找出V-S中使lowcost值最小的顶点j(距离s最近的顶点j); 然后，根据数组closest选取边(j,closest[j］)；

最后，将j添加到S中，并对closest和lowcost作必要的修改。 选边过程：

9、P126图４－８，利用kruskal算法求最小生成树， 给出其选边过程？

答：伪代码：

void krustral(int n, float c[][])//c[][]存储边权值 { mergesort（float c[][], T[]）; //按边权值排序 T=空集； //T表示最小生成树的边集合 while( |T|

欢迎大家下载学习

15