《算法分析与设计》期末考试复习题纲（完整版）要点 - 图文

Partition函数的具体实现 template

int Partition (Type a[], int p, int r) {

int i = p, j = r + 1; Type x=a[p];

// 将< x的元素交换到左边区域 // 将> x的元素交换到右边区域 while (true) {

while (a[++i] x); if (i >= j) break; Swap(a[i], a[j]); } 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]];} }

5

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为当前价值 //依次装入单位重量价值高的整个物品

6

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); //依物品单位重量价值非增排序

7

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

8

}