子集和数问题的实现
源代码：
#include <stdio.h>
#define N 8
int X[N]={0};
int W[N];
int M,NUM=0;
int main()
{
?void input();
?void sumofsub(int,int,int);
?int s,r,k;
?input();
?s = r = 0;
?for(k=0;k<N;k++)
??r += W[k];
?k = 0;
?if(M > r || M < W[0])
??printf("no answer!\n");
?else
?{
??sumofsub(s,k,r);
?}
?return 0;
}
void input()
{
?int i;
?printf("input the set of W[1-%d]:",N);
?for(i=0;i<N;i++)
?{
??scanf("%d",&W[i]);
?}
?printf("input the sum M = ");
?scanf("%d",&M);
}
void sumofsub(int s,int k,int r)
{
?void print(int);
?X[k] = 1;
?if(s+W[k] == M)
??print(k);
?else
?{
??if(s+W[k]+W[k+1] <= M)
???sumofsub(s+W[k],k+1,r-W[k]);
?}
?if(s+r-W[k] >= M && s+W[k+1] <= M)
?{
??X[k] = 0;
??sumofsub(s,k+1,r-W[k]);
?}
}
void print(int k)
{
?int i;
?NUM++;
?printf("the %dth answer is:",NUM);
?for(i=0;i<=k;i++)
?{
??printf("%d ",X[i]);
?}
?for(;i<N;i++)
?{
??printf("%d ",0);
?}
?printf("\n");
}
结果：
input the set of W[1-8]:1 2 3 4 5 6 7 8
input the sum M = 8
the 1th answer is:1 1 0 0 1 0 0 0
the 2th answer is:1 0 1 1 0 0 0 0
the 3th answer is:1 0 0 0 0 0 1 0
the 4th answer is:0 1 0 0 0 1 0 0
the 5th answer is:0 0 1 0 1 0 0 0
the 6th answer is:0 0 0 0 0 0 0 1
?
