Trend Posts
Author
View LUQMAN's profile
Monday, July 21, 2014
/*Find a subset of a given set S = {sl, s2,.....,sn} of n positive integerswhose sum is equal to a given positive integer d. For example, if S={1, 2, 5, 6, 8} and d = 9 there are two solutions{1,2,6}and{1,8}.Asuitable message is to be displayed if the given problem instancedoesn't have a solution.*/
#include<stdio.h>
void subset(int,int,int);
int i,w[10],n,sum=0,x[10],c=0,k,r,d;
void main()
{
printf("\nEnter the number of elements\n");
scanf("%d",&n);
printf("\nEnter the elements in the ascending order\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
printf("\nEnter the sum:\n");
scanf("%d",&d);
for(i=0;i<n;i++)
sum=sum+w[i];
if(sum<d || d<w[0])
printf("\nSubset is not possible\n");
subset(0,0,sum);
if(c==0)
printf("\nSubset is not possible\n");
}
void subset(int cs,int k,int r)
{
x[k]=1;
if(cs+w[k]==d)
{
printf("\nSolution %d is: {",++c);
for(i=0;i<=k;i++)
if(x[i]==1)
printf("%d,",w[i]);
printf("\b }");
}
else if(cs+w[k]+w[k+1]<=d)
subset(cs+w[k],k+1,r-w[k]);
if(cs+r-w[k]>=d && cs+w[k+1]<=d)
{
x[k]=0;
subset(cs,k+1,r-w[k]);
}
}
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment
You are very Important to Us...
STAY TUNE...