DAA PROGRAM

Fractional Knapsack Problem

#include<conio.h>
#include<stdio.h>
void get();
void show();
void sort();
#define max 10
int i,j, n,y[max],fp=-1,fw;
float unit[max],w[max],p[max],m,U, x[max];

int main()
{
//now calculate the values of x[i] that sould be included in knapsack
get();
sort();
for(i=1;i<=n;i++)
{
x[i]=0.0;
}
U=m;
for(i=1;i<=n;i++)
{
if(w[i]>U)
break;
x[i]=1.0;
U=U-w[i];
}
if(i<=n)
x[i]=U/w[i];
printf("&f",x[i]);

show();
getch();
return 0;
}

//input the values of n , w , p[i] , w[i]
void get()
{
printf("\n Enter total number of items: ");
scanf("%d",&n);
printf("\n Enter the Maximum capacity of the Sack: ");
scanf("%f",&m);
for(i=1;i<=n;i++)
{
printf("\n Enter the weight of the item # %d : ",i);
scanf("%f",&w[i]);
printf("\n Enter the profit of the item # %d : ", i);
scanf("%f", &p[i]);
}
}
//now arrange the values in p[i] and w[i] in dreacreasing order of the ration p[i]/w[i]

void sort()
{
int t,t1;
float t2;
for(i=1;i<=n;i++)
unit[i] = p[i] / w[i];
for(i=1;i<=n-1;i++)
{
for(j=i+1;j<=n;j++)
{
if(unit[i]  < unit[j])
{
t2 = unit[i];
unit[i] = unit[j];
unit[j] = t2;

t = p[i];
p[i] = p[j];
p[j] = t;

t1 = w[i];
w[i] = w[j];
w[j] =t1;
}
}
}
}

//now calculate the values of x[i] that sould be included in knapsack
void show()
{
float s=0.0;
printf("\n\tItem\tWeight\t\tCost\t\tUnit Profit\tSelected ");
for(i=1;i<=n;i++)
printf("\n\t%d\t%f\t%f\t%f\t%f",i,w[i],p[i],unit[i],x[i]);
printf("\n\n The Sack now holds following items ");
for(i=1;i<=n;i++)
{
if(x[i]!=0)
{
s += p[i] * x[i];
printf("%d\t",i);
}
}
printf("%f",s);
}

Dijkastra's Algorithm Program in C

#include "stdio.h"
#include "conio.h"
#define infinity 999

void dij(int n,int v,int cost[10][10],int dist[])
{
 int i,u,count,w,flag[10],min;
 for(i=1;i<=n;i++)
  flag[i]=0,dist[i]=cost[v][i];
 count=2;
 while(count<=n)
 {
  min=99;
  for(w=1;w<=n;w++)
   if(dist[w]<min && !flag[w])
    min=dist[w],u=w;
  flag[u]=1;
  count++;
  for(w=1;w<=n;w++)
   if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
    dist[w]=dist[u]+cost[u][w];
 }
}

void main()
{
 int n,v,i,j,cost[10][10],dist[10];
 clrscr();
 printf("\n Enter the number of nodes:");
 scanf("%d",&n);
 printf("\n Enter the cost matrix:\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]=infinity;
  }
 printf("\n Enter the source matrix:");
 scanf("%d",&v);
 dij(n,v,cost,dist);
 printf("\n Shortest path:\n");
 for(i=1;i<=n;i++)
  if(i!=v)
   printf("%d->%d,cost=%d\n",v,i,dist[i]);
 getch();
}

- 

DFS Program in C

#include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n;
void dfs(int v)
{
 int i;
 reach[v]=1;
 for(i=1;i<=n;i++)
  if(a[v][i] && !reach[i])
  {
   printf("\n %d->%d",v,i);
   dfs(i);
  }
}
void main()
{
 int i,j,count=0;
 clrscr();
 printf("\n Enter number of vertices:");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  reach[i]=0;
  for(j=1;j<=n;j++)
   a[i][j]=0;
 }
 printf("\n Enter the adjacency matrix:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   scanf("%d",&a[i][j]);
 dfs(1);
 printf("\n");
 for(i=1;i<=n;i++)
 {
  if(reach[i])
   count++;
 }
 if(count==n)
  printf("\n Graph is connected");
 else
  printf("\n Graph is not connected");
 getch();

- 

BFS Program in C

#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
 for(i=1;i<=n;i++)
  if(a[v][i] && !visited[i])
   q[++r]=i;
 if(f<=r)
 {
  visited[q[f]]=1;
  bfs(q[f++]);
 }
}
void main()
{
 int v;
 clrscr();
 printf("\n Enter the number of vertices:");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  q[i]=0;
  visited[i]=0;
 }
 printf("\n Enter graph data in matrix form:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   scanf("%d",&a[i][j]);
 printf("\n Enter the starting vertex:");
 scanf("%d",&v);
 bfs(v);
 printf("\n The node which are reachable are:\n");
 for(i=1;i<=n;i++)
  if(visited[i])
   printf("%d\t",i);
  else
   printf("\n Bfs is not possible");
 getch();
}

- 

Binary Search Program in C

#include<stdio.h>
#include<stdio.h>
void main()
{
int a[100],i,first,last,mid,n,search,c;
clrscr();
printf("Enter number of elements");
scanf("%d",&n);
printf("Enter value :");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("Enter value to find\n");
scanf("%d",&search);
first=0;
last=n-1;
while(first<=last)
{
mid=(first+last)/2;
if(a[mid]==search)
{
printf("\nValue is found");
break;
}
else if(a[mid]<search)
{
last=mid-1;
// break;
}
else if(a[mid]<search)
{
first=mid+1;
}
else
{
printf("Value is not found");
break;
}
}
getch();
}

Selection Sort Program in C

#include<stdio.h>
#include<stdio.h>
void main()
{
int i,j,n[10],temp;
printf("Enter 10 numbers one by one ");
for(i=0;i<10;i++)
scanf("%d",&n[i]);
printf("The original numbers are \n");
for(i=0;i<10;i++)
printf("%5d",n[i]);
for(i=0;i<10;i++)
{
for(j=i+1;j<10;j++)
{
if(n[i]>n[j])
{
temp=n[i];
n[i]=n[j];
n[j]=temp;
}
}
}
printf("\nNumbers are in sorted order\n");
for(i=0;i<10;i++)
{
printf("%d",n[i]);
}
getch();
}