回溯法求解 template<class T> g (int i) template<dass T> (>n){/在叶结点上 class Loading friend MaxLoading(T[, T, int); /检查子树 privat r-=w[] void maxLoading(int i); if(cw+w[]<=c)【∥/尝试x[i=1 /货箱数目 cw +=w[] /货箱黛量数组 Cw-= w[:y ∥/第一艘船的容量 if(cw+r> best)∥/尝试x[i=0 /当前装载的重量 m axLoading(i+1) /目前最优装载的重量 } m=4,W=[8,6,2,3],c=12 搜索前进到第一个叶结点(的右孩子 besty被置为10。回溯到E,然后向下移 动到K的左孩子此时 best被更新为11 n我们没有移动到K的右孩子,因为在右孩子 结点cW=8,r=0 到结点A。同样,不必移动到右孩子C,因 为在C点cW=0,r=11且cW+r≤ best =[8,6,2,3],c=12 回滴算法 分支限界法 分支限界法 队列式分支限界法 函数 EnQueue用于将活动结点加入到队列中。 Q用于存放活动结点表,Q中用EW表示每个活 动结点所相应的当前载重量,当EW=-1时 Void EnQueue( queue<Type> &Q, Type wt, 表示队列已到达解空间树同一层结点的尾 Type best int i, int n) if(i==n)//该结点为叶结点,不再扩展 if( wt best)best wt; else Q. Add( wt i回溯算法 49 回溯法求解 template<class T> class Loading { friend MaxLoading(T [], T, int); p r i v a t e : void maxLoading(int i); int n; // 货箱数目 T *w, // 货箱重量数组 c, // 第一艘船的容量 cw, // 当前装载的重量 bestw; // 目前最优装载的重量 } ; 回溯算法 50 template<class T> void Loading<T>::maxLoading(int i) { // 从第i 层结点搜索 if (i > n) {// 在叶结点上 bestw = cw; r e t u r n ; } // 检查子树 r -= w[i]; if (cw + w[i] <= c) { //尝试x[i] = 1 cw += w[i]; m a x L o a d i n g ( i + 1 ) ; cw -= w[i]; } if (cw + r > bestw) //尝试x[i] = 0 m a x L o a d i n g ( i + 1 ) ; r += w[i]; } 回溯算法 51 „ n= 4，w= [ 8 , 6 , 2 , 3 ]，c = 12 。 „ 搜索前进到第一个叶结点（J的右孩子）。 bestw 被置为10。回溯到E，然后向下移 动到K的左孩子此时bestw被更新为11。 „ 我们没有移动到K的右孩子，因为在右孩子 结点cw=8，r=0，cw+r≤bestw。回溯 到结点A。同样，不必移动到右孩子C，因 为在C点cw=0，r=11且cw+r≤bestw。 回溯算法 52 w= [ 8 , 6 , 2 , 3 ]，c = 12 cw=0 r=19 1 cw=8 r=11 0 1 1 0 0 cw=8 r=5 cw=10 r=3 bestw=10 cw=8 r=3 cw=11 r=0 bestw=11 0 cw=0 r=11 cw+r<=bestw J K E A B C L M 回溯算法 53 分支限界法 „ 队列式分支限界法 Q用于存放活动结点表，Q中用Ew表示每个活 动结点所相应的当前载重量，当Ew=-1时， 表示队列已到达解空间树同一层结点的尾 部。 回溯算法 54 分支限界法 函数EnQueue用于将活动结点加入到队列中。 Template <class Type> Void EnQueue( Queue<Type> &Q, Type wt, Type & bestw, int i, int n) { if( i == n ){ //该结点为叶结点 ，不再扩展 if( wt > bestw ) bestw = wt; } else Q.Add( wt ); }