bound函数的计算方法 回溯算法_ knApsack头 ■得到当前结点出发可以达到的可能的最大价值 float btKnapsack(int n, int X[l, float W[, float float M) 从当前部分解(x0x1…x1)开始,采用贪心法计 算一般背包问题的策略,允许最后一个物品被分割 CW=OF Cp=0; 后加入背包,从而得到从结点出发的子树中可以达 for (int i=O;i<n; i++)& 到的总价值的上界 W+=W[ 计算总价值和总盒量 ■如果这个上界小于当前的bp值,说明该子树不 if(cw<=M) return cp;∥/可以 可能包含最优解,就可以被“剪枝”,则将这个 btsort(W, P, n); //按价值量比排序 p=cw= 0; bp=0; 部分解结点变为死结点 backtrack(o,XWPM)∥递归回测 return bp 返回最优解的总价值,同时把最优解放在全局数组Y[中 递归函数: backtrack() void backtrack(int i, int xII, float w[, float /W存储各物品量量 Po, float)t if( cw+ W[]<=Mt /取物品 /已到叶结点,取得当前最大价值,回溯 P是存储各物品价值的数组 if(cp> bpt cktrack(+1XWPM);//前进,搜囊 bp cpi CW-= W[]; /回溯,消除标记 for(int j=OF; j<n; j++) YU= xU] if( bound(i+1,WP)>b){//不取物品 X[i]=0 return; track(i+1,xW,P,M);∥/前进,搜索 回滴算法 限界函数 bound() 时间复杂度分析 取决于 btsorto, bound; backtrack(三个函 float bound ( int i, float w[], float P[[ float cr=M-CW: float b= btsorto一般为o(nlgn)只执行一次 /cw是运行过程中部分解的总重量,cp是总价值 Bound为o(n)在大多数 backtrack调用中 while((i< n)&&(W[]<= cr))I cr-= W[]; 搜索递归函数 backtrack的时间复杂度由递 b += P[] 归调用的次数决定 /直至背包中剩余容量无法装下下 数坏舞歪銘点题之与态空的树地点数 /允许分割,以求得上界(贪心法 调用 backtrack的代价就是执行 bound的 return b }回溯算法 25 bound()函数的计算方法 „ 得到当前结点出发可以达到的可能的最大价值 „ 从当前部分解(x0,x1,...,xk-1)开始，采用贪心法计 算一般背包问题的策略，允许最后一个物品被分割 后加入背包，从而得到从结点i出发的子树中可以达 到的总价值的上界。 „ 如果这个上界小于当前的bp值，说明该子树不 可能包含最优解，就可以被“剪枝”，则将这个 部分解结点变为死结点 回溯算法 26 回溯算法—btKnapsack头 float btKnapsack(int n, int X[], float W[],float P[],float M) { cw=0; cp=0; for (int i=0;i<n;i++) { cp += P[i]; cw += W[i]; } // 计算总价值和总重量 if (cw <= M) return cp; // 可以全部装入 btSort(W,P,n); // 按价值重量比排序 cp = cw = 0; bp=0; backtrack(0, X, W, P, M); // 递归回溯 return bp; } 返回最优解的总价值，同时把最优解放在全局数组Y[]中 回溯算法 27 递归函数：backtrack() void backtrack(int i, int X[], float W[], float P[], float M) { //已到叶结点，取得当前最大价值，回溯 if (i>=n) { if (cp > bp) { bp = cp; for (int j=0; j<n; j++) Y[j] = X[j]; } return; } 回溯算法 28 // W存储各物品重量 if ( cw + W[i] <=M) { // 取物品i X[i] = 1; cw += W[i]; cp += P[i]; // P是存储各物品价值的数组 backtrack(i+1, X, W, P, M); // 前进，搜索 cw -= W[i]; // 回溯, 消除标记 cp -= P[i]; } if (bound(i+1, W, P) > bp) { // 不取物品i X[i] = 0; backtrack(i+1, X, W, P, M); // 前进，搜索 } } 回溯算法 29 限界函数:bound(i) float bound(int i, float W[], float P[]) { float cr = M - cw; float b = cp; //cw是运行过程中部分解的总重量，cp是总价值 while (( i < n ) && (W[i] <= cr)) { cr -= W[i]; b += P[i]; i++; } //直至背包中剩余容量无法装下下一个物品 //允许分割，以求得上界（贪心法） if (i < n) b += P[i] * cr / W[i]; return b; } 回溯算法 30 时间复杂度分析 取决于btSort(),bound();backtrack()三个函 数 „ btSort()一般为O(nlogn),只执行一次 „ Bound()为O(n)在大多数backtrack()调用中 bound()被调用一次 „ 搜索递归函数backtrack()的时间复杂度由递 归调用的次数决定 „ 最坏情形的调用次数恰恰与状态空间的树结点数一 致，并且结点数2^(n+1)-1 „ 每次调用backtrack()的代价就是执行bound()的 代价O(n)