Like us on google+

Wednesday, 21 May 2014

Widgets

Subset Sum Problem Using Backtracking approach.

#include<stdio.h>
void subset(int n,int w[],int d);

int main()
{

int n;
int w[10];
int d;
int i;
printf("enter numbr of elements in array\n");
scanf("%d",&n);

printf("enter array elements in ascending order\n");

for(i=1;i<=n;i++)
scanf("%d",&w[i]);


printf("enter max subset value\n");
scanf("%d",&d);
subset(n,w,d);
}


void subset(int n,int w[],int d)
{
int i;
int s=0;
int x[10]; // tracking of values in array w
for(i=1;i<=n;i++)
x[i]=0;

int k=1;
x[k]=1;


while(1)
{
if(k<=n && x[k]==1)
{
if(s+w[k]==d) // soln found
{
printf("soln is\n");
for(i=1;i<=n;i++)
{
if(x[i]==1)
printf("%d \t",w[i]);



}
printf("\n");
x[k]=0;
}
else if(s+w[k]<d)
{
s+=w[k];
}
else
{
x[k]=0;
}
}
else
{
k--;
while(k>0 && x[k]==0)
{
k--;
}

if(k==0)
break;

x[k]=0;
s=s-w[k];
}
k+=1;
x[k]=1;
}



}
--------------------------------------------------------------------------------------------------------------
OUTPUT:
enter number of elements in array
5
enter array elements in ascending order
1 2 4 5 6
enter max subset value
6
soln is
1 5
soln is
2 4
soln is
6

SHARE THIS POST   

  • Facebook
  • Twitter
  • Myspace
  • Google Buzz
  • Reddit
  • Stumnleupon
  • Delicious
  • Digg
  • Technorati
About us:
Hi guys Sandesh and Rajesh here ... studing engineering in PESIT started this blog as a google contest and also we love blogging ...Hope u like it ...Encourage us by liking us on g+... Any queries dont hesitate to ask Read More →

0 comments: