A={v,w2,…,wn}中的元素是按不降的次序排列的,则上述继续搜 索的条件还可以加强为 ∑x+∑≥Mamd∑wx+Wk+1≤M 7.3) k+l≤ 上述不等式记做Bk。 定和子集问题的回溯算法伪代码 SumSubset(s,k,r)/寻找W[1:n]中元素和为M的所有子集。 //w[l:n]中元素按不降次序排列,进入此过程时,X[1], //X[k-1]的值已经确定。记s=∑W小X[小,r=∑W l≤j≤k-1 k≤j≤n //假定W[1]≤M,∑W[门≥M l≤j≤n 1 global integer M, n; global real W[l: n]; 2 global boolean X[l: n] 3 real, s: integer k, j: //由于B-=true,因此s+W[k]≤M 4X[k]=1;//生成左儿子。 5 if s+Wk print (X[j], j from 1 to k) else fs+W[k]+W[k+1]≤Mthe Sum Subset(s+Wlk, k+1, r-WLkD 9 endif 10 dif{ , , , } A = w 1 w2 L wn 中的元素是按不降的次序排列的，则上述继续搜 索的条件还可以加强为 w x w M and w xi wk M i k i k i n i i i k i + ≥ + + ≤ ≤ ≤ + ≤ ≤ ≤ ≤ ∑ ∑ ∑ 1 1 1 1 (7.3) 上述不等式记做 Bk。 定和子集问题的回溯算法伪代码 SumSubset(s,k,r) // 寻找 W[1:n]中元素和为 M 的所有子集。 //W[1:n]中元素按不降次序排列，进入此过程时，X[1], . . . , //X[k-1]的值已经确定。记 ∑ ≤ ≤ − = 1 1 [ ] [ ] j k s W j X j ， ∑ ≤ ≤ = k j n r W[ j] //假定 W[1] ≤ M, ∑ ≤ ≤ ≥ j n W j M 1 [ ] 1 global integer M, n; global real W[1:n]; 2 global boolean X[1:n]; 3 real r, s; integer k, j; //由于 Bk-1=true，因此 s + W[k]≤ M 4 X[k]=1; // 生成左儿子。 5 if s + W[k]= M then print (X[j],j from 1 to k); 6 else 7 if s + W[k] + W[k+1] ≤ M then 8 SumSubset(s+W[k], k+1, r-W[k]); 9 endif 10 endif