DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:1
Aim: Writeaprogramtoperformoperationcountforagivenpseudocode
#include<stdio.h>
//#include<conio.h>voi
d main()
{
int count=0,sum=0,n,i,a[50];
//clrscr();
count=count+1;
printf("\nEnterthenvalue:");
scanf("%d",&n);
count=count+1;
printf("\nEnter%dvaluestosum:",n); for(i=0;i<n;i++)
{
count=count+1;
scanf("%d",&a[i]);
}
count=count+1;
for(i=0;i<n;i++)
{
count=count+1;
sum=sum+a[i];
count=count+1;
}
count=count+1;
printf("\nTheof%d valuesis:%dandcount is=%d",n,sum,count);
//getch();
Output:
Preparedby:[Link],RGMCET Page2
DESIGNANDANALYSISOFALGORITHMSLAB
Preparedby:[Link],RGMCET Page3
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:2
Aim:WriteaprogramtoperformBubblesort for anygiven listof numbers.
Program:
#include<stdio.h>
#include<conio.h>
voidbubblesort(int[],int);
void display(int[],int);
int main()
{
inta[20],n,i;
clrscr();
printf("\nEnterthenumberofelementsinarrayare:");
scanf("%d",&n);
printf("\nEnter%delementsinthearray:",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bubblesort(a,n);
printf("\nThesortedelementsinthearrayare:");
display(a,n);
getch();
return0;
}
voidbubblesort(inta[],int n)
{
inti,j,temp,excg=0;
int last=n-1;
for(i=0;i<n;i++)
{
excg=0;
for(j=0;j<last;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
excg++;
}
}
}
if(excg==0)
return ;
else
last=last-1;
Preparedby:[Link],RGMCET Page4
DESIGNANDANALYSISOFALGORITHMSLAB
}
voiddisplay(inta[],intn)
{
int i;
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
Output:
Preparedby:[Link],RGMCET Page5
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:3
Aim:WriteaprogramtoperformInsertionsortforanygiven listof numbers.
Program:
#include<stdio.h>
#include<conio.h>voi
d inssort(int[],int);
void display(int[],int);
int main()
{
inta[20],n,i;
clrscr();
printf("\nEnterthenumberofelementsinarrayare:");
scanf("%d",&n);
printf("\nEnter%delementsinthearray:",n); for(i=0;i<n;i++)
scanf("%d",&a[i]);
inssort(a,n);
printf("\nThesortedelementsinthearrayare:"); display(a,n);
getch();
return0;
}
voidinssort(int a[],int n)
{
int i,j,index=0;
for(i=1;i<n;i++)
{
index=a[i];
j=i;
while((j>0)&&(a[j-1]>index))
{
a[j]=a[j-1];
j--;
}
a[j]=index;
}
}
voiddisplay(inta[],intn)
{
int i;
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
}
Preparedby:[Link],RGMCET Page6
DESIGNANDANALYSISOFALGORITHMSLAB
Output:
Preparedby:[Link],RGMCET Page7
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:4
Aim:Write aprogram to performQuick sortforanygivenlist of numbers.
Program:
#include<stdio.h>
#include<conio.h>void
qsort(int[],int,int);
intpartition(int [],int,int);
voidqsort(inta[],intfirst,intlast)
{
int j;
if(first<last)
{
j=partition(a,first,last+1);
qsort(a,first,j-1);
qsort(a,j+1,last);
}
}
intpartition(inta[],intfirst,intlast)
{
intv=a[first];
int i=first;
int j=last;
inttemp=0;
do
{
do
{
i++;
}while(a[i]<v);
do
{
j--;
}while(a[j]>v);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);
a[first]=a[j];
a[j]=v;
return j;
}
Preparedby:[Link],RGMCET Page8
DESIGNANDANALYSISOFALGORITHMSLAB
int main()
{
inta[40],i,n;
clrscr();
printf("\nEnterthenoofelements(size):");
scanf("%d",&n);
printf("\nEntertheELementstosort:"); for(i=0;i<n;i++)
scanf("%d",&a[i]);
qsort(a,0,n-1);
printf("\nTheELementsaftersortingare:");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
getch();
return0;
}
Output:
Preparedby:[Link],RGMCET Page9
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:5
Aim:Write aprogram tofind Maximumand Minimumof thegiven setof integer values.
Program:
#include<stdio.h>
#include<conio.h>
voidminmax(int,int,int,int);
int i,j,a[50],n,fmax,fmin;int
main()
{
clrscr();
printf("\nEnterthenumberofelementsinarrayare:");
scanf("%d",&n);
printf("\nEnter%delementsinthearray:",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nTheElementsinthearrayare:");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
//fmax=fmin=a[0];
minmax(0,n-1,a[0],a[0]);
printf("\n The minimum Element of the list of elements is:%d",fmin);
printf("\nThemaximumElementofthelistofelementsis:%d",fmax); getch();
return0;
}
voidminmax(inti,intj,intmax,intmin)
{
intgmax,gmin,hmax,hmin;
gmax=hmax=max;
gmin=hmin=min;
if(i==j)
{
fmax=fmin=a[i];
}
elseif(i==(j-1))
{
if(a[i]>a[j])
{
fmax=a[i];
fmin=a[j];
}
else
{
fmax=a[j];
Preparedby:[Link],RGMCET Page10
DESIGNANDANALYSISOFALGORITHMSLAB
fmin=a[i];
}
}
else
{
int mid=(i+j)/2;
minmax(i,mid,a[i],a[i]);
gmax=fmax;
gmin=fmin;
minmax(mid+1,j,a[mid+1],a[mid+1]);
hmax=fmax;
hmin=fmin;
if(gmax>hmax)
{
fmax=gmax;
}
else
{
fmax=hmax;
}
if(gmin>hmin)
{
fmin=hmin;
}
else
{
fmin=gmin;
}
}
}
Output:
Preparedby:[Link],RGMCET Page11
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:6
Aim:WriteaProgram toperformMergeSort onthegiventwo listsofinteger values.
Program:
#include<stdio.h>
#include<conio.h>
void merge(int[],int,int,int);
voidmergesort(int[], int,int);
voidmerge(int a[25], intlow,int mid, int high)
{
intb[25],h,i,j,k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++)
Preparedby:[Link],RGMCET Page12
DESIGNANDANALYSISOFALGORITHMSLAB
{
a[k]=b[k];
}
}
voidmergesort(int a[25],intlow,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a, low,mid,high);
}
}
void main()
{
inta[25],i,n;
clrscr();
printf("\nEnterthesizeoftheelementstobesorted:");
scanf("%d",&n);
printf("\nEntertheelementstosort:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nTheElementsbeforesortingare:");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
mergesort(a,0,n-1);
printf("\nTheelementsaftersortingare:");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
getch();
}
Output:
Preparedby:[Link],RGMCET Page13
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:7
Aim: WriteaProgramto perform BinarySearch foragivensetofintegervaluesrecursivelyand non-
recursively.
Program:
/*Aim:TowriteaCprogramtodemonstratetheBinarySearch*/
#include<stdio.h>
#include<conio.h>
void bubblesort(int[],int);
intbinsrch(int[],int,int,int);
void display(int[],int);
int i,j;
int main()
{
inta[20],n,key,pos=-1;
clrscr();
printf("\nEnterthenumberofelementsinarrayare:");
scanf("%d",&n);
printf("\nEnter%delementsinthearray:",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEntertheelementtobesearched:");
scanf("%d",&key);
bubblesort(a,n);
printf("\nThesortedelementsinthearrayare:");
display(a,n);
pos=binsrch(a,key,0,n-1);
if(pos!=-1)
printf("\nTheElement%disfoundinposition%d",key,pos); else
printf("\nElementnotfound");
getch();
return0;
}
intbinsrch(inta[],intkey,intlow,inthigh)
{
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(key<a[mid])
high=mid-
1;elseif(key>a[mid])
low=mid+1;
Preparedby:[Link],RGMCET Page14
DESIGNANDANALYSISOFALGORITHMSLAB
else
returnmid;
}
return-1;
}
voidbubblesort(inta[],int n)
{
inti,j,temp,excg=0;
int last=n-1;
for(i=0;i<n;i++)
{
excg=0;
for(j=0;j<last;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
excg++;
}
}
}
if(excg==0)
return ;
else
last=last-1;
}
voiddisplay(inta[],intn)
{
int i;
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
Output:
1.
Preparedby:[Link],RGMCET Page15
DESIGNANDANALYSISOFALGORITHMSLAB
2.
Preparedby:[Link],RGMCET Page16
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:8
Aim:Write aprogramto find solution forknapsack problem usinggreedymethod.
Program:
#include<stdio.h>
#include<conio.h>
void readf();
voidknapsack(int,int);
void dsort(int n);
void
display(int);intp[20]
,w[20],n,m;
doublex[20],d[20],temp,res=0.0,sum=0.0;
void readf()
{
int m,n,i;
printf("\nEnterthenoofProfitsandweights:");
scanf("%d",&n);
printf("\nEntertheMaximumCapacityoftheKnapsack:");
scanf("%d",&m);
printf("\nEnter%dprofitsoftheweights:",n);
for(i=0;i<n;i++)
scanf("%d",&p[i]);
printf("\nEnter%dWeights:",n);
for(i=0;i<n;i++)
scanf("%d",&w[i]);
for(i=0;i<n;i++)
d[i]=(double)p[i]/w[i];
dsort(n);knapsack(m,n);
display(n);
}
voiddsort(int n)
{
int i,j,t;
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(d[j]<d[j+1])
{
temp=d[j];
d[j]=d[j+1];
d[j+1]=temp;
t=p[j];
Preparedby:[Link],RGMCET Page17
DESIGNANDANALYSISOFALGORITHMSLAB
p[j]=p[j+1];
p[j+1]=t;
t=w[j];
w[j]=w[j+1];
w[j+1]=t;
}
}
}
}
voiddisplay(intn)
{
int i,m;
printf("\nTheRequiredOptimalsolutionis:\n");
printf("Profits Weights Xvalue\n");
for(i=0;i<n;i++)
{
printf("%d\t%d\t%f\n",p[i],w[i],x[i]);
sum=sum+(p[i]*x[i]);
res=res+(w[i]*x[i]);
}
printf("\nTheTotalResultantProfitis:%f",sum);
printf("\nThetotalresultantWeightintotheknapsackis:%f",res);
}
voidknapsack(int m,int n)
{
int i,cu=m;
for(i=0;i<n;i++)
{
x[i]=0.0;
}
for(i=0;i<n;i++)
{
if(w[i]<cu)
{
x[i]=1.0;
cu=cu-w[i];
}
else
break;
}
if(i<=n)
{
x[i]=(double)cu/w[i];
}
}
Preparedby:[Link],RGMCET Page18
DESIGNANDANALYSISOFALGORITHMSLAB
int main()
{
clrscr();
readf();
getch();
return0;
Output:
Preparedby:[Link],RGMCET Page19
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:9
Aim:Writeaprogramto findminimumcost spanningtreeusingPrim’sAlgorithm.
Program:
#include<stdio.h>
#include<conio.h>
intn,cost[10][10],temp,nears[10];
void readv();
voidprimsalg();
void readv()
{
int i,j;
printf("\nEntertheNoofnodesorvertices:");
scanf("%d",&n);
printf("\nEntertheCostAdjacencymatrixofthegivengraph:");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if((cost[i][j]==0)&&(i!=j))
{
cost[i][j]=999;
}
}
}
}
void primsalg()
{
intk,l,min,a,t[10][10],u,i,j,mincost=0;
min=999;
for(i=1;i<=n;i++) //ToFindtheMinimumEdgeE(k,l)
{
for(u=1;u<=n;u++)
{
if(i!=u)
{
if(cost[i][u]<min)
{
min=cost[i][u];
k=i;
l=u;
}
}
}
Preparedby:[Link],RGMCET Page20
DESIGNANDANALYSISOFALGORITHMSLAB
}
t[1][1]=k;
t[1][2]=l;
printf("\nTheMinimumCostSpanningtreeis...");
printf("\n(%d,%d)-->%d",k,l,min);
for(i=1;i<=n;i++)
{
if(i!=k)
{
if(cost[i][l]<cost[i][k])
{
nears[i]=l;
}
else
{
nears[i]=k;
}
}
}
nears[k]=nears[l]=0;
mincost=min;
for(i=2;i<=n-1;i++)
{
j=findnextindex(cost,nears); t[i][1]=j;
t[i][2]=nears[j];
printf("\n(%d,%d)-->%d",t[i][1],t[i][2],cost[j][nears[j]]);
mincost=mincost+cost[j][nears[j]];
nears[j]=0;
for(k=1;k<=n;k++)
{
if(nears[k]!=0&& cost[k][nears[k]]>cost[k][j])
{
nears[k]=j;
}
}
}
printf("\nTheRequiredMincostoftheSpanningTree is:%d",mincost);
}
intfindnextindex(intcost[10][10],int nears[10])
{
intmin=999,a,k,p;
for(a=1;a<=n;a++)
{
p=nears[a];
if(p!=0)
Preparedby:[Link],RGMCET Page21
DESIGNANDANALYSISOFALGORITHMSLAB
{
if(cost[a][p]<min)
{
min=cost[a][p];
k=a;
}
}
}
returnk;
}
void main()
{
clrscr();
readv();
primsalg();
getch();
}
Output:
Preparedby:[Link],RGMCET Page22
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:10
Aim:Writeaprogramto findminimum costspanningtreeusingKruskal’sAlgorithm.
Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
intmin,mincost=0,cost[9][9],parent[9];
int find(int);
intuni(int,int);
void main()
{
clrscr();
printf("\n\tImplementationofKruskal'salgorithm\n");
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
printf("\nEnterthecostadjacencymatrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
printf("TheedgesofMinimumCostSpanningTreeare\n"); while(ne
< n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j] <min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
Preparedby:[Link],RGMCET Page23
DESIGNANDANALYSISOFALGORITHMSLAB
{
printf("%dedge(%d,%d)=%d\n",ne++,a,b,min); mincost
+=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimumcost=%d\n",mincost);
getch();
}
intfind(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,intj)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return0;
}
Output:
Preparedby:[Link],RGMCET Page24
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:11
Aim:Writeaprogramto performSinglesourceshortestpath problemforagivengraph.
Program:
#include<stdio.h>
#include<conio.h>
void readf();
void SP();
intcost[20][20],dist[20],s[20];
int n,u,min,v,w;
void readf()
{
int i,j;
printf("\nEnterthenoofvertices:");
scanf("%d",&n);
printf("\nEntertheCostofvertices:"); for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
}
void SP()
{
int i,j;
printf("\nEnterthesourcevertex:");
scanf("%d",&v);
for(i=1;i<=n;i++)
{
s[i]=0;
dist[i]=cost[v][i];
}
s[v]=1;
dist[v]=0;
for(i=2;i<=n;i++)
{
min=dist[i];
for(j=2;j<=n;j++)
{
if(s[j]==0)
{
Preparedby:[Link],RGMCET Page25
DESIGNANDANALYSISOFALGORITHMSLAB
if(min>dist[j])
{
min=dist[j];
u=j;
}
}
}
s[u]=1;
for(w=1;w<=n;w++)
{
if(cost[u][w]!=0&&s[w]==0)
{
if(dist[w]>(dist[u]+cost[u][w]))
{
dist[w]=dist[u]+cost[u][w];
}
}
}
}
printf("\nFromtheSourcevertex%d",v);
for(i=1;i<=n;i++)
printf("\n%d->%d",i,dist[i]);
}
void main()
{
clrscr();
readf();
SP();
getch();
}
Preparedby:[Link],RGMCET Page26
DESIGNANDANALYSISOFALGORITHMSLAB
Output:
Preparedby:[Link],RGMCET Page27
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:12
Aim:Write aprogram tofind solution forjob sequencingwith deadlines problem.
Program:
#include<stdio.h>
#include<conio.h>
int jobseq();
void psort();
inttp,j[10],d[10],p[10],n;
void main()
{
int i,k;
clrscr();
printf("\nEnterthen'oofjobs:");
scanf("%d",&n);
printf("\nEnterthe%dDeadlinesforthejobs:",n);
for(i=1;i<=n;i++)
scanf("%d",&d[i]);
printf("\nEntertheProfitsrequiredforjobs:");
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
psort();
for(i=1;i<n;i++)
printf("%d",p[i]);
k=jobseq();
printf("\nTheRequiredSolutionis:"); for(i=1;i<=k;i++)
{
tp=tp+p[j[i]];
printf("%d-->",j[i]);
}
printf("\nProfits:%d",tp);
getch();
}
int jobseq()
{
int i,k,q;
d[0]=0;
j[0]=0;
j[1]=1;
k=1;
for(i=2;i<=n;i++)
{
int r=k;
while((d[j[r]]>d[i])&&(d[j[r]]!=r))
Preparedby:[Link],RGMCET Page28
DESIGNANDANALYSISOFALGORITHMSLAB
r=r-1;
if((d[j[r]]<=d[i])&&(d[i]>r))
{
for(q=k;q>=r+1;q--)
{
j[q+1]=j[q];
}
j[r+1]=i;
k=k+1;
}
}
returnk;
}
void psort()
{
int i,k,temp1;
for(i=1;i<=n;i++)
{
for(k=1;k<=n-i;k++)
{
if(p[k]<p[k+1])
{
temp1=p[k];
p[k]=p[k+1];
p[k+1]=temp1;
temp1=j[k];
j[k]=j[k+1];
j[k+1]=temp1;
temp1=d[k];
d[k]=d[k+1];
d[k+1]=temp1;
}
}
}
}
Preparedby:[Link],RGMCET Page29
DESIGNANDANALYSISOFALGORITHMSLAB
Output:
1.
2.
Preparedby:[Link],RGMCET Page30
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:13
Aim:Write aprogram forall pairsshortest path problem.
Program:
#include<stdio.h>
#include<conio.h>
void readf();
void amin();
intcost[20][20],a[20][20];
int i,j,k,n;
void readf()
{
printf("\nEnterthenoofvertices:");
scanf("%d",&n);
printf("\nEntertheCostofvertices:");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0&&(i!=j))
cost[i][j]=999;
a[i][j]=cost[i][j];
}
}
}
void amin()
{
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]>a[i][k]+a[k][j])
{
a[i][j]=a[i][k]+a[k][j];
}
}
}
}
printf("\nTheAllpairshortestpathis:"); for(i=0;i<n;i++)
{
printf("\n");
Preparedby:[Link],RGMCET Page31
DESIGNANDANALYSISOFALGORITHMSLAB
for(j=0;j<n;j++)
{
printf("%d\t",a[i][j]);
}
}
}
void main()
{
clrscr();
readf();
amin();
getch();
}
Output:
Preparedby:[Link],RGMCET Page32
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:14
Aim:Write aprogram tosolveN-QUEENS problem.
Program:
#include<stdio.h>
#include<conio.h>
#include<math.h>
void readv();
voidnqueen(int,int);
int place(int,int);
intx[25],count=0;
void readv()
{
int n;
printf("\nEnterthenoofQueenstobeplaced:");
scanf("%d",&n);
printf("\nThePlacesinwhichthe%dQueensaretoplacedinthe%dx%dChessBoard is:",n,n);
nqueen(1,n);
printf("\nTheNoofSolutionsforthe %dQueensProblem are:%d",n,count);
}
voidnqueen(intk,intn)
{
int i,j;
for(i=1;i<=n;i++)
{
if(place(k,i))
{
x[k]=i;
if(k==n)
{
count++;
if(count%10==0)
getch();
printf("\n");
for(j=1;j<=n;j++)
{
printf("%d\t",x[j]);
}
}
else
{
nqueen(k+1,n);
}
}
Preparedby:[Link],RGMCET Page33
DESIGNANDANALYSISOFALGORITHMSLAB
}
}
intplace(intk,inti)
{
int j;
for(j=1;j<=k-1;j++)
{
if((x[j]==i)||(abs(x[j]-i)==abs(j-k)))
{
return0;
}
}
return1;
}
void main()
{
clrscr();
readv();
getch();
}
Output:
Preparedby:[Link],RGMCET Page34
DESIGNANDANALYSISOFALGORITHMSLAB
ExperimentNo:15
Aim:Write aprogram to solveSum ofsubsets problem foragiven setofdistinct numbers.
Program:
#include<stdio.h>
#include<conio.h>
void SumOfSub(int,int,int);
intx[25],n,m=0,sum=0,w[25];;
void readf()
{
int i;
printf("\nEnterthenoofvaluesintheset:");
scanf("%d",&n);
printf("\nEnterthe%dweightsofthevaluesintheset:",n); for(i=1;i<=n;i++)
{
scanf("%d",&w[i]);
sum=sum+w[i];
x[i]=0;
}
printf("\nEntertherequiredsumofthevaluesinthesubset:");
scanf("%d",&m);
printf("\nTheTotalsumoftheweightsis:%d",sum); SumOfSub(0,1,sum);
}
void SumOfSub(int s,intk,int r)
{
int i,j;
x[k]=1;
if(sum>=m)
{
if(s+w[k]==m)
{
printf("\n");
for(j=1;j<=n;j++)
{
printf("%d\t",x[j]);
}
printf("\n-->");
for(j=1;j<=k;j++)
{
if(x[j]==1)
printf("%d\t",w[j]);
}
}
Preparedby:[Link],RGMCET Page35
DESIGNANDANALYSISOFALGORITHMSLAB
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]);
}
}
else
{
printf("\nNoSolutionsAvailablebecausesumofallweightsis%dlessthanrequiredsum
%d",sum,m);
}
}
void main()
{
clrscr();
readf();
getch();
}
Output:
Preparedby:[Link],RGMCET Page36