原创 子集和数问题

void SumOfSub(s,k,r) {
//找w(1:n)中和数为M的所有子集。进入此过程时x(1),…,X(k-1)的值已确定。
k-1 n
//s=ΣW(i)X(i)且r=ΣW(j)。W(j)按非递减排列。假定w(1)≤M，ΣW(i)≥M
j=1 j=k
l int M，n；float W[n]；bool X[n]； //M、W[n]、X[n]定义成全局变量
2 float r，s；int k，j；
//生成左子结点。注意，由于Bk-1=true，因此s + w[k]≤M
3 X[k]=1；
4 if(s+w[k]==M) { //子集找到
5 print(X[j],j=1 to k)；}
//由于W(j)＞0，1≤j≤k，所以不存在递归调用
6 else
7 if(s＋W[k]＋W[k+1]<=M) { //Bk=true
8 SumOfSub(s+W[k]，k+1，r-W[k])；}
9 //endif
10 //endif
//生成右孩子和计算 Bk的值 //
11 if((s+r-W[k]>=M) and (s＋w(k＋1)<=M)) { //Bk=true
12 X[k]=0；
13 SumOfSub(s,k+l,r-W[k])；
14 }；//if
15}//SumOfSub