《算法分析与设计》期末考试总结复习习题纲完整版

欢迎阅读

a[p] = a[j]; a[j] = x; return j; }

3. 用贪心算法求解最优装载问题。 最优装载问题 P95 课件第4章(2)第3-8页 template

void Loading(int x[], Type w[], Type c, int n) {

int *t = new int [n+1]; Sort(w, t, n); for (int i = 1; i <= n; i++) x[i] = 0; for (int j = 1; j <= n && w[t[j]] <= c; j++) {x[t[i]] = 1; c -= w[t[j]];} }

4. 用回溯法求解0-1背包/批处理作业调度 /最大团问题，要会画解空间树。 例1：用回溯法求解0-1背包 P133课件第5章(2)第24-38页 template class Knap {

private: Typep Bound(int i); //计算上界 void Backtrack(int i); Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组 Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最优价值 };

void Knap::Backtrack(int i) { if(i>n) { bestp=cp; return; }

欢迎阅读

if(cw+w[i]<=c) //进入左子树 { cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; }

if(Bound(i+1)>bestp) //进入右子树 Backtrack(i+1); }

Typep Knap::Bound(int i) {

Typew cleft=c-cw; //剩余的背包容量 Typep b=cp; //b为当前价值 //依次装入单位重量价值高的整个物品 while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } if(i<=n) //装入物品的一部分 b+=p[i]*cleft/w[i]; return b; //返回上界 }

class Object //物品类 {

friend int Knapsack(int *,int *,int,int); public: int operator <(Object a) const { return (d>=a.d); } int ID; //物品编号 float d; //单位重量价值 };

Typep Knapsack( Typep p[],Typew w[],Typew c,int n) { //为Typep Knapsack初始化 Typew W=0; //总重量 Typep P=0; //总价值

Object* Q=new Object[n]; //创建物品数组，下标从0开始

欢迎阅读

for(int i=1;i<=n;i++) //初始物品数组数据 { Q[i-1].ID=i;

Q[i-1].d=1.0*p[i]/w[i]; P+=p[i]; W+=w[i]; }

if(W<=c) //能装入所有物品 return P;

if(W<=c) //能装入所有物品 return P; QuickSort(Q,0,n-1); //依物品单位重量价值非增排序 Knap K; K.p=new Typep[n+1]; K.w=new Typew[n+1]; for(int i=1;i<=n;i++) { K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; K.Backtrack(1); delete[] Q; delete[] K.w; delete[] K.p; return K.bestp; }

例2：批处理作业调度 课件第5章(2)P2-5问题描述,课本P125-127 解空间：排列树 算法描述： class Flowshop {

static int [][] m, // 各作业所需的处理时间 [] x, // 当前作业调度 [] bestx, // 当前最优作业调度 [] f2, // 机器2完成处理时间 f1, // 机器1完成处理时间 f, // 完成时间和

bestf, // 当前最优的完成时间和 n; // 作业数 static 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];//第j个作业在第一台机器上所需时间 f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2];

欢迎阅读

f+=f2[i];

if (f < bestf) //约束函数

{ Swap(x[i], x[j]); Backtrack(i+1); Swap(x[i], x[j]); } f1 - =m[x[j]][1]; f - =f2[i]; } }

例3：最大团问题，要会画解空间树。 class Clique {

friend int MaxClique(int **,int [],int); public: void Print(); //输出最优解 private: void Backtrack(int i); int **a; //图G的邻接矩阵，下标从1开始 int n; //图G的顶点数 int *x; //当前解 int *bestx; //当前最优解 int cn; //当前团的顶点数 int bestn; //当前最大团的顶点数 };

void Clique::Backtrack(int i) { if(i>n) { for(int j=1;j<=n;j++) bestx[j]=x[j]; bestn=cn; return;} //判断第i个顶点是否与已选顶点都有边相连 int OK=1; for(int j=1;j

{ x[i]=1; cn++; Backtrack(i+1); x[i]=0; cn--; } if(cn+n-i>bestn) //如有可能在右子树中找到更大的团，则进入右子树 { x[i]=0; Backtrack(i+1); } }

计算时间：O(n2n) 四、 简答题