4. 用回溯法求解0-1背包/批处理作业调度 /最大团问题，要会画解空间树。 例1：用回溯法求解0-1背包 P133课件第5章(2)第24-38页 template
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
if(Bound(i+1)>bestp) //进入右子树 Backtrack(i+1); }
Typep Knap
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.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
}
例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 { OK=0; break; } //只要与当前团中一个顶点无边相连，则中止 if(OK) //进入左子树 9 { x[i]=1; cn++; Backtrack(i+1); x[i]=0; cn--; } if(cn+n-i>bestn) //如有可能在右子树中找到更大的团，则进入右子树 { x[i]=0; Backtrack(i+1); } } 计算时间：O(n2) n 四、 简答题 1. 请简述使用动态规划算法解题的基本步骤。P44 动态规划的设计分为以下4个步骤： (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 2. 简述动态规划方法与分治法的异同。P44 相同点：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。 不同点：分治法的子问题互相独立且与原问题相同。与分治法不同的是，适合于动态规划求解的问题，经分解得到的子问题往往不是互相独立的。也就是各个子问题包含公共的子子问题。 3. 试比较Prim算法与Kruskal算法的异同。105-P107 相同点：Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法都可以看作是应用贪心算法构造最小生成树的例子。利用了最小生成树性质。 不同点： 10