子集和数问题

　　子集和数问题是假定有n个不同的正数(通常称为权)，要求找出这些数中所有使得某和数为M的组合。

子集和数问题的递归回溯算法,代码如下：

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

1. #include <stdio.h>  
2. int M,n;  
3. int w[100];  
4. int x[100];  
5. void SumOfSub(int s, int k, int r)  
6. {  
7.      //s=w[1]*x[1]+...+w[k-1]*x[k-1]  
8.      //r=w[k]+...w[n]   
9.      //w[i]需要按非降次序排列   
10.     int i;  
11.     x[k]=1;  
12.     for(i=1; i<=k; i++)  
13.        printf("%d", x[i]);  
14.     printf("/n");  
15.     if(s+w[k]==M) //子集找到  
16.     {  
17.         printf("ans:");  
18.         for(i=1; i<=k; i++)  
19.             printf("%d", x[i]);  
20.         printf("/n");  
21.     }else if(s+w[k]+w[k+1]<=M)  
22.         SumOfSub(s+w[k], k+1, r-w[k]);  
23.       
24.     if(s+r-w[k]>=M && s+w[k+1]<=M)  
25.     {  
26.         x[k]=0;  
27.         SumOfSub(s, k+1, r-w[k]);  
28.     }  
29. }   
30. int main()  
31. {  
32.     int s,k,r;  
33.     n=4;  
34.     w[1]=7;  
35.     w[2]=11;  
36.     w[3]=13;  
37.     w[4]=24;  
38.     M=31;  
39.       
40.     s=0;  
41.     k=1;  
42.     r=55;  
43.       
44.     SumOfSub(s, k, r);  
45.     getchar();  
46.     return 0;  
47. }